Coverage Report

Created: 2018-10-23 03:11

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_input.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2008-2009 Katholieke Universiteit Leuven
3
 * Copyright 2010      INRIA Saclay
4
 * Copyright 2012-2013 Ecole Normale Superieure
5
 *
6
 * Use of this software is governed by the MIT license
7
 *
8
 * Written by Sven Verdoolaege, K.U.Leuven, Departement
9
 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
10
 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
11
 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 
12
 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
13
 */
14
15
#include <ctype.h>
16
#include <stdio.h>
17
#include <string.h>
18
#include <isl_ctx_private.h>
19
#include <isl_map_private.h>
20
#include <isl/set.h>
21
#include <isl_seq.h>
22
#include <isl_stream_private.h>
23
#include <isl/obj.h>
24
#include "isl_polynomial_private.h"
25
#include <isl/union_set.h>
26
#include <isl/union_map.h>
27
#include <isl_mat_private.h>
28
#include <isl_aff_private.h>
29
#include <isl_vec_private.h>
30
#include <isl/list.h>
31
#include <isl_val_private.h>
32
33
struct variable {
34
  char            *name;
35
  int          pos;
36
  struct variable   *next;
37
};
38
39
struct vars {
40
  struct isl_ctx  *ctx;
41
  int    n;
42
  struct variable *v;
43
};
44
45
static struct vars *vars_new(struct isl_ctx *ctx)
46
3.14k
{
47
3.14k
  struct vars *v;
48
3.14k
  v = isl_alloc_type(ctx, struct vars);
49
3.14k
  if (!v)
50
0
    return NULL;
51
3.14k
  v->ctx = ctx;
52
3.14k
  v->n = 0;
53
3.14k
  v->v = NULL;
54
3.14k
  return v;
55
3.14k
}
56
57
static void variable_free(struct variable *var)
58
3.14k
{
59
4.70k
  while (var) {
60
1.55k
    struct variable *next = var->next;
61
1.55k
    free(var->name);
62
1.55k
    free(var);
63
1.55k
    var = next;
64
1.55k
  }
65
3.14k
}
66
67
static void vars_free(struct vars *v)
68
3.14k
{
69
3.14k
  if (!v)
70
0
    return;
71
3.14k
  variable_free(v->v);
72
3.14k
  free(v);
73
3.14k
}
74
75
static void vars_drop(struct vars *v, int n)
76
3.47k
{
77
3.47k
  struct variable *var;
78
3.47k
79
3.47k
  if (!v || !v->v)
80
211
    return;
81
3.26k
82
3.26k
  v->n -= n;
83
3.26k
84
3.26k
  var = v->v;
85
10.6k
  while (--n >= 0) {
86
7.34k
    struct variable *next = var->next;
87
7.34k
    free(var->name);
88
7.34k
    free(var);
89
7.34k
    var = next;
90
7.34k
  }
91
3.26k
  v->v = var;
92
3.26k
}
93
94
static struct variable *variable_new(struct vars *v, const char *name, int len,
95
        int pos)
96
8.90k
{
97
8.90k
  struct variable *var;
98
8.90k
  var = isl_calloc_type(v->ctx, struct variable);
99
8.90k
  if (!var)
100
0
    goto error;
101
8.90k
  var->name = strdup(name);
102
8.90k
  var->name[len] = '\0';
103
8.90k
  var->pos = pos;
104
8.90k
  var->next = v->v;
105
8.90k
  return var;
106
0
error:
107
0
  variable_free(v->v);
108
0
  return NULL;
109
8.90k
}
110
111
static int vars_pos(struct vars *v, const char *s, int len)
112
15.7k
{
113
15.7k
  int pos;
114
15.7k
  struct variable *q;
115
15.7k
116
15.7k
  if (len == -1)
117
15.7k
    len = strlen(s);
118
47.9k
  for (q = v->v; q; 
q = q->next32.1k
) {
119
42.2k
    if (strncmp(q->name, s, len) == 0 && 
q->name[len] == '\0'10.4k
)
120
10.1k
      break;
121
42.2k
  }
122
15.7k
  if (q)
123
10.1k
    pos = q->pos;
124
5.67k
  else {
125
5.67k
    pos = v->n;
126
5.67k
    v->v = variable_new(v, s, len, v->n);
127
5.67k
    if (!v->v)
128
0
      return -1;
129
5.67k
    v->n++;
130
5.67k
  }
131
15.7k
  return pos;
132
15.7k
}
133
134
static int vars_add_anon(struct vars *v)
135
3.23k
{
136
3.23k
  v->v = variable_new(v, "", 0, v->n);
137
3.23k
138
3.23k
  if (!v->v)
139
0
    return -1;
140
3.23k
  v->n++;
141
3.23k
142
3.23k
  return 0;
143
3.23k
}
144
145
/* Obtain next token, with some preprocessing.
146
 * In particular, evaluate expressions of the form x^y,
147
 * with x and y values.
148
 */
149
static struct isl_token *next_token(__isl_keep isl_stream *s)
150
53.6k
{
151
53.6k
  struct isl_token *tok, *tok2;
152
53.6k
153
53.6k
  tok = isl_stream_next_token(s);
154
53.6k
  if (!tok || tok->type != ISL_TOKEN_VALUE)
155
43.4k
    return tok;
156
10.1k
  if (!isl_stream_eat_if_available(s, '^'))
157
10.1k
    return tok;
158
0
  tok2 = isl_stream_next_token(s);
159
0
  if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
160
0
    isl_stream_error(s, tok2, "expecting constant value");
161
0
    goto error;
162
0
  }
163
0
164
0
  isl_int_pow_ui(tok->u.v, tok->u.v, isl_int_get_ui(tok2->u.v));
165
0
166
0
  isl_token_free(tok2);
167
0
  return tok;
168
0
error:
169
0
  isl_token_free(tok);
170
0
  isl_token_free(tok2);
171
0
  return NULL;
172
0
}
173
174
/* Read an isl_val from "s".
175
 *
176
 * The following token sequences are recognized
177
 *
178
 *  "infty"   ->  infty
179
 *  "-" "infty" ->  -infty
180
 *  "NaN"   ->  NaN
181
 *  n "/" d   ->  n/d
182
 *  v   ->  v
183
 *
184
 * where n, d and v are integer constants.
185
 */
186
__isl_give isl_val *isl_stream_read_val(__isl_keep isl_stream *s)
187
365
{
188
365
  struct isl_token *tok = NULL;
189
365
  struct isl_token *tok2 = NULL;
190
365
  isl_val *val;
191
365
192
365
  tok = next_token(s);
193
365
  if (!tok) {
194
0
    isl_stream_error(s, NULL, "unexpected EOF");
195
0
    goto error;
196
0
  }
197
365
  if (tok->type == ISL_TOKEN_INFTY) {
198
50
    isl_token_free(tok);
199
50
    return isl_val_infty(s->ctx);
200
50
  }
201
315
  if (tok->type == '-' &&
202
315
      
isl_stream_eat_if_available(s, ISL_TOKEN_INFTY)32
) {
203
32
    isl_token_free(tok);
204
32
    return isl_val_neginfty(s->ctx);
205
32
  }
206
283
  if (tok->type == ISL_TOKEN_NAN) {
207
52
    isl_token_free(tok);
208
52
    return isl_val_nan(s->ctx);
209
52
  }
210
231
  if (tok->type != ISL_TOKEN_VALUE) {
211
0
    isl_stream_error(s, tok, "expecting value");
212
0
    goto error;
213
0
  }
214
231
215
231
  if (isl_stream_eat_if_available(s, '/')) {
216
54
    tok2 = next_token(s);
217
54
    if (!tok2) {
218
0
      isl_stream_error(s, NULL, "unexpected EOF");
219
0
      goto error;
220
0
    }
221
54
    if (tok2->type != ISL_TOKEN_VALUE) {
222
0
      isl_stream_error(s, tok2, "expecting value");
223
0
      goto error;
224
0
    }
225
54
    val = isl_val_rat_from_isl_int(s->ctx, tok->u.v, tok2->u.v);
226
54
    val = isl_val_normalize(val);
227
177
  } else {
228
177
    val = isl_val_int_from_isl_int(s->ctx, tok->u.v);
229
177
  }
230
231
231
231
  isl_token_free(tok);
232
231
  isl_token_free(tok2);
233
231
  return val;
234
0
error:
235
0
  isl_token_free(tok);
236
0
  isl_token_free(tok2);
237
0
  return NULL;
238
231
}
239
240
/* Read an isl_val from "str".
241
 */
242
struct isl_val *isl_val_read_from_str(struct isl_ctx *ctx,
243
  const char *str)
244
348
{
245
348
  isl_val *val;
246
348
  isl_stream *s = isl_stream_new_str(ctx, str);
247
348
  if (!s)
248
0
    return NULL;
249
348
  val = isl_stream_read_val(s);
250
348
  isl_stream_free(s);
251
348
  return val;
252
348
}
253
254
static int accept_cst_factor(__isl_keep isl_stream *s, isl_int *f)
255
381
{
256
381
  struct isl_token *tok;
257
381
258
381
  tok = next_token(s);
259
381
  if (!tok || tok->type != ISL_TOKEN_VALUE) {
260
0
    isl_stream_error(s, tok, "expecting constant value");
261
0
    goto error;
262
0
  }
263
381
264
381
  isl_int_mul(*f, *f, tok->u.v);
265
381
266
381
  isl_token_free(tok);
267
381
268
381
  if (isl_stream_eat_if_available(s, '*'))
269
0
    return accept_cst_factor(s, f);
270
381
271
381
  return 0;
272
0
error:
273
0
  isl_token_free(tok);
274
0
  return -1;
275
381
}
276
277
/* Given an affine expression aff, return an affine expression
278
 * for aff % d, with d the next token on the stream, which is
279
 * assumed to be a constant.
280
 *
281
 * We introduce an integer division q = [aff/d] and the result
282
 * is set to aff - d q.
283
 */
284
static __isl_give isl_pw_aff *affine_mod(__isl_keep isl_stream *s,
285
  struct vars *v, __isl_take isl_pw_aff *aff)
286
120
{
287
120
  struct isl_token *tok;
288
120
  isl_pw_aff *q;
289
120
290
120
  tok = next_token(s);
291
120
  if (!tok || tok->type != ISL_TOKEN_VALUE) {
292
0
    isl_stream_error(s, tok, "expecting constant value");
293
0
    goto error;
294
0
  }
295
120
296
120
  q = isl_pw_aff_copy(aff);
297
120
  q = isl_pw_aff_scale_down(q, tok->u.v);
298
120
  q = isl_pw_aff_floor(q);
299
120
  q = isl_pw_aff_scale(q, tok->u.v);
300
120
301
120
  aff = isl_pw_aff_sub(aff, q);
302
120
303
120
  isl_token_free(tok);
304
120
  return aff;
305
0
error:
306
0
  isl_pw_aff_free(aff);
307
0
  isl_token_free(tok);
308
0
  return NULL;
309
120
}
310
311
static __isl_give isl_pw_aff *accept_affine(__isl_keep isl_stream *s,
312
  __isl_take isl_space *space, struct vars *v);
313
static __isl_give isl_pw_aff_list *accept_affine_list(__isl_keep isl_stream *s,
314
  __isl_take isl_space *dim, struct vars *v);
315
316
static __isl_give isl_pw_aff *accept_minmax(__isl_keep isl_stream *s,
317
  __isl_take isl_space *dim, struct vars *v)
318
6
{
319
6
  struct isl_token *tok;
320
6
  isl_pw_aff_list *list = NULL;
321
6
  int min;
322
6
323
6
  tok = isl_stream_next_token(s);
324
6
  if (!tok)
325
0
    goto error;
326
6
  min = tok->type == ISL_TOKEN_MIN;
327
6
  isl_token_free(tok);
328
6
329
6
  if (isl_stream_eat(s, '('))
330
0
    goto error;
331
6
332
6
  list = accept_affine_list(s, isl_space_copy(dim), v);
333
6
  if (!list)
334
0
    goto error;
335
6
336
6
  if (isl_stream_eat(s, ')'))
337
0
    goto error;
338
6
339
6
  isl_space_free(dim);
340
6
  return min ? 
isl_pw_aff_list_min(list)5
:
isl_pw_aff_list_max(list)1
;
341
0
error:
342
0
  isl_space_free(dim);
343
0
  isl_pw_aff_list_free(list);
344
0
  return NULL;
345
6
}
346
347
/* Is "tok" the start of an integer division?
348
 */
349
static int is_start_of_div(struct isl_token *tok)
350
15.8k
{
351
15.8k
  if (!tok)
352
0
    return 0;
353
15.8k
  if (tok->type == '[')
354
272
    return 1;
355
15.6k
  if (tok->type == ISL_TOKEN_FLOOR)
356
293
    return 1;
357
15.3k
  if (tok->type == ISL_TOKEN_CEIL)
358
0
    return 1;
359
15.3k
  if (tok->type == ISL_TOKEN_FLOORD)
360
2
    return 1;
361
15.3k
  if (tok->type == ISL_TOKEN_CEILD)
362
0
    return 1;
363
15.3k
  return 0;
364
15.3k
}
365
366
/* Read an integer division from "s" and return it as an isl_pw_aff.
367
 *
368
 * The integer division can be of the form
369
 *
370
 *  [<affine expression>]
371
 *  floor(<affine expression>)
372
 *  ceil(<affine expression>)
373
 *  floord(<affine expression>,<denominator>)
374
 *  ceild(<affine expression>,<denominator>)
375
 */
376
static __isl_give isl_pw_aff *accept_div(__isl_keep isl_stream *s,
377
  __isl_take isl_space *dim, struct vars *v)
378
353
{
379
353
  struct isl_token *tok;
380
353
  int f = 0;
381
353
  int c = 0;
382
353
  int extra = 0;
383
353
  isl_pw_aff *pwaff = NULL;
384
353
385
353
  if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOORD))
386
1
    extra = f = 1;
387
352
  else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEILD))
388
0
    extra = c = 1;
389
352
  else if (isl_stream_eat_if_available(s, ISL_TOKEN_FLOOR))
390
193
    f = 1;
391
159
  else if (isl_stream_eat_if_available(s, ISL_TOKEN_CEIL))
392
0
    c = 1;
393
353
  if (f || 
c159
) {
394
194
    if (isl_stream_eat(s, '('))
395
0
      goto error;
396
159
  } else {
397
159
    if (isl_stream_eat(s, '['))
398
0
      goto error;
399
353
  }
400
353
401
353
  pwaff = accept_affine(s, isl_space_copy(dim), v);
402
353
403
353
  if (extra) {
404
1
    if (isl_stream_eat(s, ','))
405
0
      goto error;
406
1
407
1
    tok = next_token(s);
408
1
    if (!tok)
409
0
      goto error;
410
1
    if (tok->type != ISL_TOKEN_VALUE) {
411
0
      isl_stream_error(s, tok, "expected denominator");
412
0
      isl_stream_push_token(s, tok);
413
0
      goto error;
414
0
    }
415
1
    pwaff = isl_pw_aff_scale_down(pwaff,  tok->u.v);
416
1
    isl_token_free(tok);
417
1
  }
418
353
419
353
  if (c)
420
0
    pwaff = isl_pw_aff_ceil(pwaff);
421
353
  else
422
353
    pwaff = isl_pw_aff_floor(pwaff);
423
353
424
353
  if (f || 
c159
) {
425
194
    if (isl_stream_eat(s, ')'))
426
0
      goto error;
427
159
  } else {
428
159
    if (isl_stream_eat(s, ']'))
429
0
      goto error;
430
353
  }
431
353
432
353
  isl_space_free(dim);
433
353
  return pwaff;
434
0
error:
435
0
  isl_space_free(dim);
436
0
  isl_pw_aff_free(pwaff);
437
0
  return NULL;
438
353
}
439
440
static __isl_give isl_pw_aff *accept_affine_factor(__isl_keep isl_stream *s,
441
  __isl_take isl_space *dim, struct vars *v)
442
9.70k
{
443
9.70k
  struct isl_token *tok = NULL;
444
9.70k
  isl_pw_aff *res = NULL;
445
9.70k
446
9.70k
  tok = next_token(s);
447
9.70k
  if (!tok) {
448
0
    isl_stream_error(s, NULL, "unexpected EOF");
449
0
    goto error;
450
0
  }
451
9.70k
452
9.70k
  if (tok->type == ISL_TOKEN_AFF) {
453
278
    res = isl_pw_aff_copy(tok->u.pwaff);
454
278
    isl_token_free(tok);
455
9.42k
  } else if (tok->type == ISL_TOKEN_IDENT) {
456
8.84k
    int n = v->n;
457
8.84k
    int pos = vars_pos(v, tok->u.s, -1);
458
8.84k
    isl_aff *aff;
459
8.84k
460
8.84k
    if (pos < 0)
461
0
      goto error;
462
8.84k
    if (pos >= n) {
463
0
      vars_drop(v, v->n - n);
464
0
      isl_stream_error(s, tok, "unknown identifier");
465
0
      goto error;
466
0
    }
467
8.84k
468
8.84k
    aff = isl_aff_zero_on_domain(isl_local_space_from_space(isl_space_copy(dim)));
469
8.84k
    if (!aff)
470
0
      goto error;
471
8.84k
    isl_int_set_si(aff->v->el[2 + pos], 1);
472
8.84k
    res = isl_pw_aff_from_aff(aff);
473
8.84k
    isl_token_free(tok);
474
8.84k
  } else 
if (588
tok->type == ISL_TOKEN_VALUE588
) {
475
0
    if (isl_stream_eat_if_available(s, '*')) {
476
0
      res = accept_affine_factor(s, isl_space_copy(dim), v);
477
0
      res = isl_pw_aff_scale(res, tok->u.v);
478
0
    } else {
479
0
      isl_local_space *ls;
480
0
      isl_aff *aff;
481
0
      ls = isl_local_space_from_space(isl_space_copy(dim));
482
0
      aff = isl_aff_zero_on_domain(ls);
483
0
      aff = isl_aff_add_constant(aff, tok->u.v);
484
0
      res = isl_pw_aff_from_aff(aff);
485
0
    }
486
0
    isl_token_free(tok);
487
588
  } else if (tok->type == '(') {
488
258
    isl_token_free(tok);
489
258
    tok = NULL;
490
258
    res = accept_affine(s, isl_space_copy(dim), v);
491
258
    if (!res)
492
0
      goto error;
493
258
    if (isl_stream_eat(s, ')'))
494
0
      goto error;
495
330
  } else if (is_start_of_div(tok)) {
496
324
    isl_stream_push_token(s, tok);
497
324
    tok = NULL;
498
324
    res = accept_div(s, isl_space_copy(dim), v);
499
324
  } else 
if (6
tok->type == ISL_TOKEN_MIN6
||
tok->type == ISL_TOKEN_MAX1
) {
500
6
    isl_stream_push_token(s, tok);
501
6
    tok = NULL;
502
6
    res = accept_minmax(s, isl_space_copy(dim), v);
503
6
  } else {
504
0
    isl_stream_error(s, tok, "expecting factor");
505
0
    goto error;
506
0
  }
507
9.70k
  if (isl_stream_eat_if_available(s, '%') ||
508
9.70k
      
isl_stream_eat_if_available(s, ISL_TOKEN_MOD)9.66k
) {
509
120
    isl_space_free(dim);
510
120
    return affine_mod(s, v, res);
511
120
  }
512
9.58k
  if (isl_stream_eat_if_available(s, '*')) {
513
7
    isl_int f;
514
7
    isl_int_init(f);
515
7
    isl_int_set_si(f, 1);
516
7
    if (accept_cst_factor(s, &f) < 0) {
517
0
      isl_int_clear(f);
518
0
      goto error2;
519
0
    }
520
7
    res = isl_pw_aff_scale(res, f);
521
7
    isl_int_clear(f);
522
7
  }
523
9.58k
  if (isl_stream_eat_if_available(s, '/')) {
524
374
    isl_int f;
525
374
    isl_int_init(f);
526
374
    isl_int_set_si(f, 1);
527
374
    if (accept_cst_factor(s, &f) < 0) {
528
0
      isl_int_clear(f);
529
0
      goto error2;
530
0
    }
531
374
    res = isl_pw_aff_scale_down(res, f);
532
374
    isl_int_clear(f);
533
374
  }
534
9.58k
535
9.58k
  isl_space_free(dim);
536
9.58k
  return res;
537
0
error:
538
0
  isl_token_free(tok);
539
0
error2:
540
0
  isl_pw_aff_free(res);
541
0
  isl_space_free(dim);
542
0
  return NULL;
543
0
}
544
545
static __isl_give isl_pw_aff *add_cst(__isl_take isl_pw_aff *pwaff, isl_int v)
546
6.04k
{
547
6.04k
  isl_aff *aff;
548
6.04k
  isl_space *space;
549
6.04k
550
6.04k
  space = isl_pw_aff_get_domain_space(pwaff);
551
6.04k
  aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
552
6.04k
  aff = isl_aff_add_constant(aff, v);
553
6.04k
554
6.04k
  return isl_pw_aff_add(pwaff, isl_pw_aff_from_aff(aff));
555
6.04k
}
556
557
/* Return a piecewise affine expression defined on the specified domain
558
 * that represents NaN.
559
 */
560
static __isl_give isl_pw_aff *nan_on_domain(__isl_keep isl_space *space)
561
30
{
562
30
  isl_local_space *ls;
563
30
564
30
  ls = isl_local_space_from_space(isl_space_copy(space));
565
30
  return isl_pw_aff_nan_on_domain(ls);
566
30
}
567
568
static __isl_give isl_pw_aff *accept_affine(__isl_keep isl_stream *s,
569
  __isl_take isl_space *space, struct vars *v)
570
13.6k
{
571
13.6k
  struct isl_token *tok = NULL;
572
13.6k
  isl_local_space *ls;
573
13.6k
  isl_pw_aff *res;
574
13.6k
  int sign = 1;
575
13.6k
576
13.6k
  ls = isl_local_space_from_space(isl_space_copy(space));
577
13.6k
  res = isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls));
578
13.6k
  if (!res)
579
0
    goto error;
580
13.6k
581
15.9k
  
for (;;)13.6k
{
582
15.9k
    tok = next_token(s);
583
15.9k
    if (!tok) {
584
0
      isl_stream_error(s, NULL, "unexpected EOF");
585
0
      goto error;
586
0
    }
587
15.9k
    if (tok->type == '-') {
588
113
      sign = -sign;
589
113
      isl_token_free(tok);
590
113
      continue;
591
113
    }
592
15.7k
    if (tok->type == '(' || 
is_start_of_div(tok)15.5k
||
593
15.7k
        
tok->type == ISL_TOKEN_MIN15.3k
||
tok->type == ISL_TOKEN_MAX15.3k
||
594
15.7k
        
tok->type == ISL_TOKEN_IDENT15.3k
||
595
15.7k
        
tok->type == ISL_TOKEN_AFF7.72k
) {
596
8.33k
      isl_pw_aff *term;
597
8.33k
      isl_stream_push_token(s, tok);
598
8.33k
      tok = NULL;
599
8.33k
      term = accept_affine_factor(s,
600
8.33k
                isl_space_copy(space), v);
601
8.33k
      if (sign < 0)
602
458
        res = isl_pw_aff_sub(res, term);
603
7.88k
      else
604
7.88k
        res = isl_pw_aff_add(res, term);
605
8.33k
      if (!res)
606
0
        goto error;
607
8.33k
      sign = 1;
608
8.33k
    } else 
if (7.44k
tok->type == ISL_TOKEN_VALUE7.44k
) {
609
7.41k
      if (sign < 0)
610
7.41k
        
isl_int_neg246
(tok->u.v, tok->u.v);
611
7.41k
      if (isl_stream_eat_if_available(s, '*') ||
612
7.41k
          
isl_stream_next_token_is(s, ISL_TOKEN_IDENT)7.29k
) {
613
1.36k
        isl_pw_aff *term;
614
1.36k
        term = accept_affine_factor(s,
615
1.36k
                isl_space_copy(space), v);
616
1.36k
        term = isl_pw_aff_scale(term, tok->u.v);
617
1.36k
        res = isl_pw_aff_add(res, term);
618
1.36k
        if (!res)
619
0
          goto error;
620
6.04k
      } else {
621
6.04k
        res = add_cst(res, tok->u.v);
622
6.04k
      }
623
7.41k
      sign = 1;
624
7.41k
    } else 
if (31
tok->type == ISL_TOKEN_NAN31
) {
625
30
      res = isl_pw_aff_add(res, nan_on_domain(space));
626
30
    } else {
627
1
      isl_stream_error(s, tok, "unexpected isl_token");
628
1
      isl_stream_push_token(s, tok);
629
1
      isl_pw_aff_free(res);
630
1
      isl_space_free(space);
631
1
      return NULL;
632
1
    }
633
15.7k
    isl_token_free(tok);
634
15.7k
635
15.7k
    tok = next_token(s);
636
15.7k
    if (tok && tok->type == '-') {
637
591
      sign = -sign;
638
591
      isl_token_free(tok);
639
15.1k
    } else if (tok && tok->type == '+') {
640
1.54k
      /* nothing */
641
1.54k
      isl_token_free(tok);
642
13.6k
    } else if (tok && tok->type == ISL_TOKEN_VALUE &&
643
13.6k
         
isl_int_is_neg37
(tok->u.v)) {
644
37
      isl_stream_push_token(s, tok);
645
13.6k
    } else {
646
13.6k
      if (tok)
647
13.6k
        isl_stream_push_token(s, tok);
648
13.6k
      break;
649
13.6k
    }
650
15.7k
  }
651
13.6k
652
13.6k
  isl_space_free(space);
653
13.6k
  return res;
654
0
error:
655
0
  isl_space_free(space);
656
0
  isl_token_free(tok);
657
0
  isl_pw_aff_free(res);
658
0
  return NULL;
659
13.6k
}
660
661
/* Is "type" the type of a comparison operator between lists
662
 * of affine expressions?
663
 */
664
static int is_list_comparator_type(int type)
665
22.0k
{
666
22.0k
  switch (type) {
667
22.0k
  case ISL_TOKEN_LEX_LT:
668
18
  case ISL_TOKEN_LEX_GT:
669
18
  case ISL_TOKEN_LEX_LE:
670
18
  case ISL_TOKEN_LEX_GE:
671
18
    return 1;
672
21.9k
  default:
673
21.9k
    return 0;
674
22.0k
  }
675
22.0k
}
676
677
static int is_comparator(struct isl_token *tok)
678
12.3k
{
679
12.3k
  if (!tok)
680
0
    return 0;
681
12.3k
  if (is_list_comparator_type(tok->type))
682
6
    return 1;
683
12.3k
684
12.3k
  switch (tok->type) {
685
12.3k
  case ISL_TOKEN_LT:
686
4.79k
  case ISL_TOKEN_GT:
687
4.79k
  case ISL_TOKEN_LE:
688
4.79k
  case ISL_TOKEN_GE:
689
4.79k
  case ISL_TOKEN_NE:
690
4.79k
  case '=':
691
4.79k
    return 1;
692
7.59k
  default:
693
7.59k
    return 0;
694
12.3k
  }
695
12.3k
}
696
697
static __isl_give isl_map *read_formula(__isl_keep isl_stream *s,
698
  struct vars *v, __isl_take isl_map *map, int rational);
699
static __isl_give isl_pw_aff *accept_extended_affine(__isl_keep isl_stream *s,
700
  __isl_take isl_space *dim, struct vars *v, int rational);
701
702
/* Accept a ternary operator, given the first argument.
703
 */
704
static __isl_give isl_pw_aff *accept_ternary(__isl_keep isl_stream *s,
705
  __isl_take isl_map *cond, struct vars *v, int rational)
706
1
{
707
1
  isl_space *dim;
708
1
  isl_pw_aff *pwaff1 = NULL, *pwaff2 = NULL, *pa_cond;
709
1
710
1
  if (!cond)
711
0
    return NULL;
712
1
713
1
  if (isl_stream_eat(s, '?'))
714
0
    goto error;
715
1
716
1
  dim = isl_space_wrap(isl_map_get_space(cond));
717
1
  pwaff1 = accept_extended_affine(s, dim, v, rational);
718
1
  if (!pwaff1)
719
0
    goto error;
720
1
721
1
  if (isl_stream_eat(s, ':'))
722
0
    goto error;
723
1
724
1
  dim = isl_pw_aff_get_domain_space(pwaff1);
725
1
  pwaff2 = accept_extended_affine(s, dim, v, rational);
726
1
  if (!pwaff1)
727
0
    goto error;
728
1
729
1
  pa_cond = isl_set_indicator_function(isl_map_wrap(cond));
730
1
  return isl_pw_aff_cond(pa_cond, pwaff1, pwaff2);
731
0
error:
732
0
  isl_map_free(cond);
733
0
  isl_pw_aff_free(pwaff1);
734
0
  isl_pw_aff_free(pwaff2);
735
0
  return NULL;
736
1
}
737
738
/* Set *line and *col to those of the next token, if any.
739
 */
740
static void set_current_line_col(__isl_keep isl_stream *s, int *line, int *col)
741
6.87k
{
742
6.87k
  struct isl_token *tok;
743
6.87k
744
6.87k
  tok = isl_stream_next_token(s);
745
6.87k
  if (!tok)
746
0
    return;
747
6.87k
748
6.87k
  *line = tok->line;
749
6.87k
  *col = tok->col;
750
6.87k
  isl_stream_push_token(s, tok);
751
6.87k
}
752
753
/* Push a token encapsulating "pa" onto "s", with the given
754
 * line and column.
755
 */
756
static int push_aff(__isl_keep isl_stream *s, int line, int col,
757
  __isl_take isl_pw_aff *pa)
758
125
{
759
125
  struct isl_token *tok;
760
125
761
125
  tok = isl_token_new(s->ctx, line, col, 0);
762
125
  if (!tok)
763
0
    goto error;
764
125
  tok->type = ISL_TOKEN_AFF;
765
125
  tok->u.pwaff = pa;
766
125
  isl_stream_push_token(s, tok);
767
125
768
125
  return 0;
769
0
error:
770
0
  isl_pw_aff_free(pa);
771
0
  return -1;
772
125
}
773
774
/* Accept an affine expression that may involve ternary operators.
775
 * We first read an affine expression.
776
 * If it is not followed by a comparison operator, we simply return it.
777
 * Otherwise, we assume the affine expression is part of the first
778
 * argument of a ternary operator and try to parse that.
779
 */
780
static __isl_give isl_pw_aff *accept_extended_affine(__isl_keep isl_stream *s,
781
  __isl_take isl_space *dim, struct vars *v, int rational)
782
3.50k
{
783
3.50k
  isl_space *space;
784
3.50k
  isl_map *cond;
785
3.50k
  isl_pw_aff *pwaff;
786
3.50k
  struct isl_token *tok;
787
3.50k
  int line = -1, col = -1;
788
3.50k
  int is_comp;
789
3.50k
790
3.50k
  set_current_line_col(s, &line, &col);
791
3.50k
792
3.50k
  pwaff = accept_affine(s, dim, v);
793
3.50k
  if (rational)
794
4
    pwaff = isl_pw_aff_set_rational(pwaff);
795
3.50k
  if (!pwaff)
796
0
    return NULL;
797
3.50k
798
3.50k
  tok = isl_stream_next_token(s);
799
3.50k
  if (!tok)
800
0
    return isl_pw_aff_free(pwaff);
801
3.50k
802
3.50k
  is_comp = is_comparator(tok);
803
3.50k
  isl_stream_push_token(s, tok);
804
3.50k
  if (!is_comp)
805
3.50k
    return pwaff;
806
1
807
1
  space = isl_pw_aff_get_domain_space(pwaff);
808
1
  cond = isl_map_universe(isl_space_unwrap(space));
809
1
810
1
  if (push_aff(s, line, col, pwaff) < 0)
811
0
    cond = isl_map_free(cond);
812
1
  if (!cond)
813
0
    return NULL;
814
1
815
1
  cond = read_formula(s, v, cond, rational);
816
1
817
1
  return accept_ternary(s, cond, v, rational);
818
1
}
819
820
static __isl_give isl_map *read_var_def(__isl_keep isl_stream *s,
821
  __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
822
  int rational)
823
138
{
824
138
  isl_pw_aff *def;
825
138
  int pos;
826
138
  isl_map *def_map;
827
138
828
138
  if (type == isl_dim_param)
829
0
    pos = isl_map_dim(map, isl_dim_param);
830
138
  else {
831
138
    pos = isl_map_dim(map, isl_dim_in);
832
138
    if (type == isl_dim_out)
833
138
      pos += isl_map_dim(map, isl_dim_out);
834
138
    type = isl_dim_in;
835
138
  }
836
138
  --pos;
837
138
838
138
  def = accept_extended_affine(s, isl_space_wrap(isl_map_get_space(map)),
839
138
          v, rational);
840
138
  def_map = isl_map_from_pw_aff(def);
841
138
  def_map = isl_map_equate(def_map, type, pos, isl_dim_out, 0);
842
138
  def_map = isl_set_unwrap(isl_map_domain(def_map));
843
138
844
138
  map = isl_map_intersect(map, def_map);
845
138
846
138
  return map;
847
138
}
848
849
static __isl_give isl_pw_aff_list *accept_affine_list(__isl_keep isl_stream *s,
850
  __isl_take isl_space *dim, struct vars *v)
851
8.89k
{
852
8.89k
  isl_pw_aff *pwaff;
853
8.89k
  isl_pw_aff_list *list;
854
8.89k
  struct isl_token *tok = NULL;
855
8.89k
856
8.89k
  pwaff = accept_affine(s, isl_space_copy(dim), v);
857
8.89k
  list = isl_pw_aff_list_from_pw_aff(pwaff);
858
8.89k
  if (!list)
859
1
    goto error;
860
8.89k
861
9.04k
  
for (;;)8.89k
{
862
9.04k
    tok = isl_stream_next_token(s);
863
9.04k
    if (!tok) {
864
0
      isl_stream_error(s, NULL, "unexpected EOF");
865
0
      goto error;
866
0
    }
867
9.04k
    if (tok->type != ',') {
868
8.89k
      isl_stream_push_token(s, tok);
869
8.89k
      break;
870
8.89k
    }
871
152
    isl_token_free(tok);
872
152
873
152
    pwaff = accept_affine(s, isl_space_copy(dim), v);
874
152
    list = isl_pw_aff_list_concat(list,
875
152
        isl_pw_aff_list_from_pw_aff(pwaff));
876
152
    if (!list)
877
0
      goto error;
878
152
  }
879
8.89k
880
8.89k
  isl_space_free(dim);
881
8.89k
  return list;
882
1
error:
883
1
  isl_space_free(dim);
884
1
  isl_pw_aff_list_free(list);
885
1
  return NULL;
886
8.89k
}
887
888
static __isl_give isl_map *read_defined_var_list(__isl_keep isl_stream *s,
889
  struct vars *v, __isl_take isl_map *map, int rational)
890
137
{
891
137
  struct isl_token *tok;
892
137
893
230
  while ((tok = isl_stream_next_token(s)) != NULL) {
894
230
    int p;
895
230
    int n = v->n;
896
230
897
230
    if (tok->type != ISL_TOKEN_IDENT)
898
0
      break;
899
230
900
230
    p = vars_pos(v, tok->u.s, -1);
901
230
    if (p < 0)
902
0
      goto error;
903
230
    if (p < n) {
904
0
      isl_stream_error(s, tok, "expecting unique identifier");
905
0
      goto error;
906
0
    }
907
230
908
230
    map = isl_map_add_dims(map, isl_dim_out, 1);
909
230
910
230
    isl_token_free(tok);
911
230
    tok = isl_stream_next_token(s);
912
230
    if (tok && tok->type == '=') {
913
138
      isl_token_free(tok);
914
138
      map = read_var_def(s, map, isl_dim_out, v, rational);
915
138
      tok = isl_stream_next_token(s);
916
138
    }
917
230
918
230
    if (!tok || tok->type != ',')
919
137
      break;
920
93
921
93
    isl_token_free(tok);
922
93
  }
923
137
  if (tok)
924
137
    isl_stream_push_token(s, tok);
925
137
926
137
  return map;
927
0
error:
928
0
  isl_token_free(tok);
929
0
  isl_map_free(map);
930
0
  return NULL;
931
137
}
932
933
static int next_is_tuple(__isl_keep isl_stream *s)
934
12.4k
{
935
12.4k
  struct isl_token *tok;
936
12.4k
  int is_tuple;
937
12.4k
938
12.4k
  tok = isl_stream_next_token(s);
939
12.4k
  if (!tok)
940
0
    return 0;
941
12.4k
  if (tok->type == '[') {
942
2.16k
    isl_stream_push_token(s, tok);
943
2.16k
    return 1;
944
2.16k
  }
945
10.3k
  if (tok->type != ISL_TOKEN_IDENT && 
!tok->is_keyword3.07k
) {
946
3.03k
    isl_stream_push_token(s, tok);
947
3.03k
    return 0;
948
3.03k
  }
949
7.29k
950
7.29k
  is_tuple = isl_stream_next_token_is(s, '[');
951
7.29k
952
7.29k
  isl_stream_push_token(s, tok);
953
7.29k
954
7.29k
  return is_tuple;
955
7.29k
}
956
957
/* Is "pa" an expression in term of earlier dimensions?
958
 * The alternative is that the dimension is defined to be equal to itself,
959
 * meaning that it has a universe domain and an expression that depends
960
 * on itself.  "i" is the position of the expression in a sequence
961
 * of "n" expressions.  The final dimensions of "pa" correspond to
962
 * these "n" expressions.
963
 */
964
static int pw_aff_is_expr(__isl_keep isl_pw_aff *pa, int i, int n)
965
136
{
966
136
  isl_aff *aff;
967
136
968
136
  if (!pa)
969
0
    return -1;
970
136
  if (pa->n != 1)
971
0
    return 1;
972
136
  if (!isl_set_plain_is_universe(pa->p[0].set))
973
0
    return 1;
974
136
975
136
  aff = pa->p[0].aff;
976
136
  if (isl_int_is_zero(aff->v->el[aff->v->size - n + i]))
977
136
    
return 10
;
978
136
  return 0;
979
136
}
980
981
/* Does the tuple contain any dimensions that are defined
982
 * in terms of earlier dimensions?
983
 */
984
static int tuple_has_expr(__isl_keep isl_multi_pw_aff *tuple)
985
122
{
986
122
  int i, n;
987
122
  int has_expr = 0;
988
122
  isl_pw_aff *pa;
989
122
990
122
  if (!tuple)
991
0
    return -1;
992
122
  n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
993
258
  for (i = 0; i < n; 
++i136
) {
994
136
    pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
995
136
    has_expr = pw_aff_is_expr(pa, i, n);
996
136
    isl_pw_aff_free(pa);
997
136
    if (has_expr < 0 || has_expr)
998
0
      break;
999
136
  }
1000
122
1001
122
  return has_expr;
1002
122
}
1003
1004
/* Set the name of dimension "pos" in "space" to "name".
1005
 * During printing, we add primes if the same name appears more than once
1006
 * to distinguish the occurrences.  Here, we remove those primes from "name"
1007
 * before setting the name of the dimension.
1008
 */
1009
static __isl_give isl_space *space_set_dim_name(__isl_take isl_space *space,
1010
  int pos, char *name)
1011
5.39k
{
1012
5.39k
  char *prime;
1013
5.39k
1014
5.39k
  if (!name)
1015
0
    return space;
1016
5.39k
1017
5.39k
  prime = strchr(name, '\'');
1018
5.39k
  if (prime)
1019
82
    *prime = '\0';
1020
5.39k
  space = isl_space_set_dim_name(space, isl_dim_out, pos, name);
1021
5.39k
  if (prime)
1022
82
    *prime = '\'';
1023
5.39k
1024
5.39k
  return space;
1025
5.39k
}
1026
1027
/* Accept a piecewise affine expression.
1028
 *
1029
 * At the outer level, the piecewise affine expression may be of the form
1030
 *
1031
 *  aff1 : condition1; aff2 : conditions2; ...
1032
 *
1033
 * or simply
1034
 *
1035
 *  aff
1036
 *
1037
 * each of the affine expressions may in turn include ternary operators.
1038
 *
1039
 * There may be parentheses around some subexpression of "aff1"
1040
 * around "aff1" itself, around "aff1 : condition1" and/or
1041
 * around the entire piecewise affine expression.
1042
 * We therefore remove the opening parenthesis (if any) from the stream
1043
 * in case the closing parenthesis follows the colon, but if the closing
1044
 * parenthesis is the first thing in the stream after the parsed affine
1045
 * expression, we push the parsed expression onto the stream and parse
1046
 * again in case the parentheses enclose some subexpression of "aff1".
1047
 */
1048
static __isl_give isl_pw_aff *accept_piecewise_affine(__isl_keep isl_stream *s,
1049
  __isl_take isl_space *space, struct vars *v, int rational)
1050
3.36k
{
1051
3.36k
  isl_pw_aff *res;
1052
3.36k
  isl_space *res_space;
1053
3.36k
1054
3.36k
  res_space = isl_space_from_domain(isl_space_copy(space));
1055
3.36k
  res_space = isl_space_add_dims(res_space, isl_dim_out, 1);
1056
3.36k
  res = isl_pw_aff_empty(res_space);
1057
3.36k
  do {
1058
3.36k
    isl_pw_aff *pa;
1059
3.36k
    int seen_paren;
1060
3.36k
    int line = -1, col = -1;
1061
3.36k
1062
3.36k
    set_current_line_col(s, &line, &col);
1063
3.36k
    seen_paren = isl_stream_eat_if_available(s, '(');
1064
3.36k
    if (seen_paren)
1065
124
      pa = accept_piecewise_affine(s, isl_space_copy(space),
1066
124
              v, rational);
1067
3.24k
    else
1068
3.24k
      pa = accept_extended_affine(s, isl_space_copy(space),
1069
3.24k
              v, rational);
1070
3.36k
    if (seen_paren && 
isl_stream_eat_if_available(s, ')')124
) {
1071
124
      seen_paren = 0;
1072
124
      if (push_aff(s, line, col, pa) < 0)
1073
0
        goto error;
1074
124
      pa = accept_extended_affine(s, isl_space_copy(space),
1075
124
              v, rational);
1076
124
    }
1077
3.36k
    if (isl_stream_eat_if_available(s, ':')) {
1078
81
      isl_space *dom_space;
1079
81
      isl_set *dom;
1080
81
1081
81
      dom_space = isl_pw_aff_get_domain_space(pa);
1082
81
      dom = isl_set_universe(dom_space);
1083
81
      dom = read_formula(s, v, dom, rational);
1084
81
      pa = isl_pw_aff_intersect_domain(pa, dom);
1085
81
    }
1086
3.36k
1087
3.36k
    res = isl_pw_aff_union_add(res, pa);
1088
3.36k
1089
3.36k
    if (seen_paren && 
isl_stream_eat(s, ')')0
)
1090
0
      goto error;
1091
3.36k
  } while (isl_stream_eat_if_available(s, ';'));
1092
3.36k
1093
3.36k
  isl_space_free(space);
1094
3.36k
1095
3.36k
  return res;
1096
0
error:
1097
0
  isl_space_free(space);
1098
0
  return isl_pw_aff_free(res);
1099
3.36k
}
1100
1101
/* Read an affine expression from "s" for use in read_tuple.
1102
 *
1103
 * accept_extended_affine requires a wrapped space as input.
1104
 * read_tuple on the other hand expects each isl_pw_aff
1105
 * to have an anonymous space.  We therefore adjust the space
1106
 * of the isl_pw_aff before returning it.
1107
 */
1108
static __isl_give isl_pw_aff *read_tuple_var_def(__isl_keep isl_stream *s,
1109
  struct vars *v, int rational)
1110
3.23k
{
1111
3.23k
  isl_space *space;
1112
3.23k
  isl_pw_aff *def;
1113
3.23k
1114
3.23k
  space = isl_space_wrap(isl_space_alloc(s->ctx, 0, v->n, 0));
1115
3.23k
1116
3.23k
  def = accept_piecewise_affine(s, space, v, rational);
1117
3.23k
1118
3.23k
  space = isl_space_set_alloc(s->ctx, 0, v->n);
1119
3.23k
  def = isl_pw_aff_reset_domain_space(def, space);
1120
3.23k
1121
3.23k
  return def;
1122
3.23k
}
1123
1124
/* Read a list of tuple elements by calling "read_el" on each of them and
1125
 * return a space with the same number of set dimensions derived from
1126
 * the parameter space "space" and possibly updated by "read_el".
1127
 * The elements in the list are separated by either "," or "][".
1128
 * If "comma" is set then only "," is allowed.
1129
 */
1130
static __isl_give isl_space *read_tuple_list(__isl_keep isl_stream *s,
1131
  struct vars *v, __isl_take isl_space *space, int rational, int comma,
1132
  __isl_give isl_space *(*read_el)(__isl_keep isl_stream *s,
1133
    struct vars *v, __isl_take isl_space *space, int rational,
1134
    void *user),
1135
  void *user)
1136
6.90k
{
1137
6.90k
  if (!space)
1138
0
    return NULL;
1139
6.90k
1140
6.90k
  space = isl_space_set_from_params(space);
1141
6.90k
1142
6.90k
  if (isl_stream_next_token_is(s, ']'))
1143
1.31k
    return space;
1144
5.59k
1145
8.78k
  
for (;;)5.59k
{
1146
8.78k
    struct isl_token *tok;
1147
8.78k
1148
8.78k
    space = isl_space_add_dims(space, isl_dim_set, 1);
1149
8.78k
1150
8.78k
    space = read_el(s, v, space, rational, user);
1151
8.78k
    if (!space)
1152
0
      return NULL;
1153
8.78k
1154
8.78k
    tok = isl_stream_next_token(s);
1155
8.78k
    if (!comma && 
tok8.78k
&&
tok->type == ']'8.78k
&&
1156
8.78k
        
isl_stream_next_token_is(s, '[')5.59k
) {
1157
0
      isl_token_free(tok);
1158
0
      tok = isl_stream_next_token(s);
1159
8.78k
    } else if (!tok || tok->type != ',') {
1160
5.59k
      if (tok)
1161
5.59k
        isl_stream_push_token(s, tok);
1162
5.59k
      break;
1163
5.59k
    }
1164
3.19k
1165
3.19k
    isl_token_free(tok);
1166
3.19k
  }
1167
5.59k
1168
5.59k
  return space;
1169
5.59k
}
1170
1171
/* Read a tuple space from "s" derived from the parameter space "space".
1172
 * Call "read_el" on each element in the tuples.
1173
 */
1174
static __isl_give isl_space *read_tuple_space(__isl_keep isl_stream *s,
1175
  struct vars *v, __isl_take isl_space *space, int rational, int comma,
1176
  __isl_give isl_space *(*read_el)(__isl_keep isl_stream *s,
1177
    struct vars *v, __isl_take isl_space *space, int rational,
1178
    void *user),
1179
  void *user)
1180
7.18k
{
1181
7.18k
  struct isl_token *tok;
1182
7.18k
  char *name = NULL;
1183
7.18k
  isl_space *res = NULL;
1184
7.18k
1185
7.18k
  tok = isl_stream_next_token(s);
1186
7.18k
  if (!tok)
1187
0
    goto error;
1188
7.18k
  if (tok->type == ISL_TOKEN_IDENT || 
tok->is_keyword3.32k
) {
1189
3.85k
    name = strdup(tok->u.s);
1190
3.85k
    isl_token_free(tok);
1191
3.85k
    if (!name)
1192
0
      goto error;
1193
3.32k
  } else
1194
3.32k
    isl_stream_push_token(s, tok);
1195
7.18k
  if (isl_stream_eat(s, '['))
1196
0
    goto error;
1197
7.18k
  if (next_is_tuple(s)) {
1198
274
    isl_space *out;
1199
274
    res = read_tuple_space(s, v, isl_space_copy(space),
1200
274
          rational, comma, read_el, user);
1201
274
    if (isl_stream_eat(s, ISL_TOKEN_TO))
1202
0
      goto error;
1203
274
    out = read_tuple_space(s, v, isl_space_copy(space),
1204
274
          rational, comma, read_el, user);
1205
274
    res = isl_space_product(res, out);
1206
274
  } else
1207
6.90k
    res = read_tuple_list(s, v, isl_space_copy(space),
1208
6.90k
          rational, comma, read_el, user);
1209
7.18k
  if (isl_stream_eat(s, ']'))
1210
2
    goto error;
1211
7.17k
1212
7.17k
  if (name) {
1213
3.85k
    res = isl_space_set_tuple_name(res, isl_dim_set, name);
1214
3.85k
    free(name);
1215
3.85k
  }
1216
7.17k
1217
7.17k
  isl_space_free(space);
1218
7.17k
  return res;
1219
2
error:
1220
2
  free(name);
1221
2
  isl_space_free(res);
1222
2
  isl_space_free(space);
1223
2
  return NULL;
1224
7.17k
}
1225
1226
/* Construct an isl_pw_aff defined on a space with v->n variables
1227
 * that is equal to the last of those variables.
1228
 */
1229
static __isl_give isl_pw_aff *identity_tuple_el(struct vars *v)
1230
5.38k
{
1231
5.38k
  isl_space *space;
1232
5.38k
  isl_aff *aff;
1233
5.38k
1234
5.38k
  space = isl_space_set_alloc(v->ctx, 0, v->n);
1235
5.38k
  aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1236
5.38k
  aff = isl_aff_add_coefficient_si(aff, isl_dim_in, v->n - 1, 1);
1237
5.38k
  return isl_pw_aff_from_aff(aff);
1238
5.38k
}
1239
1240
/* This function is called for each element in a tuple inside read_tuple.
1241
 * Add a new variable to "v" and construct a corresponding isl_pw_aff defined
1242
 * over a space containing all variables in "v" defined so far.
1243
 * The isl_pw_aff expresses the new variable in terms of earlier variables
1244
 * if a definition is provided.  Otherwise, it is represented as being
1245
 * equal to itself.
1246
 * Add the isl_pw_aff to *list.
1247
 * If the new variable was named, then adjust "space" accordingly and
1248
 * return the updated space.
1249
 */
1250
static __isl_give isl_space *read_tuple_pw_aff_el(__isl_keep isl_stream *s,
1251
  struct vars *v, __isl_take isl_space *space, int rational, void *user)
1252
8.62k
{
1253
8.62k
  isl_pw_aff_list **list = (isl_pw_aff_list **) user;
1254
8.62k
  isl_pw_aff *pa;
1255
8.62k
  struct isl_token *tok;
1256
8.62k
  int new_name = 0;
1257
8.62k
1258
8.62k
  tok = next_token(s);
1259
8.62k
  if (!tok) {
1260
0
    isl_stream_error(s, NULL, "unexpected EOF");
1261
0
    return isl_space_free(space);
1262
0
  }
1263
8.62k
1264
8.62k
  if (tok->type == ISL_TOKEN_IDENT) {
1265
6.63k
    int n = v->n;
1266
6.63k
    int p = vars_pos(v, tok->u.s, -1);
1267
6.63k
    if (p < 0)
1268
0
      goto error;
1269
6.63k
    new_name = p >= n;
1270
6.63k
  }
1271
8.62k
1272
8.62k
  if (tok->type == '*') {
1273
1
    if (vars_add_anon(v) < 0)
1274
0
      goto error;
1275
1
    isl_token_free(tok);
1276
1
    pa = identity_tuple_el(v);
1277
8.62k
  } else if (new_name) {
1278
5.39k
    int pos = isl_space_dim(space, isl_dim_out) - 1;
1279
5.39k
    space = space_set_dim_name(space, pos, v->v->name);
1280
5.39k
    isl_token_free(tok);
1281
5.39k
    if (isl_stream_eat_if_available(s, '='))
1282
10
      pa = read_tuple_var_def(s, v, rational);
1283
5.38k
    else
1284
5.38k
      pa = identity_tuple_el(v);
1285
5.39k
  } else {
1286
3.22k
    isl_stream_push_token(s, tok);
1287
3.22k
    tok = NULL;
1288
3.22k
    if (vars_add_anon(v) < 0)
1289
0
      goto error;
1290
3.22k
    pa = read_tuple_var_def(s, v, rational);
1291
3.22k
  }
1292
8.62k
1293
8.62k
  *list = isl_pw_aff_list_add(*list, pa);
1294
8.62k
  if (!*list)
1295
0
    return isl_space_free(space);
1296
8.62k
1297
8.62k
  return space;
1298
0
error:
1299
0
  isl_token_free(tok);
1300
0
  return isl_space_free(space);
1301
8.62k
}
1302
1303
/* Read a tuple and represent it as an isl_multi_pw_aff.
1304
 * The range space of the isl_multi_pw_aff is the space of the tuple.
1305
 * The domain space is an anonymous space
1306
 * with a dimension for each variable in the set of variables in "v",
1307
 * including the variables in the range.
1308
 * If a given dimension is not defined in terms of earlier dimensions in
1309
 * the input, then the corresponding isl_pw_aff is set equal to one time
1310
 * the variable corresponding to the dimension being defined.
1311
 *
1312
 * The elements in the tuple are collected in a list by read_tuple_pw_aff_el.
1313
 * Each element in this list is defined over a space representing
1314
 * the variables defined so far.  We need to adjust the earlier
1315
 * elements to have as many variables in the domain as the final
1316
 * element in the list.
1317
 */
1318
static __isl_give isl_multi_pw_aff *read_tuple(__isl_keep isl_stream *s,
1319
  struct vars *v, int rational, int comma)
1320
6.36k
{
1321
6.36k
  int i, n;
1322
6.36k
  isl_space *space;
1323
6.36k
  isl_pw_aff_list *list;
1324
6.36k
1325
6.36k
  space = isl_space_params_alloc(v->ctx, 0);
1326
6.36k
  list = isl_pw_aff_list_alloc(s->ctx, 0);
1327
6.36k
  space = read_tuple_space(s, v, space, rational, comma,
1328
6.36k
        &read_tuple_pw_aff_el, &list);
1329
6.36k
  n = isl_space_dim(space, isl_dim_set);
1330
9.58k
  for (i = 0; i + 1 < n; 
++i3.22k
) {
1331
3.22k
    isl_pw_aff *pa;
1332
3.22k
1333
3.22k
    pa = isl_pw_aff_list_get_pw_aff(list, i);
1334
3.22k
    pa = isl_pw_aff_add_dims(pa, isl_dim_in, n - (i + 1));
1335
3.22k
    list = isl_pw_aff_list_set_pw_aff(list, i, pa);
1336
3.22k
  }
1337
6.36k
1338
6.36k
  space = isl_space_from_range(space);
1339
6.36k
  space = isl_space_add_dims(space, isl_dim_in, v->n);
1340
6.36k
  return isl_multi_pw_aff_from_pw_aff_list(space, list);
1341
6.36k
}
1342
1343
/* Add the tuple represented by the isl_multi_pw_aff "tuple" to "map".
1344
 * We first create the appropriate space in "map" based on the range
1345
 * space of this isl_multi_pw_aff.  Then, we add equalities based
1346
 * on the affine expressions.  These live in an anonymous space,
1347
 * however, so we first need to reset the space to that of "map".
1348
 */
1349
static __isl_give isl_map *map_from_tuple(__isl_take isl_multi_pw_aff *tuple,
1350
  __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
1351
  int rational)
1352
5.90k
{
1353
5.90k
  int i, n;
1354
5.90k
  isl_ctx *ctx;
1355
5.90k
  isl_space *space = NULL;
1356
5.90k
1357
5.90k
  if (!map || !tuple)
1358
0
    goto error;
1359
5.90k
  ctx = isl_multi_pw_aff_get_ctx(tuple);
1360
5.90k
  n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
1361
5.90k
  space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
1362
5.90k
  if (!space)
1363
0
    goto error;
1364
5.90k
1365
5.90k
  if (type == isl_dim_param) {
1366
807
    if (isl_space_has_tuple_name(space, isl_dim_set) ||
1367
807
        isl_space_is_wrapping(space)) {
1368
0
      isl_die(ctx, isl_error_invalid,
1369
0
        "parameter tuples cannot be named or nested",
1370
0
        goto error);
1371
0
    }
1372
807
    map = isl_map_add_dims(map, type, n);
1373
1.82k
    for (i = 0; i < n; 
++i1.01k
) {
1374
1.01k
      isl_id *id;
1375
1.01k
      if (!isl_space_has_dim_name(space, isl_dim_set, i))
1376
1.01k
        
isl_die0
(ctx, isl_error_invalid,
1377
1.01k
          "parameters must be named",
1378
1.01k
          goto error);
1379
1.01k
      id = isl_space_get_dim_id(space, isl_dim_set, i);
1380
1.01k
      map = isl_map_set_dim_id(map, isl_dim_param, i, id);
1381
1.01k
    }
1382
5.09k
  } else if (type == isl_dim_in) {
1383
3.06k
    isl_set *set;
1384
3.06k
1385
3.06k
    set = isl_set_universe(isl_space_copy(space));
1386
3.06k
    if (rational)
1387
22
      set = isl_set_set_rational(set);
1388
3.06k
    set = isl_set_intersect_params(set, isl_map_params(map));
1389
3.06k
    map = isl_map_from_domain(set);
1390
3.06k
  } else {
1391
2.03k
    isl_set *set;
1392
2.03k
1393
2.03k
    set = isl_set_universe(isl_space_copy(space));
1394
2.03k
    if (rational)
1395
0
      set = isl_set_set_rational(set);
1396
2.03k
    map = isl_map_from_domain_and_range(isl_map_domain(map), set);
1397
2.03k
  }
1398
5.90k
1399
14.0k
  
for (i = 0; 5.90k
i < n;
++i8.12k
) {
1400
8.12k
    isl_pw_aff *pa;
1401
8.12k
    isl_space *space;
1402
8.12k
    isl_aff *aff;
1403
8.12k
    isl_set *set;
1404
8.12k
    isl_map *map_i;
1405
8.12k
1406
8.12k
    pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
1407
8.12k
    space = isl_pw_aff_get_domain_space(pa);
1408
8.12k
    aff = isl_aff_zero_on_domain(isl_local_space_from_space(space));
1409
8.12k
    aff = isl_aff_add_coefficient_si(aff,
1410
8.12k
            isl_dim_in, v->n - n + i, -1);
1411
8.12k
    pa = isl_pw_aff_add(pa, isl_pw_aff_from_aff(aff));
1412
8.12k
    if (rational)
1413
253
      pa = isl_pw_aff_set_rational(pa);
1414
8.12k
    set = isl_pw_aff_zero_set(pa);
1415
8.12k
    map_i = isl_map_from_range(set);
1416
8.12k
    map_i = isl_map_reset_space(map_i, isl_map_get_space(map));
1417
8.12k
    map = isl_map_intersect(map, map_i);
1418
8.12k
  }
1419
5.90k
1420
5.90k
  isl_space_free(space);
1421
5.90k
  isl_multi_pw_aff_free(tuple);
1422
5.90k
  return map;
1423
0
error:
1424
0
  isl_space_free(space);
1425
0
  isl_multi_pw_aff_free(tuple);
1426
0
  isl_map_free(map);
1427
0
  return NULL;
1428
5.90k
}
1429
1430
/* Read a tuple from "s" and add it to "map".
1431
 * The tuple is initially represented as an isl_multi_pw_aff and
1432
 * then added to "map".
1433
 */
1434
static __isl_give isl_map *read_map_tuple(__isl_keep isl_stream *s,
1435
  __isl_take isl_map *map, enum isl_dim_type type, struct vars *v,
1436
  int rational, int comma)
1437
5.74k
{
1438
5.74k
  isl_multi_pw_aff *tuple;
1439
5.74k
1440
5.74k
  tuple = read_tuple(s, v, rational, comma);
1441
5.74k
  if (!tuple)
1442
2
    return isl_map_free(map);
1443
5.74k
1444
5.74k
  return map_from_tuple(tuple, map, type, v, rational);
1445
5.74k
}
1446
1447
/* Given two equal-length lists of piecewise affine expression with the space
1448
 * of "set" as domain, construct a set in the same space that expresses
1449
 * that "left" and "right" satisfy the comparison "type".
1450
 *
1451
 * A space is constructed of the same dimension as the number of elements
1452
 * in the two lists.  The comparison is then expressed in a map from
1453
 * this space to itself and wrapped into a set.  Finally the two lists
1454
 * of piecewise affine expressions are plugged into this set.
1455
 *
1456
 * Let S be the space of "set" and T the constructed space.
1457
 * The lists are first changed into two isl_multi_pw_affs in S -> T and
1458
 * then combined into an isl_multi_pw_aff in S -> [T -> T],
1459
 * while the comparison is first expressed in T -> T, then [T -> T]
1460
 * and finally in S.
1461
 */
1462
static __isl_give isl_set *list_cmp(__isl_keep isl_set *set, int type,
1463
  __isl_take isl_pw_aff_list *left, __isl_take isl_pw_aff_list *right)
1464
6
{
1465
6
  isl_space *space;
1466
6
  int n;
1467
6
  isl_multi_pw_aff *mpa1, *mpa2;
1468
6
1469
6
  if (!set || !left || !right)
1470
0
    goto error;
1471
6
1472
6
  space = isl_set_get_space(set);
1473
6
  n = isl_pw_aff_list_n_pw_aff(left);
1474
6
  space = isl_space_from_domain(space);
1475
6
  space = isl_space_add_dims(space, isl_dim_out, n);
1476
6
  mpa1 = isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space), left);
1477
6
  mpa2 = isl_multi_pw_aff_from_pw_aff_list(isl_space_copy(space), right);
1478
6
  mpa1 = isl_multi_pw_aff_range_product(mpa1, mpa2);
1479
6
1480
6
  space = isl_space_range(space);
1481
6
  switch (type) {
1482
6
  case ISL_TOKEN_LEX_LT:
1483
2
    set = isl_map_wrap(isl_map_lex_lt(space));
1484
2
    break;
1485
6
  case ISL_TOKEN_LEX_GT:
1486
2
    set = isl_map_wrap(isl_map_lex_gt(space));
1487
2
    break;
1488
6
  case ISL_TOKEN_LEX_LE:
1489
1
    set = isl_map_wrap(isl_map_lex_le(space));
1490
1
    break;
1491
6
  case ISL_TOKEN_LEX_GE:
1492
1
    set = isl_map_wrap(isl_map_lex_ge(space));
1493
1
    break;
1494
6
  default:
1495
0
    isl_multi_pw_aff_free(mpa1);
1496
0
    isl_space_free(space);
1497
0
    isl_die(isl_set_get_ctx(set), isl_error_internal,
1498
6
      "unhandled list comparison type", return NULL);
1499
6
  }
1500
6
  set = isl_set_preimage_multi_pw_aff(set, mpa1);
1501
6
  return set;
1502
0
error:
1503
0
  isl_pw_aff_list_free(left);
1504
0
  isl_pw_aff_list_free(right);
1505
0
  return NULL;
1506
6
}
1507
1508
/* Construct constraints of the form
1509
 *
1510
 *  a op b
1511
 *
1512
 * where a is an element in "left", op is an operator of type "type" and
1513
 * b is an element in "right", add the constraints to "set" and return
1514
 * the result.
1515
 * "rational" is set if the constraints should be treated as
1516
 * a rational constraints.
1517
 *
1518
 * If "type" is the type of a comparison operator between lists
1519
 * of affine expressions, then a single (compound) constraint
1520
 * is constructed by list_cmp instead.
1521
 */
1522
static __isl_give isl_set *construct_constraints(
1523
  __isl_take isl_set *set, int type,
1524
  __isl_keep isl_pw_aff_list *left, __isl_keep isl_pw_aff_list *right,
1525
  int rational)
1526
4.80k
{
1527
4.80k
  isl_set *cond;
1528
4.80k
1529
4.80k
  left = isl_pw_aff_list_copy(left);
1530
4.80k
  right = isl_pw_aff_list_copy(right);
1531
4.80k
  if (rational) {
1532
24
    left = isl_pw_aff_list_set_rational(left);
1533
24
    right = isl_pw_aff_list_set_rational(right);
1534
24
  }
1535
4.80k
  if (is_list_comparator_type(type))
1536
6
    cond = list_cmp(set, type, left, right);
1537
4.79k
  else if (type == ISL_TOKEN_LE)
1538
2.37k
    cond = isl_pw_aff_list_le_set(left, right);
1539
2.42k
  else if (type == ISL_TOKEN_GE)
1540
1.35k
    cond = isl_pw_aff_list_ge_set(left, right);
1541
1.07k
  else if (type == ISL_TOKEN_LT)
1542
389
    cond = isl_pw_aff_list_lt_set(left, right);
1543
684
  else if (type == ISL_TOKEN_GT)
1544
128
    cond = isl_pw_aff_list_gt_set(left, right);
1545
556
  else if (type == ISL_TOKEN_NE)
1546
12
    cond = isl_pw_aff_list_ne_set(left, right);
1547
544
  else
1548
544
    cond = isl_pw_aff_list_eq_set(left, right);
1549
4.80k
1550
4.80k
  return isl_set_intersect(set, cond);
1551
4.80k
}
1552
1553
/* Read a constraint from "s", add it to "map" and return the result.
1554
 * "v" contains a description of the identifiers parsed so far.
1555
 * "rational" is set if the constraint should be treated as
1556
 * a rational constraint.
1557
 * The constraint read from "s" may be applied to multiple pairs
1558
 * of affine expressions and may be chained.
1559
 * In particular, a list of affine expressions is read, followed
1560
 * by a comparison operator and another list of affine expressions.
1561
 * The comparison operator is then applied to each pair of elements
1562
 * in the two lists and the results are added to "map".
1563
 * However, if the operator expects two lists of affine expressions,
1564
 * then it is applied directly to those lists and the two lists
1565
 * are required to have the same length.
1566
 * If the next token is another comparison operator, then another
1567
 * list of affine expressions is read and the process repeats.
1568
 *
1569
 * The processing is performed on a wrapped copy of "map" because
1570
 * an affine expression cannot have a binary relation as domain.
1571
 */
1572
static __isl_give isl_map *add_constraint(__isl_keep isl_stream *s,
1573
  struct vars *v, __isl_take isl_map *map, int rational)
1574
4.08k
{
1575
4.08k
  struct isl_token *tok;
1576
4.08k
  int type;
1577
4.08k
  isl_pw_aff_list *list1 = NULL, *list2 = NULL;
1578
4.08k
  int n1, n2;
1579
4.08k
  isl_set *set;
1580
4.08k
1581
4.08k
  set = isl_map_wrap(map);
1582
4.08k
  list1 = accept_affine_list(s, isl_set_get_space(set), v);
1583
4.08k
  if (!list1)
1584
1
    goto error;
1585
4.08k
  tok = isl_stream_next_token(s);
1586
4.08k
  if (!is_comparator(tok)) {
1587
0
    isl_stream_error(s, tok, "missing operator");
1588
0
    if (tok)
1589
0
      isl_stream_push_token(s, tok);
1590
0
    goto error;
1591
0
  }
1592
4.08k
  type = tok->type;
1593
4.08k
  isl_token_free(tok);
1594
4.80k
  for (;;) {
1595
4.80k
    list2 = accept_affine_list(s, isl_set_get_space(set), v);
1596
4.80k
    if (!list2)
1597
0
      goto error;
1598
4.80k
    n1 = isl_pw_aff_list_n_pw_aff(list1);
1599
4.80k
    n2 = isl_pw_aff_list_n_pw_aff(list2);
1600
4.80k
    if (is_list_comparator_type(type) && 
n1 != n26
) {
1601
0
      isl_stream_error(s, NULL,
1602
0
          "list arguments not of same size");
1603
0
      goto error;
1604
0
    }
1605
4.80k
1606
4.80k
    set = construct_constraints(set, type, list1, list2, rational);
1607
4.80k
    isl_pw_aff_list_free(list1);
1608
4.80k
    list1 = list2;
1609
4.80k
1610
4.80k
    tok = isl_stream_next_token(s);
1611
4.80k
    if (!is_comparator(tok)) {
1612
4.08k
      if (tok)
1613
4.08k
        isl_stream_push_token(s, tok);
1614
4.08k
      break;
1615
4.08k
    }
1616
719
    type = tok->type;
1617
719
    isl_token_free(tok);
1618
719
  }
1619
4.08k
  isl_pw_aff_list_free(list1);
1620
4.08k
1621
4.08k
  return isl_set_unwrap(set);
1622
1
error:
1623
1
  isl_pw_aff_list_free(list1);
1624
1
  isl_pw_aff_list_free(list2);
1625
1
  isl_set_free(set);
1626
1
  return NULL;
1627
4.08k
}
1628
1629
static __isl_give isl_map *read_exists(__isl_keep isl_stream *s,
1630
  struct vars *v, __isl_take isl_map *map, int rational)
1631
137
{
1632
137
  int n = v->n;
1633
137
  int seen_paren = isl_stream_eat_if_available(s, '(');
1634
137
1635
137
  map = isl_map_from_domain(isl_map_wrap(map));
1636
137
  map = read_defined_var_list(s, v, map, rational);
1637
137
1638
137
  if (isl_stream_eat(s, ':'))
1639
0
    goto error;
1640
137
1641
137
  map = read_formula(s, v, map, rational);
1642
137
  map = isl_set_unwrap(isl_map_domain(map));
1643
137
1644
137
  vars_drop(v, v->n - n);
1645
137
  if (seen_paren && 
isl_stream_eat(s, ')')93
)
1646
0
    goto error;
1647
137
1648
137
  return map;
1649
0
error:
1650
0
  isl_map_free(map);
1651
0
  return NULL;
1652
137
}
1653
1654
/* Parse an expression between parentheses and push the result
1655
 * back on the stream.
1656
 *
1657
 * The parsed expression may be either an affine expression
1658
 * or a condition.  The first type is pushed onto the stream
1659
 * as an isl_pw_aff, while the second is pushed as an isl_map.
1660
 *
1661
 * If the initial token indicates the start of a condition,
1662
 * we parse it as such.
1663
 * Otherwise, we first parse an affine expression and push
1664
 * that onto the stream.  If the affine expression covers the
1665
 * entire expression between parentheses, we return.
1666
 * Otherwise, we assume that the affine expression is the
1667
 * start of a condition and continue parsing.
1668
 */
1669
static int resolve_paren_expr(__isl_keep isl_stream *s,
1670
  struct vars *v, __isl_take isl_map *map, int rational)
1671
192
{
1672
192
  struct isl_token *tok, *tok2;
1673
192
  int line, col;
1674
192
  isl_pw_aff *pwaff;
1675
192
1676
192
  tok = isl_stream_next_token(s);
1677
192
  if (!tok || tok->type != '(')
1678
0
    goto error;
1679
192
1680
192
  if (isl_stream_next_token_is(s, '('))
1681
7
    if (resolve_paren_expr(s, v, isl_map_copy(map), rational))
1682
0
      goto error;
1683
192
1684
192
  if (isl_stream_next_token_is(s, ISL_TOKEN_EXISTS) ||
1685
192
      
isl_stream_next_token_is(s, ISL_TOKEN_NOT)161
||
1686
192
      
isl_stream_next_token_is(s, ISL_TOKEN_TRUE)160
||
1687
192
      
isl_stream_next_token_is(s, ISL_TOKEN_FALSE)160
||
1688
192
      
isl_stream_next_token_is(s, ISL_TOKEN_MAP)160
) {
1689
39
    map = read_formula(s, v, map, rational);
1690
39
    if (isl_stream_eat(s, ')'))
1691
0
      goto error;
1692
39
    tok->type = ISL_TOKEN_MAP;
1693
39
    tok->u.map = map;
1694
39
    isl_stream_push_token(s, tok);
1695
39
    return 0;
1696
39
  }
1697
153
1698
153
  tok2 = isl_stream_next_token(s);
1699
153
  if (!tok2)
1700
0
    goto error;
1701
153
  line = tok2->line;
1702
153
  col = tok2->col;
1703
153
  isl_stream_push_token(s, tok2);
1704
153
1705
153
  pwaff = accept_affine(s, isl_space_wrap(isl_map_get_space(map)), v);
1706
153
  if (!pwaff)
1707
0
    goto error;
1708
153
1709
153
  tok2 = isl_token_new(s->ctx, line, col, 0);
1710
153
  if (!tok2)
1711
0
    goto error2;
1712
153
  tok2->type = ISL_TOKEN_AFF;
1713
153
  tok2->u.pwaff = pwaff;
1714
153
1715
153
  if (isl_stream_eat_if_available(s, ')')) {
1716
25
    isl_stream_push_token(s, tok2);
1717
25
    isl_token_free(tok);
1718
25
    isl_map_free(map);
1719
25
    return 0;
1720
25
  }
1721
128
1722
128
  isl_stream_push_token(s, tok2);
1723
128
1724
128
  map = read_formula(s, v, map, rational);
1725
128
  if (isl_stream_eat(s, ')'))
1726
0
    goto error;
1727
128
1728
128
  tok->type = ISL_TOKEN_MAP;
1729
128
  tok->u.map = map;
1730
128
  isl_stream_push_token(s, tok);
1731
128
1732
128
  return 0;
1733
0
error2:
1734
0
  isl_pw_aff_free(pwaff);
1735
0
error:
1736
0
  isl_token_free(tok);
1737
0
  isl_map_free(map);
1738
0
  return -1;
1739
0
}
1740
1741
static __isl_give isl_map *read_conjunct(__isl_keep isl_stream *s,
1742
  struct vars *v, __isl_take isl_map *map, int rational)
1743
4.40k
{
1744
4.40k
  if (isl_stream_next_token_is(s, '('))
1745
185
    if (resolve_paren_expr(s, v, isl_map_copy(map), rational))
1746
0
      goto error;
1747
4.40k
1748
4.40k
  if (isl_stream_next_token_is(s, ISL_TOKEN_MAP)) {
1749
167
    struct isl_token *tok;
1750
167
    tok = isl_stream_next_token(s);
1751
167
    if (!tok)
1752
0
      goto error;
1753
167
    isl_map_free(map);
1754
167
    map = isl_map_copy(tok->u.map);
1755
167
    isl_token_free(tok);
1756
167
    return map;
1757
167
  }
1758
4.23k
1759
4.23k
  if (isl_stream_eat_if_available(s, ISL_TOKEN_EXISTS))
1760
137
    return read_exists(s, v, map, rational);
1761
4.09k
1762
4.09k
  if (isl_stream_eat_if_available(s, ISL_TOKEN_TRUE))
1763
1
    return map;
1764
4.09k
1765
4.09k
  if (isl_stream_eat_if_available(s, ISL_TOKEN_FALSE)) {
1766
12
    isl_space *dim = isl_map_get_space(map);
1767
12
    isl_map_free(map);
1768
12
    return isl_map_empty(dim);
1769
12
  }
1770
4.08k
    
1771
4.08k
  return add_constraint(s, v, map, rational);
1772
0
error:
1773
0
  isl_map_free(map);
1774
0
  return NULL;
1775
4.08k
}
1776
1777
static __isl_give isl_map *read_conjuncts(__isl_keep isl_stream *s,
1778
  struct vars *v, __isl_take isl_map *map, int rational)
1779
2.26k
{
1780
2.26k
  isl_map *res;
1781
2.26k
  int negate;
1782
2.26k
1783
2.26k
  negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1784
2.26k
  res = read_conjunct(s, v, isl_map_copy(map), rational);
1785
2.26k
  if (negate)
1786
1
    res = isl_map_subtract(isl_map_copy(map), res);
1787
2.26k
1788
4.40k
  while (res && 
isl_stream_eat_if_available(s, ISL_TOKEN_AND)4.40k
) {
1789
2.13k
    isl_map *res_i;
1790
2.13k
1791
2.13k
    negate = isl_stream_eat_if_available(s, ISL_TOKEN_NOT);
1792
2.13k
    res_i = read_conjunct(s, v, isl_map_copy(map), rational);
1793
2.13k
    if (negate)
1794
0
      res = isl_map_subtract(res, res_i);
1795
2.13k
    else
1796
2.13k
      res = isl_map_intersect(res, res_i);
1797
2.13k
  }
1798
2.26k
1799
2.26k
  isl_map_free(map);
1800
2.26k
  return res;
1801
2.26k
}
1802
1803
static struct isl_map *read_disjuncts(__isl_keep isl_stream *s,
1804
  struct vars *v, __isl_take isl_map *map, int rational)
1805
2.18k
{
1806
2.18k
  isl_map *res;
1807
2.18k
1808
2.18k
  if (isl_stream_next_token_is(s, '}'))
1809
72
    return map;
1810
2.10k
1811
2.10k
  res = read_conjuncts(s, v, isl_map_copy(map), rational);
1812
2.26k
  while (isl_stream_eat_if_available(s, ISL_TOKEN_OR)) {
1813
158
    isl_map *res_i;
1814
158
1815
158
    res_i = read_conjuncts(s, v, isl_map_copy(map), rational);
1816
158
    res = isl_map_union(res, res_i);
1817
158
  }
1818
2.10k
1819
2.10k
  isl_map_free(map);
1820
2.10k
  return res;
1821
2.10k
}
1822
1823
/* Read a first order formula from "s", add the corresponding
1824
 * constraints to "map" and return the result.
1825
 *
1826
 * In particular, read a formula of the form
1827
 *
1828
 *  a
1829
 *
1830
 * or
1831
 *
1832
 *  a implies b
1833
 *
1834
 * where a and b are disjunctions.
1835
 *
1836
 * In the first case, map is replaced by
1837
 *
1838
 *  map \cap { [..] : a }
1839
 *
1840
 * In the second case, it is replaced by
1841
 *
1842
 *  (map \setminus { [..] : a}) \cup (map \cap { [..] : b })
1843
 */
1844
static __isl_give isl_map *read_formula(__isl_keep isl_stream *s,
1845
  struct vars *v, __isl_take isl_map *map, int rational)
1846
2.18k
{
1847
2.18k
  isl_map *res;
1848
2.18k
1849
2.18k
  res = read_disjuncts(s, v, isl_map_copy(map), rational);
1850
2.18k
1851
2.18k
  if (isl_stream_eat_if_available(s, ISL_TOKEN_IMPLIES)) {
1852
1
    isl_map *res2;
1853
1
1854
1
    res = isl_map_subtract(isl_map_copy(map), res);
1855
1
    res2 = read_disjuncts(s, v, map, rational);
1856
1
    res = isl_map_union(res, res2);
1857
1
  } else
1858
2.17k
    isl_map_free(map);
1859
2.18k
1860
2.18k
  return res;
1861
2.18k
}
1862
1863
static int polylib_pos_to_isl_pos(__isl_keep isl_basic_map *bmap, int pos)
1864
1.88k
{
1865
1.88k
  if (pos < isl_basic_map_dim(bmap, isl_dim_out))
1866
1.45k
    return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1867
1.45k
         isl_basic_map_dim(bmap, isl_dim_in) + pos;
1868
429
  pos -= isl_basic_map_dim(bmap, isl_dim_out);
1869
429
1870
429
  if (pos < isl_basic_map_dim(bmap, isl_dim_in))
1871
0
    return 1 + isl_basic_map_dim(bmap, isl_dim_param) + pos;
1872
429
  pos -= isl_basic_map_dim(bmap, isl_dim_in);
1873
429
1874
429
  if (pos < isl_basic_map_dim(bmap, isl_dim_div))
1875
0
    return 1 + isl_basic_map_dim(bmap, isl_dim_param) +
1876
0
         isl_basic_map_dim(bmap, isl_dim_in) +
1877
0
         isl_basic_map_dim(bmap, isl_dim_out) + pos;
1878
429
  pos -= isl_basic_map_dim(bmap, isl_dim_div);
1879
429
1880
429
  if (pos < isl_basic_map_dim(bmap, isl_dim_param))
1881
0
    return 1 + pos;
1882
429
1883
429
  return 0;
1884
429
}
1885
1886
static __isl_give isl_basic_map *basic_map_read_polylib_constraint(
1887
  __isl_keep isl_stream *s, __isl_take isl_basic_map *bmap)
1888
429
{
1889
429
  int j;
1890
429
  struct isl_token *tok;
1891
429
  int type;
1892
429
  int k;
1893
429
  isl_int *c;
1894
429
1895
429
  if (!bmap)
1896
0
    return NULL;
1897
429
1898
429
  tok = isl_stream_next_token(s);
1899
429
  if (!tok || tok->type != ISL_TOKEN_VALUE) {
1900
0
    isl_stream_error(s, tok, "expecting coefficient");
1901
0
    if (tok)
1902
0
      isl_stream_push_token(s, tok);
1903
0
    goto error;
1904
0
  }
1905
429
  if (!tok->on_new_line) {
1906
0
    isl_stream_error(s, tok, "coefficient should appear on new line");
1907
0
    isl_stream_push_token(s, tok);
1908
0
    goto error;
1909
0
  }
1910
429
1911
429
  type = isl_int_get_si(tok->u.v);
1912
429
  isl_token_free(tok);
1913
429
1914
429
  isl_assert(s->ctx, type == 0 || type == 1, goto error);
1915
429
  if (type == 0) {
1916
30
    k = isl_basic_map_alloc_equality(bmap);
1917
30
    c = bmap->eq[k];
1918
399
  } else {
1919
399
    k = isl_basic_map_alloc_inequality(bmap);
1920
399
    c = bmap->ineq[k];
1921
399
  }
1922
429
  if (k < 0)
1923
0
    goto error;
1924
429
1925
2.31k
  
for (j = 0; 429
j < 1 + isl_basic_map_total_dim(bmap);
++j1.88k
) {
1926
1.88k
    int pos;
1927
1.88k
    tok = isl_stream_next_token(s);
1928
1.88k
    if (!tok || tok->type != ISL_TOKEN_VALUE) {
1929
0
      isl_stream_error(s, tok, "expecting coefficient");
1930
0
      if (tok)
1931
0
        isl_stream_push_token(s, tok);
1932
0
      goto error;
1933
0
    }
1934
1.88k
    if (tok->on_new_line) {
1935
0
      isl_stream_error(s, tok,
1936
0
        "coefficient should not appear on new line");
1937
0
      isl_stream_push_token(s, tok);
1938
0
      goto error;
1939
0
    }
1940
1.88k
    pos = polylib_pos_to_isl_pos(bmap, j);
1941
1.88k
    isl_int_set(c[pos], tok->u.v);
1942
1.88k
    isl_token_free(tok);
1943
1.88k
  }
1944
429
1945
429
  return bmap;
1946
0
error:
1947
0
  isl_basic_map_free(bmap);
1948
0
  return NULL;
1949
429
}
1950
1951
static __isl_give isl_basic_map *basic_map_read_polylib(
1952
  __isl_keep isl_stream *s)
1953
105
{
1954
105
  int i;
1955
105
  struct isl_token *tok;
1956
105
  struct isl_token *tok2;
1957
105
  int n_row, n_col;
1958
105
  int on_new_line;
1959
105
  unsigned in = 0, out, local = 0;
1960
105
  struct isl_basic_map *bmap = NULL;
1961
105
  int nparam = 0;
1962
105
1963
105
  tok = isl_stream_next_token(s);
1964
105
  if (!tok) {
1965
0
    isl_stream_error(s, NULL, "unexpected EOF");
1966
0
    return NULL;
1967
0
  }
1968
105
  tok2 = isl_stream_next_token(s);
1969
105
  if (!tok2) {
1970
0
    isl_token_free(tok);
1971
0
    isl_stream_error(s, NULL, "unexpected EOF");
1972
0
    return NULL;
1973
0
  }
1974
105
  if (tok->type != ISL_TOKEN_VALUE || tok2->type != ISL_TOKEN_VALUE) {
1975
0
    isl_stream_push_token(s, tok2);
1976
0
    isl_stream_push_token(s, tok);
1977
0
    isl_stream_error(s, NULL,
1978
0
         "expecting constraint matrix dimensions");
1979
0
    return NULL;
1980
0
  }
1981
105
  n_row = isl_int_get_si(tok->u.v);
1982
105
  n_col = isl_int_get_si(tok2->u.v);
1983
105
  on_new_line = tok2->on_new_line;
1984
105
  isl_token_free(tok2);
1985
105
  isl_token_free(tok);
1986
105
  isl_assert(s->ctx, !on_new_line, return NULL);
1987
105
  isl_assert(s->ctx, n_row >= 0, return NULL);
1988
105
  isl_assert(s->ctx, n_col >= 2 + nparam, return NULL);
1989
105
  tok = isl_stream_next_token_on_same_line(s);
1990
105
  if (tok) {
1991
0
    if (tok->type != ISL_TOKEN_VALUE) {
1992
0
      isl_stream_error(s, tok,
1993
0
            "expecting number of output dimensions");
1994
0
      isl_stream_push_token(s, tok);
1995
0
      goto error;
1996
0
    }
1997
0
    out = isl_int_get_si(tok->u.v);
1998
0
    isl_token_free(tok);
1999
0
2000
0
    tok = isl_stream_next_token_on_same_line(s);
2001
0
    if (!tok || tok->type != ISL_TOKEN_VALUE) {
2002
0
      isl_stream_error(s, tok,
2003
0
            "expecting number of input dimensions");
2004
0
      if (tok)
2005
0
        isl_stream_push_token(s, tok);
2006
0
      goto error;
2007
0
    }
2008
0
    in = isl_int_get_si(tok->u.v);
2009
0
    isl_token_free(tok);
2010
0
2011
0
    tok = isl_stream_next_token_on_same_line(s);
2012
0
    if (!tok || tok->type != ISL_TOKEN_VALUE) {
2013
0
      isl_stream_error(s, tok,
2014
0
            "expecting number of existentials");
2015
0
      if (tok)
2016
0
        isl_stream_push_token(s, tok);
2017
0
      goto error;
2018
0
    }
2019
0
    local = isl_int_get_si(tok->u.v);
2020
0
    isl_token_free(tok);
2021
0
2022
0
    tok = isl_stream_next_token_on_same_line(s);
2023
0
    if (!tok || tok->type != ISL_TOKEN_VALUE) {
2024
0
      isl_stream_error(s, tok,
2025
0
            "expecting number of parameters");
2026
0
      if (tok)
2027
0
        isl_stream_push_token(s, tok);
2028
0
      goto error;
2029
0
    }
2030
0
    nparam = isl_int_get_si(tok->u.v);
2031
0
    isl_token_free(tok);
2032
0
    if (n_col != 1 + out + in + local + nparam + 1) {
2033
0
      isl_stream_error(s, NULL,
2034
0
            "dimensions don't match");
2035
0
      goto error;
2036
0
    }
2037
105
  } else
2038
105
    out = n_col - 2 - nparam;
2039
105
  bmap = isl_basic_map_alloc(s->ctx, nparam, in, out, local, n_row, n_row);
2040
105
  if (!bmap)
2041
0
    return NULL;
2042
105
2043
105
  for (i = 0; i < local; 
++i0
) {
2044
0
    int k = isl_basic_map_alloc_div(bmap);
2045
0
    if (k < 0)
2046
0
      goto error;
2047
0
    isl_seq_clr(bmap->div[k], 1 + 1 + nparam + in + out + local);
2048
0
  }
2049
105
2050
534
  
for (i = 0; 105
i < n_row;
++i429
)
2051
429
    bmap = basic_map_read_polylib_constraint(s, bmap);
2052
105
2053
105
  tok = isl_stream_next_token_on_same_line(s);
2054
105
  if (tok) {
2055
0
    isl_stream_error(s, tok, "unexpected extra token on line");
2056
0
    isl_stream_push_token(s, tok);
2057
0
    goto error;
2058
0
  }
2059
105
2060
105
  bmap = isl_basic_map_simplify(bmap);
2061
105
  bmap = isl_basic_map_finalize(bmap);
2062
105
  return bmap;
2063
0
error:
2064
0
  isl_basic_map_free(bmap);
2065
0
  return NULL;
2066
105
}
2067
2068
static struct isl_map *map_read_polylib(__isl_keep isl_stream *s)
2069
105
{
2070
105
  struct isl_token *tok;
2071
105
  struct isl_token *tok2;
2072
105
  int i, n;
2073
105
  struct isl_map *map;
2074
105
2075
105
  tok = isl_stream_next_token(s);
2076
105
  if (!tok) {
2077
0
    isl_stream_error(s, NULL, "unexpected EOF");
2078
0
    return NULL;
2079
0
  }
2080
105
  tok2 = isl_stream_next_token_on_same_line(s);
2081
105
  if (tok2 && tok2->type == ISL_TOKEN_VALUE) {
2082
105
    isl_stream_push_token(s, tok2);
2083
105
    isl_stream_push_token(s, tok);
2084
105
    return isl_map_from_basic_map(basic_map_read_polylib(s));
2085
105
  }
2086
0
  if (tok2) {
2087
0
    isl_stream_error(s, tok2, "unexpected token");
2088
0
    isl_stream_push_token(s, tok2);
2089
0
    isl_stream_push_token(s, tok);
2090
0
    return NULL;
2091
0
  }
2092
0
  n = isl_int_get_si(tok->u.v);
2093
0
  isl_token_free(tok);
2094
0
2095
0
  isl_assert(s->ctx, n >= 1, return NULL);
2096
0
2097
0
  map = isl_map_from_basic_map(basic_map_read_polylib(s));
2098
0
2099
0
  for (i = 1; map && i < n; ++i)
2100
0
    map = isl_map_union(map,
2101
0
      isl_map_from_basic_map(basic_map_read_polylib(s)));
2102
0
2103
0
  return map;
2104
0
}
2105
2106
static int optional_power(__isl_keep isl_stream *s)
2107
66
{
2108
66
  int pow;
2109
66
  struct isl_token *tok;
2110
66
2111
66
  tok = isl_stream_next_token(s);
2112
66
  if (!tok)
2113
0
    return 1;
2114
66
  if (tok->type != '^') {
2115
60
    isl_stream_push_token(s, tok);
2116
60
    return 1;
2117
60
  }
2118
6
  isl_token_free(tok);
2119
6
  tok = isl_stream_next_token(s);
2120
6
  if (!tok || tok->type != ISL_TOKEN_VALUE) {
2121
0
    isl_stream_error(s, tok, "expecting exponent");
2122
0
    if (tok)
2123
0
      isl_stream_push_token(s, tok);
2124
0
    return 1;
2125
0
  }
2126
6
  pow = isl_int_get_si(tok->u.v);
2127
6
  isl_token_free(tok);
2128
6
  return pow;
2129
6
}
2130
2131
static __isl_give isl_pw_qpolynomial *read_term(__isl_keep isl_stream *s,
2132
  __isl_keep isl_map *map, struct vars *v);
2133
2134
static __isl_give isl_pw_qpolynomial *read_factor(__isl_keep isl_stream *s,
2135
  __isl_keep isl_map *map, struct vars *v)
2136
84
{
2137
84
  isl_pw_qpolynomial *pwqp;
2138
84
  struct isl_token *tok;
2139
84
2140
84
  tok = next_token(s);
2141
84
  if (!tok) {
2142
0
    isl_stream_error(s, NULL, "unexpected EOF");
2143
0
    return NULL;
2144
0
  }
2145
84
  if (tok->type == '(') {
2146
21
    int pow;
2147
21
2148
21
    isl_token_free(tok);
2149
21
    pwqp = read_term(s, map, v);
2150
21
    if (!pwqp)
2151
0
      return NULL;
2152
21
    if (isl_stream_eat(s, ')'))
2153
0
      goto error;
2154
21
    pow = optional_power(s);
2155
21
    pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
2156
63
  } else if (tok->type == ISL_TOKEN_VALUE) {
2157
15
    struct isl_token *tok2;
2158
15
    isl_qpolynomial *qp;
2159
15
2160
15
    tok2 = isl_stream_next_token(s);
2161
15
    if (tok2 && tok2->type == '/') {
2162
4
      isl_token_free(tok2);
2163
4
      tok2 = next_token(s);
2164
4
      if (!tok2 || tok2->type != ISL_TOKEN_VALUE) {
2165
0
        isl_stream_error(s, tok2, "expected denominator");
2166
0
        isl_token_free(tok);
2167
0
        isl_token_free(tok2);
2168
0
        return NULL;
2169
0
      }
2170
4
      qp = isl_qpolynomial_rat_cst_on_domain(isl_map_get_space(map),
2171
4
                tok->u.v, tok2->u.v);
2172
4
      isl_token_free(tok2);
2173
11
    } else {
2174
11
      isl_stream_push_token(s, tok2);
2175
11
      qp = isl_qpolynomial_cst_on_domain(isl_map_get_space(map),
2176
11
            tok->u.v);
2177
11
    }
2178
15
    isl_token_free(tok);
2179
15
    pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2180
48
  } else if (tok->type == ISL_TOKEN_INFTY) {
2181
1
    isl_qpolynomial *qp;
2182
1
    isl_token_free(tok);
2183
1
    qp = isl_qpolynomial_infty_on_domain(isl_map_get_space(map));
2184
1
    pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2185
47
  } else if (tok->type == ISL_TOKEN_NAN) {
2186
0
    isl_qpolynomial *qp;
2187
0
    isl_token_free(tok);
2188
0
    qp = isl_qpolynomial_nan_on_domain(isl_map_get_space(map));
2189
0
    pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2190
47
  } else if (tok->type == ISL_TOKEN_IDENT) {
2191
16
    int n = v->n;
2192
16
    int pos = vars_pos(v, tok->u.s, -1);
2193
16
    int pow;
2194
16
    isl_qpolynomial *qp;
2195
16
    if (pos < 0) {
2196
0
      isl_token_free(tok);
2197
0
      return NULL;
2198
0
    }
2199
16
    if (pos >= n) {
2200
0
      vars_drop(v, v->n - n);
2201
0
      isl_stream_error(s, tok, "unknown identifier");
2202
0
      isl_token_free(tok);
2203
0
      return NULL;
2204
0
    }
2205
16
    isl_token_free(tok);
2206
16
    pow = optional_power(s);
2207
16
    qp = isl_qpolynomial_var_pow_on_domain(isl_map_get_space(map), pos, pow);
2208
16
    pwqp = isl_pw_qpolynomial_from_qpolynomial(qp);
2209
31
  } else if (is_start_of_div(tok)) {
2210
29
    isl_pw_aff *pwaff;
2211
29
    int pow;
2212
29
2213
29
    isl_stream_push_token(s, tok);
2214
29
    pwaff = accept_div(s, isl_map_get_space(map), v);
2215
29
    pow = optional_power(s);
2216
29
    pwqp = isl_pw_qpolynomial_from_pw_aff(pwaff);
2217
29
    pwqp = isl_pw_qpolynomial_pow(pwqp, pow);
2218
29
  } else 
if (2
tok->type == '-'2
) {
2219
2
    isl_token_free(tok);
2220
2
    pwqp = read_factor(s, map, v);
2221
2
    pwqp = isl_pw_qpolynomial_neg(pwqp);
2222
2
  } else {
2223
0
    isl_stream_error(s, tok, "unexpected isl_token");
2224
0
    isl_stream_push_token(s, tok);
2225
0
    return NULL;
2226
0
  }
2227
84
2228
84
  if (isl_stream_eat_if_available(s, '*') ||
2229
84
      
isl_stream_next_token_is(s, ISL_TOKEN_IDENT)69
) {
2230
15
    isl_pw_qpolynomial *pwqp2;
2231
15
2232
15
    pwqp2 = read_factor(s, map, v);
2233
15
    pwqp = isl_pw_qpolynomial_mul(pwqp, pwqp2);
2234
15
  }
2235
84
2236
84
  return pwqp;
2237
0
error:
2238
0
  isl_pw_qpolynomial_free(pwqp);
2239
0
  return NULL;
2240
84
}
2241
2242
static __isl_give isl_pw_qpolynomial *read_term(__isl_keep isl_stream *s,
2243
  __isl_keep isl_map *map, struct vars *v)
2244
54
{
2245
54
  struct isl_token *tok;
2246
54
  isl_pw_qpolynomial *pwqp;
2247
54
2248
54
  pwqp = read_factor(s, map, v);
2249
54
2250
67
  for (;;) {
2251
67
    tok = next_token(s);
2252
67
    if (!tok)
2253
0
      return pwqp;
2254
67
2255
67
    if (tok->type == '+') {
2256
12
      isl_pw_qpolynomial *pwqp2;
2257
12
2258
12
      isl_token_free(tok);
2259
12
      pwqp2 = read_factor(s, map, v);
2260
12
      pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
2261
55
    } else if (tok->type == '-') {
2262
1
      isl_pw_qpolynomial *pwqp2;
2263
1
2264
1
      isl_token_free(tok);
2265
1
      pwqp2 = read_factor(s, map, v);
2266
1
      pwqp = isl_pw_qpolynomial_sub(pwqp, pwqp2);
2267
54
    } else if (tok->type == ISL_TOKEN_VALUE &&
2268
54
          
isl_int_is_neg0
(tok->u.v)) {
2269
0
      isl_pw_qpolynomial *pwqp2;
2270
0
2271
0
      isl_stream_push_token(s, tok);
2272
0
      pwqp2 = read_factor(s, map, v);
2273
0
      pwqp = isl_pw_qpolynomial_add(pwqp, pwqp2);
2274
54
    } else {
2275
54
      isl_stream_push_token(s, tok);
2276
54
      break;
2277
54
    }
2278
67
  }
2279
54
2280
54
  return pwqp;
2281
54
}
2282
2283
static __isl_give isl_map *read_optional_formula(__isl_keep isl_stream *s,
2284
  __isl_take isl_map *map, struct vars *v, int rational)
2285
3.44k
{
2286
3.44k
  struct isl_token *tok;
2287
3.44k
2288
3.44k
  tok = isl_stream_next_token(s);
2289
3.44k
  if (!tok) {
2290
0
    isl_stream_error(s, NULL, "unexpected EOF");
2291
0
    goto error;
2292
0
  }
2293
3.44k
  if (tok->type == ':' ||
2294
3.44k
      
(1.70k
tok->type == ISL_TOKEN_OR1.70k
&&
!strcmp(tok->u.s, "|")0
)) {
2295
1.73k
    isl_token_free(tok);
2296
1.73k
    map = read_formula(s, v, map, rational);
2297
1.73k
  } else
2298
1.70k
    isl_stream_push_token(s, tok);
2299
3.44k
2300
3.44k
  return map;
2301
0
error:
2302
0
  isl_map_free(map);
2303
0
  return NULL;
2304
3.44k
}
2305
2306
static struct isl_obj obj_read_poly(__isl_keep isl_stream *s,
2307
  __isl_take isl_map *map, struct vars *v, int n)
2308
33
{
2309
33
  struct isl_obj obj = { isl_obj_pw_qpolynomial, NULL };
2310
33
  isl_pw_qpolynomial *pwqp;
2311
33
  struct isl_set *set;
2312
33
2313
33
  pwqp = read_term(s, map, v);
2314
33
  map = read_optional_formula(s, map, v, 0);
2315
33
  set = isl_map_range(map);
2316
33
2317
33
  pwqp = isl_pw_qpolynomial_intersect_domain(pwqp, set);
2318
33
2319
33
  vars_drop(v, v->n - n);
2320
33
2321
33
  obj.v = pwqp;
2322
33
  return obj;
2323
33
}
2324
2325
static struct isl_obj obj_read_poly_or_fold(__isl_keep isl_stream *s,
2326
  __isl_take isl_set *set, struct vars *v, int n)
2327
33
{
2328
33
  struct isl_obj obj = { isl_obj_pw_qpolynomial_fold, NULL };
2329
33
  isl_pw_qpolynomial *pwqp;
2330
33
  isl_pw_qpolynomial_fold *pwf = NULL;
2331
33
2332
33
  if (!isl_stream_eat_if_available(s, ISL_TOKEN_MAX))
2333
33
    return obj_read_poly(s, set, v, n);
2334
0
2335
0
  if (isl_stream_eat(s, '('))
2336
0
    goto error;
2337
0
2338
0
  pwqp = read_term(s, set, v);
2339
0
  pwf = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max, pwqp);
2340
0
2341
0
  while (isl_stream_eat_if_available(s, ',')) {
2342
0
    isl_pw_qpolynomial_fold *pwf_i;
2343
0
    pwqp = read_term(s, set, v);
2344
0
    pwf_i = isl_pw_qpolynomial_fold_from_pw_qpolynomial(isl_fold_max,
2345
0
                  pwqp);
2346
0
    pwf = isl_pw_qpolynomial_fold_fold(pwf, pwf_i);
2347
0
  }
2348
0
2349
0
  if (isl_stream_eat(s, ')'))
2350
0
    goto error;
2351
0
2352
0
  set = read_optional_formula(s, set, v, 0);
2353
0
  pwf = isl_pw_qpolynomial_fold_intersect_domain(pwf, set);
2354
0
2355
0
  vars_drop(v, v->n - n);
2356
0
2357
0
  obj.v = pwf;
2358
0
  return obj;
2359
0
error:
2360
0
  isl_set_free(set);
2361
0
  isl_pw_qpolynomial_fold_free(pwf);
2362
0
  obj.type = isl_obj_none;
2363
0
  return obj;
2364
0
}
2365
2366
static int is_rational(__isl_keep isl_stream *s)
2367
3.07k
{
2368
3.07k
  struct isl_token *tok;
2369
3.07k
2370
3.07k
  tok = isl_stream_next_token(s);
2371
3.07k
  if (!tok)
2372
0
    return 0;
2373
3.07k
  if (tok->type == ISL_TOKEN_RAT && 
isl_stream_next_token_is(s, ':')22
) {
2374
22
    isl_token_free(tok);
2375
22
    isl_stream_eat(s, ':');
2376
22
    return 1;
2377
22
  }
2378
3.05k
2379
3.05k
  isl_stream_push_token(s, tok);
2380
3.05k
2381
3.05k
  return 0;
2382
3.05k
}
2383
2384
static struct isl_obj obj_read_body(__isl_keep isl_stream *s,
2385
  __isl_take isl_map *map, struct vars *v)
2386
3.07k
{
2387
3.07k
  struct isl_token *tok;
2388
3.07k
  struct isl_obj obj = { isl_obj_set, NULL };
2389
3.07k
  int n = v->n;
2390
3.07k
  int rational;
2391
3.07k
2392
3.07k
  rational = is_rational(s);
2393
3.07k
  if (rational)
2394
22
    map = isl_map_set_rational(map);
2395
3.07k
2396
3.07k
  if (isl_stream_next_token_is(s, ':')) {
2397
172
    obj.type = isl_obj_set;
2398
172
    obj.v = read_optional_formula(s, map, v, rational);
2399
172
    return obj;
2400
172
  }
2401
2.90k
2402
2.90k
  if (!next_is_tuple(s))
2403
1
    return obj_read_poly_or_fold(s, map, v, n);
2404
2.90k
2405
2.90k
  map = read_map_tuple(s, map, isl_dim_in, v, rational, 0);
2406
2.90k
  if (!map)
2407
0
    goto error;
2408
2.90k
  tok = isl_stream_next_token(s);
2409
2.90k
  if (!tok)
2410
0
    goto error;
2411
2.90k
  if (tok->type == ISL_TOKEN_TO) {
2412
1.78k
    obj.type = isl_obj_map;
2413
1.78k
    isl_token_free(tok);
2414
1.78k
    if (!next_is_tuple(s)) {
2415
32
      isl_set *set = isl_map_domain(map);
2416
32
      return obj_read_poly_or_fold(s, set, v, n);
2417
32
    }
2418
1.75k
    map = read_map_tuple(s, map, isl_dim_out, v, rational, 0);
2419
1.75k
    if (!map)
2420
1
      goto error;
2421
1.11k
  } else {
2422
1.11k
    map = isl_map_domain(map);
2423
1.11k
    isl_stream_push_token(s, tok);
2424
1.11k
  }
2425
2.90k
2426
2.90k
  map = read_optional_formula(s, map, v, rational);
2427
2.87k
2428
2.87k
  vars_drop(v, v->n - n);
2429
2.87k
2430
2.87k
  obj.v = map;
2431
2.87k
  return obj;
2432
1
error:
2433
1
  isl_map_free(map);
2434
1
  obj.type = isl_obj_none;
2435
1
  return obj;
2436
2.90k
}
2437
2438
static struct isl_obj to_union(isl_ctx *ctx, struct isl_obj obj)
2439
832
{
2440
832
  if (obj.type == isl_obj_map) {
2441
648
    obj.v = isl_union_map_from_map(obj.v);
2442
648
    obj.type = isl_obj_union_map;
2443
648
  } else 
if (184
obj.type == 184
isl_obj_set184
) {
2444
182
    obj.v = isl_union_set_from_set(obj.v);
2445
182
    obj.type = isl_obj_union_set;
2446
182
  } else 
if (2
obj.type == 2
isl_obj_pw_qpolynomial2
) {
2447
2
    obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
2448
2
    obj.type = isl_obj_union_pw_qpolynomial;
2449
2
  } else 
if (0
obj.type == 0
isl_obj_pw_qpolynomial_fold0
) {
2450
0
    obj.v = isl_union_pw_qpolynomial_fold_from_pw_qpolynomial_fold(obj.v);
2451
0
    obj.type = isl_obj_union_pw_qpolynomial_fold;
2452
0
  } else
2453
0
    isl_assert(ctx, 0, goto error);
2454
832
  return obj;
2455
0
error:
2456
0
  obj.type->free(obj.v);
2457
0
  obj.type = isl_obj_none;
2458
0
  return obj;
2459
832
}
2460
2461
static struct isl_obj obj_add(__isl_keep isl_stream *s,
2462
  struct isl_obj obj1, struct isl_obj obj2)
2463
718
{
2464
718
  if (obj2.type == isl_obj_none || !obj2.v)
2465
0
    goto error;
2466
718
  if (obj1.type == isl_obj_set && 
obj2.type == 233
isl_obj_union_set233
)
2467
718
    
obj1 = to_union(s->ctx, obj1)0
;
2468
718
  if (obj1.type == isl_obj_union_set && 
obj2.type == 22
isl_obj_set22
)
2469
718
    
obj2 = to_union(s->ctx, obj2)22
;
2470
718
  if (obj1.type == isl_obj_map && 
obj2.type == 362
isl_obj_union_map362
)
2471
718
    
obj1 = to_union(s->ctx, obj1)0
;
2472
718
  if (obj1.type == isl_obj_union_map && 
obj2.type == 97
isl_obj_map97
)
2473
718
    
obj2 = to_union(s->ctx, obj2)97
;
2474
718
  if (obj1.type == isl_obj_pw_qpolynomial &&
2475
718
      
obj2.type == 4
isl_obj_union_pw_qpolynomial4
)
2476
718
    
obj1 = to_union(s->ctx, obj1)0
;
2477
718
  if (obj1.type == isl_obj_union_pw_qpolynomial &&
2478
718
      
obj2.type == 0
isl_obj_pw_qpolynomial0
)
2479
718
    
obj2 = to_union(s->ctx, obj2)0
;
2480
718
  if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2481
718
      
obj2.type == 0
isl_obj_union_pw_qpolynomial_fold0
)
2482
718
    
obj1 = to_union(s->ctx, obj1)0
;
2483
718
  if (obj1.type == isl_obj_union_pw_qpolynomial_fold &&
2484
718
      
obj2.type == 0
isl_obj_pw_qpolynomial_fold0
)
2485
718
    
obj2 = to_union(s->ctx, obj2)0
;
2486
718
  if (obj1.type != obj2.type) {
2487
0
    isl_stream_error(s, NULL,
2488
0
        "attempt to combine incompatible objects");
2489
0
    goto error;
2490
0
  }
2491
718
  if (!obj1.type->add)
2492
718
    
isl_die0
(s->ctx, isl_error_internal,
2493
718
      "combination not supported on object type", goto error);
2494
718
  if (obj1.type == isl_obj_map && 
!isl_map_has_equal_space(obj1.v, obj2.v)362
) {
2495
261
    obj1 = to_union(s->ctx, obj1);
2496
261
    obj2 = to_union(s->ctx, obj2);
2497
261
  }
2498
718
  if (obj1.type == isl_obj_set && 
!isl_set_has_equal_space(obj1.v, obj2.v)233
) {
2499
80
    obj1 = to_union(s->ctx, obj1);
2500
80
    obj2 = to_union(s->ctx, obj2);
2501
80
  }
2502
718
  if (obj1.type == isl_obj_pw_qpolynomial &&
2503
718
      
!isl_pw_qpolynomial_has_equal_space(obj1.v, obj2.v)4
) {
2504
1
    obj1 = to_union(s->ctx, obj1);
2505
1
    obj2 = to_union(s->ctx, obj2);
2506
1
  }
2507
718
  if (obj1.type == isl_obj_pw_qpolynomial_fold &&
2508
718
      
!isl_pw_qpolynomial_fold_has_equal_space(obj1.v, obj2.v)0
) {
2509
0
    obj1 = to_union(s->ctx, obj1);
2510
0
    obj2 = to_union(s->ctx, obj2);
2511
0
  }
2512
718
  obj1.v = obj1.type->add(obj1.v, obj2.v);
2513
718
  return obj1;
2514
0
error:
2515
0
  obj1.type->free(obj1.v);
2516
0
  obj2.type->free(obj2.v);
2517
0
  obj1.type = isl_obj_none;
2518
0
  obj1.v = NULL;
2519
0
  return obj1;
2520
718
}
2521
2522
/* Are the first two tokens on "s", "domain" (either as a string
2523
 * or as an identifier) followed by ":"?
2524
 */
2525
static int next_is_domain_colon(__isl_keep isl_stream *s)
2526
2.58k
{
2527
2.58k
  struct isl_token *tok;
2528
2.58k
  char *name;
2529
2.58k
  int res;
2530
2.58k
2531
2.58k
  tok = isl_stream_next_token(s);
2532
2.58k
  if (!tok)
2533
0
    return 0;
2534
2.58k
  if (tok->type != ISL_TOKEN_IDENT && 
tok->type != ISL_TOKEN_STRING1.71k
) {
2535
1.71k
    isl_stream_push_token(s, tok);
2536
1.71k
    return 0;
2537
1.71k
  }
2538
870
2539
870
  name = isl_token_get_str(s->ctx, tok);
2540
870
  res = !strcmp(name, "domain") && 
isl_stream_next_token_is(s, ':')0
;
2541
870
  free(name);
2542
870
2543
870
  isl_stream_push_token(s, tok);
2544
870
2545
870
  return res;
2546
870
}
2547
2548
/* Do the first tokens on "s" look like a schedule?
2549
 *
2550
 * The root of a schedule is always a domain node, so the first thing
2551
 * we expect in the stream is a domain key, i.e., "domain" followed
2552
 * by ":".  If the schedule was printed in YAML flow style, then
2553
 * we additionally expect a "{" to open the outer mapping.
2554
 */
2555
static int next_is_schedule(__isl_keep isl_stream *s)
2556
2.58k
{
2557
2.58k
  struct isl_token *tok;
2558
2.58k
  int is_schedule;
2559
2.58k
2560
2.58k
  tok = isl_stream_next_token(s);
2561
2.58k
  if (!tok)
2562
0
    return 0;
2563
2.58k
  if (tok->type != '{') {
2564
719
    isl_stream_push_token(s, tok);
2565
719
    return next_is_domain_colon(s);
2566
719
  }
2567
1.86k
2568
1.86k
  is_schedule = next_is_domain_colon(s);
2569
1.86k
  isl_stream_push_token(s, tok);
2570
1.86k
2571
1.86k
  return is_schedule;
2572
1.86k
}
2573
2574
/* Read an isl_schedule from "s" and store it in an isl_obj.
2575
 */
2576
static struct isl_obj schedule_read(__isl_keep isl_stream *s)
2577
0
{
2578
0
  struct isl_obj obj;
2579
0
2580
0
  obj.type = isl_obj_schedule;
2581
0
  obj.v = isl_stream_read_schedule(s);
2582
0
2583
0
  return obj;
2584
0
}
2585
2586
/* Read a disjunction of object bodies from "s".
2587
 * That is, read the inside of the braces, but not the braces themselves.
2588
 * "v" contains a description of the identifiers parsed so far.
2589
 * "map" contains information about the parameters.
2590
 */
2591
static struct isl_obj obj_read_disjuncts(__isl_keep isl_stream *s,
2592
  struct vars *v, __isl_keep isl_map *map)
2593
2.54k
{
2594
2.54k
  struct isl_obj obj = { isl_obj_set, NULL };
2595
2.54k
2596
2.54k
  if (isl_stream_next_token_is(s, '}')) {
2597
190
    obj.type = isl_obj_union_set;
2598
190
    obj.v = isl_union_set_empty(isl_map_get_space(map));
2599
190
    return obj;
2600
190
  }
2601
2.35k
2602
3.07k
  
for (;;)2.35k
{
2603
3.07k
    struct isl_obj o;
2604
3.07k
    o = obj_read_body(s, isl_map_copy(map), v);
2605
3.07k
    if (!obj.v)
2606
2.35k
      obj = o;
2607
718
    else
2608
718
      obj = obj_add(s, obj, o);
2609
3.07k
    if (obj.type == isl_obj_none || 
!obj.v3.07k
)
2610
2
      return obj;
2611
3.07k
    if (!isl_stream_eat_if_available(s, ';'))
2612
2.35k
      break;
2613
718
    if (isl_stream_next_token_is(s, '}'))
2614
0
      break;
2615
718
  }
2616
2.35k
2617
2.35k
  
return obj2.35k
;
2618
2.35k
}
2619
2620
static struct isl_obj obj_read(__isl_keep isl_stream *s)
2621
2.58k
{
2622
2.58k
  isl_map *map = NULL;
2623
2.58k
  struct isl_token *tok;
2624
2.58k
  struct vars *v = NULL;
2625
2.58k
  struct isl_obj obj = { isl_obj_set, NULL };
2626
2.58k
2627
2.58k
  if (next_is_schedule(s))
2628
0
    return schedule_read(s);
2629
2.58k
2630
2.58k
  tok = next_token(s);
2631
2.58k
  if (!tok) {
2632
0
    isl_stream_error(s, NULL, "unexpected EOF");
2633
0
    goto error;
2634
0
  }
2635
2.58k
  if (tok->type == ISL_TOKEN_VALUE) {
2636
105
    struct isl_token *tok2;
2637
105
    struct isl_map *map;
2638
105
2639
105
    tok2 = isl_stream_next_token(s);
2640
105
    if (!tok2 || tok2->type != ISL_TOKEN_VALUE ||
2641
105
        isl_int_is_neg(tok2->u.v)) {
2642
0
      if (tok2)
2643
0
        isl_stream_push_token(s, tok2);
2644
0
      obj.type = isl_obj_val;
2645
0
      obj.v = isl_val_int_from_isl_int(s->ctx, tok->u.v);
2646
0
      isl_token_free(tok);
2647
0
      return obj;
2648
0
    }
2649
105
    isl_stream_push_token(s, tok2);
2650
105
    isl_stream_push_token(s, tok);
2651
105
    map = map_read_polylib(s);
2652
105
    if (!map)
2653
0
      goto error;
2654
105
    if (isl_map_may_be_set(map))
2655
105
      obj.v = isl_map_range(map);
2656
0
    else {
2657
0
      obj.type = isl_obj_map;
2658
0
      obj.v = map;
2659
0
    }
2660
105
    return obj;
2661
105
  }
2662
2.47k
  v = vars_new(s->ctx);
2663
2.47k
  if (!v) {
2664
0
    isl_stream_push_token(s, tok);
2665
0
    goto error;
2666
0
  }
2667
2.47k
  map = isl_map_universe(isl_space_params_alloc(s->ctx, 0));
2668
2.47k
  if (tok->type == '[') {
2669
614
    isl_stream_push_token(s, tok);
2670
614
    map = read_map_tuple(s, map, isl_dim_param, v, 0, 0);
2671
614
    if (!map)
2672
1
      goto error;
2673
613
    tok = isl_stream_next_token(s);
2674
613
    if (!tok || tok->type != ISL_TOKEN_TO) {
2675
0
      isl_stream_error(s, tok, "expecting '->'");
2676
0
      if (tok)
2677
0
        isl_stream_push_token(s, tok);
2678
0
      goto error;
2679
0
    }
2680
613
    isl_token_free(tok);
2681
613
    tok = isl_stream_next_token(s);
2682
613
  }
2683
2.47k
  
if (2.47k
!tok2.47k
||
tok->type != '{'2.47k
) {
2684
0
    isl_stream_error(s, tok, "expecting '{'");
2685
0
    if (tok)
2686
0
      isl_stream_push_token(s, tok);
2687
0
    goto error;
2688
0
  }
2689
2.47k
  isl_token_free(tok);
2690
2.47k
2691
2.47k
  tok = isl_stream_next_token(s);
2692
2.47k
  if (!tok)
2693
0
    ;
2694
2.47k
  else if (tok->type == ISL_TOKEN_IDENT && 
!strcmp(tok->u.s, "Sym")1.25k
) {
2695
1
    isl_token_free(tok);
2696
1
    if (isl_stream_eat(s, '='))
2697
0
      goto error;
2698
1
    map = read_map_tuple(s, map, isl_dim_param, v, 0, 1);
2699
1
    if (!map)
2700
0
      goto error;
2701
2.47k
  } else
2702
2.47k
    isl_stream_push_token(s, tok);
2703
2.47k
2704
2.47k
  obj = obj_read_disjuncts(s, v, map);
2705
2.47k
  if (obj.type == isl_obj_none || 
!obj.v2.47k
)
2706
2
    goto error;
2707
2.47k
2708
2.47k
  tok = isl_stream_next_token(s);
2709
2.47k
  if (tok && tok->type == '}') {
2710
2.47k
    isl_token_free(tok);
2711
2.47k
  } else {
2712
0
    isl_stream_error(s, tok, "unexpected isl_token");
2713
0
    if (tok)
2714
0
      isl_token_free(tok);
2715
0
    goto error;
2716
0
  }
2717
2.47k
2718
2.47k
  vars_free(v);
2719
2.47k
  isl_map_free(map);
2720
2.47k
2721
2.47k
  return obj;
2722
3
error:
2723
3
  isl_map_free(map);
2724
3
  obj.type->free(obj.v);
2725
3
  if (v)
2726
3
    vars_free(v);
2727
3
  obj.v = NULL;
2728
3
  return obj;
2729
2.47k
}
2730
2731
struct isl_obj isl_stream_read_obj(__isl_keep isl_stream *s)
2732
16
{
2733
16
  return obj_read(s);
2734
16
}
2735
2736
__isl_give isl_map *isl_stream_read_map(__isl_keep isl_stream *s)
2737
638
{
2738
638
  struct isl_obj obj;
2739
638
2740
638
  obj = obj_read(s);
2741
638
  if (obj.v)
2742
638
    isl_assert(s->ctx, obj.type == isl_obj_map ||
2743
638
           obj.type == isl_obj_set, goto error);
2744
638
  
2745
638
  if (obj.type == isl_obj_set)
2746
638
    
obj.v = isl_map_from_range(obj.v)31
;
2747
638
2748
638
  return obj.v;
2749
0
error:
2750
0
  obj.type->free(obj.v);
2751
0
  return NULL;
2752
638
}
2753
2754
__isl_give isl_set *isl_stream_read_set(__isl_keep isl_stream *s)
2755
552
{
2756
552
  struct isl_obj obj;
2757
552
2758
552
  obj = obj_read(s);
2759
552
  if (obj.v) {
2760
551
    if (obj.type == isl_obj_map && 
isl_map_may_be_set(obj.v)0
) {
2761
0
      obj.v = isl_map_range(obj.v);
2762
0
      obj.type = isl_obj_set;
2763
0
    }
2764
551
    isl_assert(s->ctx, obj.type == isl_obj_set, goto error);
2765
551
  }
2766
552
2767
552
  return obj.v;
2768
0
error:
2769
0
  obj.type->free(obj.v);
2770
0
  return NULL;
2771
552
}
2772
2773
__isl_give isl_union_map *isl_stream_read_union_map(__isl_keep isl_stream *s)
2774
751
{
2775
751
  struct isl_obj obj;
2776
751
2777
751
  obj = obj_read(s);
2778
751
  if (obj.type == isl_obj_map) {
2779
386
    obj.type = isl_obj_union_map;
2780
386
    obj.v = isl_union_map_from_map(obj.v);
2781
386
  }
2782
751
  if (obj.type == isl_obj_set) {
2783
0
    obj.type = isl_obj_union_set;
2784
0
    obj.v = isl_union_set_from_set(obj.v);
2785
0
  }
2786
751
  if (obj.v && obj.type == isl_obj_union_set &&
2787
751
      
isl_union_set_is_empty(obj.v)110
)
2788
110
    obj.type = isl_obj_union_map;
2789
751
  if (obj.v && obj.type != isl_obj_union_map)
2790
751
    
isl_die0
(s->ctx, isl_error_invalid, "invalid input", goto error);
2791
751
2792
751
  return obj.v;
2793
0
error:
2794
0
  obj.type->free(obj.v);
2795
0
  return NULL;
2796
751
}
2797
2798
/* Extract an isl_union_set from "obj".
2799
 * This only works if the object was detected as either a set
2800
 * (in which case it is converted to a union set) or a union set.
2801
 */
2802
static __isl_give isl_union_set *extract_union_set(isl_ctx *ctx,
2803
  struct isl_obj obj)
2804
449
{
2805
449
  if (obj.type == isl_obj_set) {
2806
290
    obj.type = isl_obj_union_set;
2807
290
    obj.v = isl_union_set_from_set(obj.v);
2808
290
  }
2809
449
  if (obj.v)
2810
449
    isl_assert(ctx, obj.type == isl_obj_union_set, goto error);
2811
449
2812
449
  return obj.v;
2813
0
error:
2814
0
  obj.type->free(obj.v);
2815
0
  return NULL;
2816
449
}
2817
2818
/* Read an isl_union_set from "s".
2819
 * First read a generic object and then try and extract
2820
 * an isl_union_set from that.
2821
 */
2822
__isl_give isl_union_set *isl_stream_read_union_set(__isl_keep isl_stream *s)
2823
378
{
2824
378
  struct isl_obj obj;
2825
378
2826
378
  obj = obj_read(s);
2827
378
  return extract_union_set(s->ctx, obj);
2828
378
}
2829
2830
static __isl_give isl_basic_map *basic_map_read(__isl_keep isl_stream *s)
2831
183
{
2832
183
  struct isl_obj obj;
2833
183
  struct isl_map *map;
2834
183
  struct isl_basic_map *bmap;
2835
183
2836
183
  obj = obj_read(s);
2837
183
  if (obj.v && (obj.type != isl_obj_map && 
obj.type != 173
isl_obj_set173
))
2838
183
    
isl_die0
(s->ctx, isl_error_invalid, "not a (basic) set or map",
2839
183
      goto error);
2840
183
  map = obj.v;
2841
183
  if (!map)
2842
0
    return NULL;
2843
183
2844
183
  if (map->n > 1)
2845
183
    
isl_die0
(s->ctx, isl_error_invalid,
2846
183
      "set or map description involves "
2847
183
      "more than one disjunct", goto error);
2848
183
2849
183
  if (map->n == 0)
2850
4
    bmap = isl_basic_map_empty(isl_map_get_space(map));
2851
179
  else
2852
179
    bmap = isl_basic_map_copy(map->p[0]);
2853
183
2854
183
  isl_map_free(map);
2855
183
2856
183
  return bmap;
2857
0
error:
2858
0
  obj.type->free(obj.v);
2859
0
  return NULL;
2860
183
}
2861
2862
static __isl_give isl_basic_set *basic_set_read(__isl_keep isl_stream *s)
2863
173
{
2864
173
  isl_basic_map *bmap;
2865
173
  bmap = basic_map_read(s);
2866
173
  if (!bmap)
2867
0
    return NULL;
2868
173
  if (!isl_basic_map_may_be_set(bmap))
2869
173
    
isl_die0
(s->ctx, isl_error_invalid,
2870
173
      "input is not a set", goto error);
2871
173
  return isl_basic_map_range(bmap);
2872
0
error:
2873
0
  isl_basic_map_free(bmap);
2874
0
  return NULL;
2875
173
}
2876
2877
__isl_give isl_basic_map *isl_basic_map_read_from_file(isl_ctx *ctx,
2878
  FILE *input)
2879
2
{
2880
2
  struct isl_basic_map *bmap;
2881
2
  isl_stream *s = isl_stream_new_file(ctx, input);
2882
2
  if (!s)
2883
0
    return NULL;
2884
2
  bmap = basic_map_read(s);
2885
2
  isl_stream_free(s);
2886
2
  return bmap;
2887
2
}
2888
2889
__isl_give isl_basic_set *isl_basic_set_read_from_file(isl_ctx *ctx,
2890
  FILE *input)
2891
110
{
2892
110
  isl_basic_set *bset;
2893
110
  isl_stream *s = isl_stream_new_file(ctx, input);
2894
110
  if (!s)
2895
0
    return NULL;
2896
110
  bset = basic_set_read(s);
2897
110
  isl_stream_free(s);
2898
110
  return bset;
2899
110
}
2900
2901
struct isl_basic_map *isl_basic_map_read_from_str(struct isl_ctx *ctx,
2902
  const char *str)
2903
8
{
2904
8
  struct isl_basic_map *bmap;
2905
8
  isl_stream *s = isl_stream_new_str(ctx, str);
2906
8
  if (!s)
2907
0
    return NULL;
2908
8
  bmap = basic_map_read(s);
2909
8
  isl_stream_free(s);
2910
8
  return bmap;
2911
8
}
2912
2913
struct isl_basic_set *isl_basic_set_read_from_str(struct isl_ctx *ctx,
2914
  const char *str)
2915
63
{
2916
63
  isl_basic_set *bset;
2917
63
  isl_stream *s = isl_stream_new_str(ctx, str);
2918
63
  if (!s)
2919
0
    return NULL;
2920
63
  bset = basic_set_read(s);
2921
63
  isl_stream_free(s);
2922
63
  return bset;
2923
63
}
2924
2925
__isl_give isl_map *isl_map_read_from_file(struct isl_ctx *ctx,
2926
  FILE *input)
2927
0
{
2928
0
  struct isl_map *map;
2929
0
  isl_stream *s = isl_stream_new_file(ctx, input);
2930
0
  if (!s)
2931
0
    return NULL;
2932
0
  map = isl_stream_read_map(s);
2933
0
  isl_stream_free(s);
2934
0
  return map;
2935
0
}
2936
2937
__isl_give isl_map *isl_map_read_from_str(struct isl_ctx *ctx,
2938
  const char *str)
2939
638
{
2940
638
  struct isl_map *map;
2941
638
  isl_stream *s = isl_stream_new_str(ctx, str);
2942
638
  if (!s)
2943
0
    return NULL;
2944
638
  map = isl_stream_read_map(s);
2945
638
  isl_stream_free(s);
2946
638
  return map;
2947
638
}
2948
2949
__isl_give isl_set *isl_set_read_from_file(struct isl_ctx *ctx,
2950
  FILE *input)
2951
0
{
2952
0
  isl_set *set;
2953
0
  isl_stream *s = isl_stream_new_file(ctx, input);
2954
0
  if (!s)
2955
0
    return NULL;
2956
0
  set = isl_stream_read_set(s);
2957
0
  isl_stream_free(s);
2958
0
  return set;
2959
0
}
2960
2961
struct isl_set *isl_set_read_from_str(struct isl_ctx *ctx,
2962
  const char *str)
2963
552
{
2964
552
  isl_set *set;
2965
552
  isl_stream *s = isl_stream_new_str(ctx, str);
2966
552
  if (!s)
2967
0
    return NULL;
2968
552
  set = isl_stream_read_set(s);
2969
552
  isl_stream_free(s);
2970
552
  return set;
2971
552
}
2972
2973
__isl_give isl_union_map *isl_union_map_read_from_file(isl_ctx *ctx,
2974
  FILE *input)
2975
0
{
2976
0
  isl_union_map *umap;
2977
0
  isl_stream *s = isl_stream_new_file(ctx, input);
2978
0
  if (!s)
2979
0
    return NULL;
2980
0
  umap = isl_stream_read_union_map(s);
2981
0
  isl_stream_free(s);
2982
0
  return umap;
2983
0
}
2984
2985
__isl_give isl_union_map *isl_union_map_read_from_str(struct isl_ctx *ctx,
2986
    const char *str)
2987
751
{
2988
751
  isl_union_map *umap;
2989
751
  isl_stream *s = isl_stream_new_str(ctx, str);
2990
751
  if (!s)
2991
0
    return NULL;
2992
751
  umap = isl_stream_read_union_map(s);
2993
751
  isl_stream_free(s);
2994
751
  return umap;
2995
751
}
2996
2997
__isl_give isl_union_set *isl_union_set_read_from_file(isl_ctx *ctx,
2998
  FILE *input)
2999
0
{
3000
0
  isl_union_set *uset;
3001
0
  isl_stream *s = isl_stream_new_file(ctx, input);
3002
0
  if (!s)
3003
0
    return NULL;
3004
0
  uset = isl_stream_read_union_set(s);
3005
0
  isl_stream_free(s);
3006
0
  return uset;
3007
0
}
3008
3009
__isl_give isl_union_set *isl_union_set_read_from_str(struct isl_ctx *ctx,
3010
    const char *str)
3011
321
{
3012
321
  isl_union_set *uset;
3013
321
  isl_stream *s = isl_stream_new_str(ctx, str);
3014
321
  if (!s)
3015
0
    return NULL;
3016
321
  uset = isl_stream_read_union_set(s);
3017
321
  isl_stream_free(s);
3018
321
  return uset;
3019
321
}
3020
3021
static __isl_give isl_vec *isl_vec_read_polylib(__isl_keep isl_stream *s)
3022
0
{
3023
0
  struct isl_vec *vec = NULL;
3024
0
  struct isl_token *tok;
3025
0
  unsigned size;
3026
0
  int j;
3027
0
3028
0
  tok = isl_stream_next_token(s);
3029
0
  if (!tok || tok->type != ISL_TOKEN_VALUE) {
3030
0
    isl_stream_error(s, tok, "expecting vector length");
3031
0
    goto error;
3032
0
  }
3033
0
3034
0
  size = isl_int_get_si(tok->u.v);
3035
0
  isl_token_free(tok);
3036
0
3037
0
  vec = isl_vec_alloc(s->ctx, size);
3038
0
3039
0
  for (j = 0; j < size; ++j) {
3040
0
    tok = isl_stream_next_token(s);
3041
0
    if (!tok || tok->type != ISL_TOKEN_VALUE) {
3042
0
      isl_stream_error(s, tok, "expecting constant value");
3043
0
      goto error;
3044
0
    }
3045
0
    isl_int_set(vec->el[j], tok->u.v);
3046
0
    isl_token_free(tok);
3047
0
  }
3048
0
3049
0
  return vec;
3050
0
error:
3051
0
  isl_token_free(tok);
3052
0
  isl_vec_free(vec);
3053
0
  return NULL;
3054
0
}
3055
3056
static __isl_give isl_vec *vec_read(__isl_keep isl_stream *s)
3057
0
{
3058
0
  return isl_vec_read_polylib(s);
3059
0
}
3060
3061
__isl_give isl_vec *isl_vec_read_from_file(isl_ctx *ctx, FILE *input)
3062
0
{
3063
0
  isl_vec *v;
3064
0
  isl_stream *s = isl_stream_new_file(ctx, input);
3065
0
  if (!s)
3066
0
    return NULL;
3067
0
  v = vec_read(s);
3068
0
  isl_stream_free(s);
3069
0
  return v;
3070
0
}
3071
3072
__isl_give isl_pw_qpolynomial *isl_stream_read_pw_qpolynomial(
3073
  __isl_keep isl_stream *s)
3074
27
{
3075
27
  struct isl_obj obj;
3076
27
3077
27
  obj = obj_read(s);
3078
27
  if (obj.v)
3079
27
    isl_assert(s->ctx, obj.type == isl_obj_pw_qpolynomial,
3080
27
         goto error);
3081
27
3082
27
  return obj.v;
3083
0
error:
3084
0
  obj.type->free(obj.v);
3085
0
  return NULL;
3086
27
}
3087
3088
__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_str(isl_ctx *ctx,
3089
    const char *str)
3090
27
{
3091
27
  isl_pw_qpolynomial *pwqp;
3092
27
  isl_stream *s = isl_stream_new_str(ctx, str);
3093
27
  if (!s)
3094
0
    return NULL;
3095
27
  pwqp = isl_stream_read_pw_qpolynomial(s);
3096
27
  isl_stream_free(s);
3097
27
  return pwqp;
3098
27
}
3099
3100
__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_read_from_file(isl_ctx *ctx,
3101
    FILE *input)
3102
0
{
3103
0
  isl_pw_qpolynomial *pwqp;
3104
0
  isl_stream *s = isl_stream_new_file(ctx, input);
3105
0
  if (!s)
3106
0
    return NULL;
3107
0
  pwqp = isl_stream_read_pw_qpolynomial(s);
3108
0
  isl_stream_free(s);
3109
0
  return pwqp;
3110
0
}
3111
3112
/* Is the next token an identifer not in "v"?
3113
 */
3114
static int next_is_fresh_ident(__isl_keep isl_stream *s, struct vars *v)
3115
68
{
3116
68
  int n = v->n;
3117
68
  int fresh;
3118
68
  struct isl_token *tok;
3119
68
3120
68
  tok = isl_stream_next_token(s);
3121
68
  if (!tok)
3122
0
    return 0;
3123
68
  fresh = tok->type == ISL_TOKEN_IDENT && 
vars_pos(v, tok->u.s, -1) >= n60
;
3124
68
  isl_stream_push_token(s, tok);
3125
68
3126
68
  vars_drop(v, v->n - n);
3127
68
3128
68
  return fresh;
3129
68
}
3130
3131
/* First read the domain of the affine expression, which may be
3132
 * a parameter space or a set.
3133
 * The tricky part is that we don't know if the domain is a set or not,
3134
 * so when we are trying to read the domain, we may actually be reading
3135
 * the affine expression itself (defined on a parameter domains)
3136
 * If the tuple we are reading is named, we assume it's the domain.
3137
 * Also, if inside the tuple, the first thing we find is a nested tuple
3138
 * or a new identifier, we again assume it's the domain.
3139
 * Finally, if the tuple is empty, then it must be the domain
3140
 * since it does not contain an affine expression.
3141
 * Otherwise, we assume we are reading an affine expression.
3142
 */
3143
static __isl_give isl_set *read_aff_domain(__isl_keep isl_stream *s,
3144
  __isl_take isl_set *dom, struct vars *v)
3145
297
{
3146
297
  struct isl_token *tok, *tok2;
3147
297
  int is_empty;
3148
297
3149
297
  tok = isl_stream_next_token(s);
3150
297
  if (tok && (tok->type == ISL_TOKEN_IDENT || 
tok->is_keyword69
)) {
3151
228
    isl_stream_push_token(s, tok);
3152
228
    return read_map_tuple(s, dom, isl_dim_set, v, 0, 0);
3153
228
  }
3154
69
  if (!tok || tok->type != '[') {
3155
0
    isl_stream_error(s, tok, "expecting '['");
3156
0
    goto error;
3157
0
  }
3158
69
  tok2 = isl_stream_next_token(s);
3159
69
  is_empty = tok2 && tok2->type == ']';
3160
69
  if (tok2)
3161
69
    isl_stream_push_token(s, tok2);
3162
69
  if (is_empty || 
next_is_tuple(s)68
||
next_is_fresh_ident(s, v)68
) {
3163
49
    isl_stream_push_token(s, tok);
3164
49
    dom = read_map_tuple(s, dom, isl_dim_set, v, 0, 0);
3165
49
  } else
3166
20
    isl_stream_push_token(s, tok);
3167
69
3168
69
  return dom;
3169
0
error:
3170
0
  if (tok)
3171
0
    isl_stream_push_token(s, tok);
3172
0
  isl_set_free(dom);
3173
0
  return NULL;
3174
69
}
3175
3176
/* Read an affine expression from "s".
3177
 */
3178
__isl_give isl_aff *isl_stream_read_aff(__isl_keep isl_stream *s)
3179
67
{
3180
67
  isl_aff *aff;
3181
67
  isl_multi_aff *ma;
3182
67
3183
67
  ma = isl_stream_read_multi_aff(s);
3184
67
  if (!ma)
3185
0
    return NULL;
3186
67
  if (isl_multi_aff_dim(ma, isl_dim_out) != 1)
3187
67
    
isl_die0
(s->ctx, isl_error_invalid,
3188
67
      "expecting single affine expression",
3189
67
      goto error);
3190
67
3191
67
  aff = isl_multi_aff_get_aff(ma, 0);
3192
67
  isl_multi_aff_free(ma);
3193
67
  return aff;
3194
0
error:
3195
0
  isl_multi_aff_free(ma);
3196
0
  return NULL;
3197
67
}
3198
3199
/* Read a piecewise affine expression from "s" with domain (space) "dom".
3200
 */
3201
static __isl_give isl_pw_aff *read_pw_aff_with_dom(__isl_keep isl_stream *s,
3202
  __isl_take isl_set *dom, struct vars *v)
3203
297
{
3204
297
  isl_pw_aff *pwaff = NULL;
3205
297
3206
297
  if (!isl_set_is_params(dom) && 
isl_stream_eat(s, ISL_TOKEN_TO)277
)
3207
0
    goto error;
3208
297
3209
297
  if (isl_stream_eat(s, '['))
3210
0
    goto error;
3211
297
3212
297
  pwaff = accept_affine(s, isl_set_get_space(dom), v);
3213
297
3214
297
  if (isl_stream_eat(s, ']'))
3215
0
    goto error;
3216
297
3217
297
  dom = read_optional_formula(s, dom, v, 0);
3218
297
  pwaff = isl_pw_aff_intersect_domain(pwaff, dom);
3219
297
3220
297
  return pwaff;
3221
0
error:
3222
0
  isl_set_free(dom);
3223
0
  isl_pw_aff_free(pwaff);
3224
0
  return NULL;
3225
297
}
3226
3227
__isl_give isl_pw_aff *isl_stream_read_pw_aff(__isl_keep isl_stream *s)
3228
57
{
3229
57
  struct vars *v;
3230
57
  isl_set *dom = NULL;
3231
57
  isl_set *aff_dom;
3232
57
  isl_pw_aff *pa = NULL;
3233
57
  int n;
3234
57
3235
57
  v = vars_new(s->ctx);
3236
57
  if (!v)
3237
0
    return NULL;
3238
57
3239
57
  dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3240
57
  if (next_is_tuple(s)) {
3241
12
    dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3242
12
    if (isl_stream_eat(s, ISL_TOKEN_TO))
3243
0
      goto error;
3244
57
  }
3245
57
  if (isl_stream_eat(s, '{'))
3246
0
    goto error;
3247
57
3248
57
  n = v->n;
3249
57
  aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
3250
57
  pa = read_pw_aff_with_dom(s, aff_dom, v);
3251
57
  vars_drop(v, v->n - n);
3252
57
3253
68
  while (isl_stream_eat_if_available(s, ';')) {
3254
11
    isl_pw_aff *pa_i;
3255
11
3256
11
    n = v->n;
3257
11
    aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
3258
11
    pa_i = read_pw_aff_with_dom(s, aff_dom, v);
3259
11
    vars_drop(v, v->n - n);
3260
11
3261
11
    pa = isl_pw_aff_union_add(pa, pa_i);
3262
11
  }
3263
57
3264
57
  if (isl_stream_eat(s, '}'))
3265
0
    goto error;
3266
57
3267
57
  vars_free(v);
3268
57
  isl_set_free(dom);
3269
57
  return pa;
3270
0
error:
3271
0
  vars_free(v);
3272
0
  isl_set_free(dom);
3273
0
  isl_pw_aff_free(pa);
3274
0
  return NULL;
3275
57
}
3276
3277
__isl_give isl_aff *isl_aff_read_from_str(isl_ctx *ctx, const char *str)
3278
67
{
3279
67
  isl_aff *aff;
3280
67
  isl_stream *s = isl_stream_new_str(ctx, str);
3281
67
  if (!s)
3282
0
    return NULL;
3283
67
  aff = isl_stream_read_aff(s);
3284
67
  isl_stream_free(s);
3285
67
  return aff;
3286
67
}
3287
3288
__isl_give isl_pw_aff *isl_pw_aff_read_from_str(isl_ctx *ctx, const char *str)
3289
57
{
3290
57
  isl_pw_aff *pa;
3291
57
  isl_stream *s = isl_stream_new_str(ctx, str);
3292
57
  if (!s)
3293
0
    return NULL;
3294
57
  pa = isl_stream_read_pw_aff(s);
3295
57
  isl_stream_free(s);
3296
57
  return pa;
3297
57
}
3298
3299
/* Extract an isl_multi_pw_aff with domain space "dom_space"
3300
 * from a tuple "tuple" read by read_tuple.
3301
 *
3302
 * Note that the function read_tuple accepts tuples where some output or
3303
 * set dimensions are defined in terms of other output or set dimensions
3304
 * since this function is also used to read maps.  As a special case,
3305
 * read_tuple also accept dimensions that are defined in terms of themselves
3306
 * (i.e., that are not defined).
3307
 * These cases are not allowed when extracting an isl_multi_pw_aff so check
3308
 * that the definitions of the output/set dimensions do not involve any
3309
 * output/set dimensions.
3310
 * Finally, drop the output dimensions from the domain of the result
3311
 * of read_tuple (which is of the form [input, output] -> [output],
3312
 * with anonymous domain) and reset the space.
3313
 */
3314
static __isl_give isl_multi_pw_aff *extract_mpa_from_tuple(
3315
  __isl_take isl_space *dom_space, __isl_keep isl_multi_pw_aff *tuple)
3316
210
{
3317
210
  int dim, i, n;
3318
210
  isl_space *space;
3319
210
  isl_multi_pw_aff *mpa;
3320
210
3321
210
  n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
3322
210
  dim = isl_space_dim(dom_space, isl_dim_all);
3323
210
  space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3324
210
  space = isl_space_align_params(space, isl_space_copy(dom_space));
3325
210
  if (!isl_space_is_params(dom_space))
3326
160
    space = isl_space_map_from_domain_and_range(
3327
160
        isl_space_copy(dom_space), space);
3328
210
  isl_space_free(dom_space);
3329
210
  mpa = isl_multi_pw_aff_alloc(space);
3330
210
3331
429
  for (i = 0; i < n; 
++i219
) {
3332
219
    isl_pw_aff *pa;
3333
219
    pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
3334
219
    if (!pa)
3335
0
      return isl_multi_pw_aff_free(mpa);
3336
219
    if (isl_pw_aff_involves_dims(pa, isl_dim_in, dim, i + 1)) {
3337
0
      isl_ctx *ctx = isl_pw_aff_get_ctx(pa);
3338
0
      isl_pw_aff_free(pa);
3339
0
      isl_die(ctx, isl_error_invalid,
3340
0
        "not an affine expression",
3341
0
        return isl_multi_pw_aff_free(mpa));
3342
0
    }
3343
219
    pa = isl_pw_aff_drop_dims(pa, isl_dim_in, dim, n);
3344
219
    space = isl_multi_pw_aff_get_domain_space(mpa);
3345
219
    pa = isl_pw_aff_reset_domain_space(pa, space);
3346
219
    mpa = isl_multi_pw_aff_set_pw_aff(mpa, i, pa);
3347
219
  }
3348
210
3349
210
  return mpa;
3350
210
}
3351
3352
/* Read a tuple of affine expressions, together with optional constraints
3353
 * on the domain from "s".  "dom" represents the initial constraints
3354
 * on the domain.
3355
 *
3356
 * The isl_multi_aff may live in either a set or a map space.
3357
 * First read the first tuple and check if it is followed by a "->".
3358
 * If so, convert the tuple into the domain of the isl_multi_pw_aff and
3359
 * read in the next tuple.  This tuple (or the first tuple if it was
3360
 * not followed by a "->") is then converted into an isl_multi_pw_aff
3361
 * through a call to extract_mpa_from_tuple.
3362
 * The result is converted to an isl_pw_multi_aff and
3363
 * its domain is intersected with the domain.
3364
 */
3365
static __isl_give isl_pw_multi_aff *read_conditional_multi_aff(
3366
  __isl_keep isl_stream *s, __isl_take isl_set *dom, struct vars *v)
3367
68
{
3368
68
  isl_multi_pw_aff *tuple;
3369
68
  isl_multi_pw_aff *mpa;
3370
68
  isl_pw_multi_aff *pma;
3371
68
  int n = v->n;
3372
68
3373
68
  tuple = read_tuple(s, v, 0, 0);
3374
68
  if (!tuple)
3375
0
    goto error;
3376
68
  if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {
3377
34
    isl_map *map = map_from_tuple(tuple, dom, isl_dim_in, v, 0);
3378
34
    dom = isl_map_domain(map);
3379
34
    tuple = read_tuple(s, v, 0, 0);
3380
34
    if (!tuple)
3381
0
      goto error;
3382
68
  }
3383
68
3384
68
  dom = read_optional_formula(s, dom, v, 0);
3385
68
3386
68
  vars_drop(v, v->n - n);
3387
68
3388
68
  mpa = extract_mpa_from_tuple(isl_set_get_space(dom), tuple);
3389
68
  isl_multi_pw_aff_free(tuple);
3390
68
  pma = isl_pw_multi_aff_from_multi_pw_aff(mpa);
3391
68
  pma = isl_pw_multi_aff_intersect_domain(pma, dom);
3392
68
3393
68
  return pma;
3394
0
error:
3395
0
  isl_set_free(dom);
3396
0
  return NULL;
3397
68
}
3398
3399
/* Read an isl_pw_multi_aff from "s".
3400
 *
3401
 * In particular, first read the parameters and then read a sequence
3402
 * of one or more tuples of affine expressions with optional conditions and
3403
 * add them up.
3404
 */
3405
__isl_give isl_pw_multi_aff *isl_stream_read_pw_multi_aff(
3406
  __isl_keep isl_stream *s)
3407
60
{
3408
60
  struct vars *v;
3409
60
  isl_set *dom;
3410
60
  isl_pw_multi_aff *pma = NULL;
3411
60
3412
60
  v = vars_new(s->ctx);
3413
60
  if (!v)
3414
0
    return NULL;
3415
60
3416
60
  dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3417
60
  if (next_is_tuple(s)) {
3418
34
    dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3419
34
    if (isl_stream_eat(s, ISL_TOKEN_TO))
3420
0
      goto error;
3421
60
  }
3422
60
  if (isl_stream_eat(s, '{'))
3423
0
    goto error;
3424
60
3425
60
  pma = read_conditional_multi_aff(s, isl_set_copy(dom), v);
3426
60
3427
68
  while (isl_stream_eat_if_available(s, ';')) {
3428
8
    isl_pw_multi_aff *pma2;
3429
8
3430
8
    pma2 = read_conditional_multi_aff(s, isl_set_copy(dom), v);
3431
8
    pma = isl_pw_multi_aff_union_add(pma, pma2);
3432
8
    if (!pma)
3433
0
      goto error;
3434
8
  }
3435
60
3436
60
  if (isl_stream_eat(s, '}'))
3437
0
    goto error;
3438
60
3439
60
  isl_set_free(dom);
3440
60
  vars_free(v);
3441
60
  return pma;
3442
0
error:
3443
0
  isl_pw_multi_aff_free(pma);
3444
0
  isl_set_free(dom);
3445
0
  vars_free(v);
3446
0
  return NULL;
3447
60
}
3448
3449
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(isl_ctx *ctx,
3450
  const char *str)
3451
60
{
3452
60
  isl_pw_multi_aff *pma;
3453
60
  isl_stream *s = isl_stream_new_str(ctx, str);
3454
60
  if (!s)
3455
0
    return NULL;
3456
60
  pma = isl_stream_read_pw_multi_aff(s);
3457
60
  isl_stream_free(s);
3458
60
  return pma;
3459
60
}
3460
3461
/* Read an isl_union_pw_multi_aff from "s".
3462
 * We currently read a generic object and if it turns out to be a set or
3463
 * a map, we convert that to an isl_union_pw_multi_aff.
3464
 * It would be more efficient if we were to construct
3465
 * the isl_union_pw_multi_aff directly.
3466
 */
3467
__isl_give isl_union_pw_multi_aff *isl_stream_read_union_pw_multi_aff(
3468
  __isl_keep isl_stream *s)
3469
36
{
3470
36
  struct isl_obj obj;
3471
36
3472
36
  obj = obj_read(s);
3473
36
  if (!obj.v)
3474
0
    return NULL;
3475
36
3476
36
  if (obj.type == isl_obj_map || 
obj.type == 7
isl_obj_set7
)
3477
36
    
obj = to_union(s->ctx, obj)29
;
3478
36
  if (obj.type == isl_obj_union_map)
3479
36
    
return isl_union_pw_multi_aff_from_union_map(obj.v)35
;
3480
1
  if (obj.type == isl_obj_union_set)
3481
1
    return isl_union_pw_multi_aff_from_union_set(obj.v);
3482
0
3483
0
  obj.type->free(obj.v);
3484
0
  isl_die(s->ctx, isl_error_invalid, "unexpected object type",
3485
0
    return NULL);
3486
0
}
3487
3488
/* Read an isl_union_pw_multi_aff from "str".
3489
 */
3490
__isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_read_from_str(
3491
  isl_ctx *ctx, const char *str)
3492
36
{
3493
36
  isl_union_pw_multi_aff *upma;
3494
36
  isl_stream *s = isl_stream_new_str(ctx, str);
3495
36
  if (!s)
3496
0
    return NULL;
3497
36
  upma = isl_stream_read_union_pw_multi_aff(s);
3498
36
  isl_stream_free(s);
3499
36
  return upma;
3500
36
}
3501
3502
/* Assuming "pa" represents a single affine expression defined on a universe
3503
 * domain, extract this affine expression.
3504
 */
3505
static __isl_give isl_aff *aff_from_pw_aff(__isl_take isl_pw_aff *pa)
3506
140
{
3507
140
  isl_aff *aff;
3508
140
3509
140
  if (!pa)
3510
0
    return NULL;
3511
140
  if (pa->n != 1)
3512
140
    
isl_die0
(isl_pw_aff_get_ctx(pa), isl_error_invalid,
3513
140
      "expecting single affine expression",
3514
140
      goto error);
3515
140
  if (!isl_set_plain_is_universe(pa->p[0].set))
3516
140
    
isl_die0
(isl_pw_aff_get_ctx(pa), isl_error_invalid,
3517
140
      "expecting universe domain",
3518
140
      goto error);
3519
140
3520
140
  aff = isl_aff_copy(pa->p[0].aff);
3521
140
  isl_pw_aff_free(pa);
3522
140
  return aff;
3523
0
error:
3524
0
  isl_pw_aff_free(pa);
3525
0
  return NULL;
3526
140
}
3527
3528
/* This function is called for each element in a tuple inside
3529
 * isl_stream_read_multi_val.
3530
 * Read an isl_val from "s" and add it to *list.
3531
 */
3532
static __isl_give isl_space *read_val_el(__isl_keep isl_stream *s,
3533
  struct vars *v, __isl_take isl_space *space, int rational, void *user)
3534
17
{
3535
17
  isl_val_list **list = (isl_val_list **) user;
3536
17
  isl_val *val;
3537
17
3538
17
  val = isl_stream_read_val(s);
3539
17
  *list = isl_val_list_add(*list, val);
3540
17
  if (!*list)
3541
0
    return isl_space_free(space);
3542
17
3543
17
  return space;
3544
17
}
3545
3546
/* Read an isl_multi_val from "s".
3547
 *
3548
 * We first read a tuple space, collecting the element values in a list.
3549
 * Then we create an isl_multi_val from the space and the isl_val_list.
3550
 */
3551
__isl_give isl_multi_val *isl_stream_read_multi_val(__isl_keep isl_stream *s)
3552
7
{
3553
7
  struct vars *v;
3554
7
  isl_set *dom = NULL;
3555
7
  isl_space *space;
3556
7
  isl_multi_val *mv = NULL;
3557
7
  isl_val_list *list;
3558
7
3559
7
  v = vars_new(s->ctx);
3560
7
  if (!v)
3561
0
    return NULL;
3562
7
3563
7
  dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3564
7
  if (next_is_tuple(s)) {
3565
1
    dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3566
1
    if (isl_stream_eat(s, ISL_TOKEN_TO))
3567
0
      goto error;
3568
7
  }
3569
7
  if (!isl_set_plain_is_universe(dom))
3570
7
    
isl_die0
(s->ctx, isl_error_invalid,
3571
7
      "expecting universe parameter domain", goto error);
3572
7
  if (isl_stream_eat(s, '{'))
3573
0
    goto error;
3574
7
3575
7
  space = isl_set_get_space(dom);
3576
7
3577
7
  list = isl_val_list_alloc(s->ctx, 0);
3578
7
  space = read_tuple_space(s, v, space, 1, 0, &read_val_el, &list);
3579
7
  mv = isl_multi_val_from_val_list(space, list);
3580
7
3581
7
  if (isl_stream_eat(s, '}'))
3582
0
    goto error;
3583
7
3584
7
  vars_free(v);
3585
7
  isl_set_free(dom);
3586
7
  return mv;
3587
0
error:
3588
0
  vars_free(v);
3589
0
  isl_set_free(dom);
3590
0
  isl_multi_val_free(mv);
3591
0
  return NULL;
3592
7
}
3593
3594
/* Read an isl_multi_val from "str".
3595
 */
3596
__isl_give isl_multi_val *isl_multi_val_read_from_str(isl_ctx *ctx,
3597
  const char *str)
3598
7
{
3599
7
  isl_multi_val *mv;
3600
7
  isl_stream *s = isl_stream_new_str(ctx, str);
3601
7
  if (!s)
3602
0
    return NULL;
3603
7
  mv = isl_stream_read_multi_val(s);
3604
7
  isl_stream_free(s);
3605
7
  return mv;
3606
7
}
3607
3608
/* Read a multi-affine expression from "s".
3609
 * If the multi-affine expression has a domain, then the tuple
3610
 * representing this domain cannot involve any affine expressions.
3611
 * The tuple representing the actual expressions needs to consist
3612
 * of only affine expressions.  Moreover, these expressions can
3613
 * only depend on parameters and input dimensions and not on other
3614
 * output dimensions.
3615
 */
3616
__isl_give isl_multi_aff *isl_stream_read_multi_aff(__isl_keep isl_stream *s)
3617
130
{
3618
130
  struct vars *v;
3619
130
  isl_set *dom = NULL;
3620
130
  isl_multi_pw_aff *tuple = NULL;
3621
130
  int dim, i, n;
3622
130
  isl_space *space, *dom_space;
3623
130
  isl_multi_aff *ma = NULL;
3624
130
3625
130
  v = vars_new(s->ctx);
3626
130
  if (!v)
3627
0
    return NULL;
3628
130
3629
130
  dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3630
130
  if (next_is_tuple(s)) {
3631
11
    dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3632
11
    if (isl_stream_eat(s, ISL_TOKEN_TO))
3633
0
      goto error;
3634
130
  }
3635
130
  if (!isl_set_plain_is_universe(dom))
3636
130
    
isl_die0
(s->ctx, isl_error_invalid,
3637
130
      "expecting universe parameter domain", goto error);
3638
130
  if (isl_stream_eat(s, '{'))
3639
0
    goto error;
3640
130
3641
130
  tuple = read_tuple(s, v, 0, 0);
3642
130
  if (!tuple)
3643
0
    goto error;
3644
130
  if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {
3645
122
    isl_set *set;
3646
122
    isl_space *space;
3647
122
    int has_expr;
3648
122
3649
122
    has_expr = tuple_has_expr(tuple);
3650
122
    if (has_expr < 0)
3651
0
      goto error;
3652
122
    if (has_expr)
3653
122
      
isl_die0
(s->ctx, isl_error_invalid,
3654
122
        "expecting universe domain", goto error);
3655
122
    space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3656
122
    set = isl_set_universe(space);
3657
122
    dom = isl_set_intersect_params(set, dom);
3658
122
    isl_multi_pw_aff_free(tuple);
3659
122
    tuple = read_tuple(s, v, 0, 0);
3660
122
    if (!tuple)
3661
0
      goto error;
3662
130
  }
3663
130
3664
130
  if (isl_stream_eat(s, '}'))
3665
0
    goto error;
3666
130
3667
130
  n = isl_multi_pw_aff_dim(tuple, isl_dim_out);
3668
130
  dim = isl_set_dim(dom, isl_dim_all);
3669
130
  dom_space = isl_set_get_space(dom);
3670
130
  space = isl_space_range(isl_multi_pw_aff_get_space(tuple));
3671
130
  space = isl_space_align_params(space, isl_space_copy(dom_space));
3672
130
  if (!isl_space_is_params(dom_space))
3673
122
    space = isl_space_map_from_domain_and_range(
3674
122
        isl_space_copy(dom_space), space);
3675
130
  isl_space_free(dom_space);
3676
130
  ma = isl_multi_aff_alloc(space);
3677
130
3678
270
  for (i = 0; i < n; 
++i140
) {
3679
140
    isl_pw_aff *pa;
3680
140
    isl_aff *aff;
3681
140
    pa = isl_multi_pw_aff_get_pw_aff(tuple, i);
3682
140
    aff = aff_from_pw_aff(pa);
3683
140
    if (!aff)
3684
0
      goto error;
3685
140
    if (isl_aff_involves_dims(aff, isl_dim_in, dim, i + 1)) {
3686
0
      isl_aff_free(aff);
3687
0
      isl_die(s->ctx, isl_error_invalid,
3688
0
        "not an affine expression", goto error);
3689
0
    }
3690
140
    aff = isl_aff_drop_dims(aff, isl_dim_in, dim, n);
3691
140
    space = isl_multi_aff_get_domain_space(ma);
3692
140
    aff = isl_aff_reset_domain_space(aff, space);
3693
140
    ma = isl_multi_aff_set_aff(ma, i, aff);
3694
140
  }
3695
130
3696
130
  isl_multi_pw_aff_free(tuple);
3697
130
  vars_free(v);
3698
130
  isl_set_free(dom);
3699
130
  return ma;
3700
0
error:
3701
0
  isl_multi_pw_aff_free(tuple);
3702
0
  vars_free(v);
3703
0
  isl_set_free(dom);
3704
0
  isl_multi_aff_free(ma);
3705
0
  return NULL;
3706
130
}
3707
3708
__isl_give isl_multi_aff *isl_multi_aff_read_from_str(isl_ctx *ctx,
3709
  const char *str)
3710
63
{
3711
63
  isl_multi_aff *maff;
3712
63
  isl_stream *s = isl_stream_new_str(ctx, str);
3713
63
  if (!s)
3714
0
    return NULL;
3715
63
  maff = isl_stream_read_multi_aff(s);
3716
63
  isl_stream_free(s);
3717
63
  return maff;
3718
63
}
3719
3720
/* Read an isl_multi_pw_aff from "s".
3721
 *
3722
 * The input format is similar to that of map, except that any conditions
3723
 * on the domains should be specified inside the tuple since each
3724
 * piecewise affine expression may have a different domain.
3725
 * However, additional, shared conditions can also be specified.
3726
 * This is especially useful for setting the explicit domain
3727
 * of a zero-dimensional isl_multi_pw_aff.
3728
 *
3729
 * Since we do not know in advance if the isl_multi_pw_aff lives
3730
 * in a set or a map space, we first read the first tuple and check
3731
 * if it is followed by a "->".  If so, we convert the tuple into
3732
 * the domain of the isl_multi_pw_aff and read in the next tuple.
3733
 * This tuple (or the first tuple if it was not followed by a "->")
3734
 * is then converted into the isl_multi_pw_aff through a call
3735
 * to extract_mpa_from_tuple and the domain of the result
3736
 * is intersected with the domain.
3737
 */
3738
__isl_give isl_multi_pw_aff *isl_stream_read_multi_pw_aff(
3739
  __isl_keep isl_stream *s)
3740
142
{
3741
142
  struct vars *v;
3742
142
  isl_set *dom = NULL;
3743
142
  isl_multi_pw_aff *tuple = NULL;
3744
142
  isl_multi_pw_aff *mpa = NULL;
3745
142
3746
142
  v = vars_new(s->ctx);
3747
142
  if (!v)
3748
0
    return NULL;
3749
142
3750
142
  dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3751
142
  if (next_is_tuple(s)) {
3752
32
    dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3753
32
    if (isl_stream_eat(s, ISL_TOKEN_TO))
3754
0
      goto error;
3755
142
  }
3756
142
  if (isl_stream_eat(s, '{'))
3757
0
    goto error;
3758
142
3759
142
  tuple = read_tuple(s, v, 0, 0);
3760
142
  if (!tuple)
3761
0
    goto error;
3762
142
  if (isl_stream_eat_if_available(s, ISL_TOKEN_TO)) {
3763
126
    isl_map *map = map_from_tuple(tuple, dom, isl_dim_in, v, 0);
3764
126
    dom = isl_map_domain(map);
3765
126
    tuple = read_tuple(s, v, 0, 0);
3766
126
    if (!tuple)
3767
0
      goto error;
3768
142
  }
3769
142
3770
142
  if (isl_stream_eat_if_available(s, ':'))
3771
63
    dom = read_formula(s, v, dom, 0);
3772
142
3773
142
  if (isl_stream_eat(s, '}'))
3774
0
    goto error;
3775
142
3776
142
  mpa = extract_mpa_from_tuple(isl_set_get_space(dom), tuple);
3777
142
3778
142
  isl_multi_pw_aff_free(tuple);
3779
142
  vars_free(v);
3780
142
  mpa = isl_multi_pw_aff_intersect_domain(mpa, dom);
3781
142
  return mpa;
3782
0
error:
3783
0
  isl_multi_pw_aff_free(tuple);
3784
0
  vars_free(v);
3785
0
  isl_set_free(dom);
3786
0
  isl_multi_pw_aff_free(mpa);
3787
0
  return NULL;
3788
142
}
3789
3790
/* Read an isl_multi_pw_aff from "str".
3791
 */
3792
__isl_give isl_multi_pw_aff *isl_multi_pw_aff_read_from_str(isl_ctx *ctx,
3793
  const char *str)
3794
142
{
3795
142
  isl_multi_pw_aff *mpa;
3796
142
  isl_stream *s = isl_stream_new_str(ctx, str);
3797
142
  if (!s)
3798
0
    return NULL;
3799
142
  mpa = isl_stream_read_multi_pw_aff(s);
3800
142
  isl_stream_free(s);
3801
142
  return mpa;
3802
142
}
3803
3804
/* Read the body of an isl_union_pw_aff from "s" with parameter domain "dom".
3805
 */
3806
static __isl_give isl_union_pw_aff *read_union_pw_aff_with_dom(
3807
  __isl_keep isl_stream *s, __isl_take isl_set *dom, struct vars *v)
3808
155
{
3809
155
  isl_pw_aff *pa;
3810
155
  isl_union_pw_aff *upa = NULL;
3811
155
  isl_set *aff_dom;
3812
155
  int n;
3813
155
3814
155
  n = v->n;
3815
155
  aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
3816
155
  pa = read_pw_aff_with_dom(s, aff_dom, v);
3817
155
  vars_drop(v, v->n - n);
3818
155
3819
155
  upa = isl_union_pw_aff_from_pw_aff(pa);
3820
155
3821
229
  while (isl_stream_eat_if_available(s, ';')) {
3822
74
    isl_pw_aff *pa_i;
3823
74
    isl_union_pw_aff *upa_i;
3824
74
3825
74
    n = v->n;
3826
74
    aff_dom = read_aff_domain(s, isl_set_copy(dom), v);
3827
74
    pa_i = read_pw_aff_with_dom(s, aff_dom, v);
3828
74
    vars_drop(v, v->n - n);
3829
74
3830
74
    upa_i = isl_union_pw_aff_from_pw_aff(pa_i);
3831
74
    upa = isl_union_pw_aff_union_add(upa, upa_i);
3832
74
  }
3833
155
3834
155
  isl_set_free(dom);
3835
155
  return upa;
3836
155
}
3837
3838
/* Read an isl_union_pw_aff from "s".
3839
 *
3840
 * First check if there are any paramters, then read in the opening brace
3841
 * and use read_union_pw_aff_with_dom to read in the body of
3842
 * the isl_union_pw_aff.  Finally, read the closing brace.
3843
 */
3844
__isl_give isl_union_pw_aff *isl_stream_read_union_pw_aff(
3845
  __isl_keep isl_stream *s)
3846
11
{
3847
11
  struct vars *v;
3848
11
  isl_set *dom;
3849
11
  isl_union_pw_aff *upa = NULL;
3850
11
3851
11
  v = vars_new(s->ctx);
3852
11
  if (!v)
3853
0
    return NULL;
3854
11
3855
11
  dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
3856
11
  if (next_is_tuple(s)) {
3857
10
    dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
3858
10
    if (isl_stream_eat(s, ISL_TOKEN_TO))
3859
0
      goto error;
3860
11
  }
3861
11
  if (isl_stream_eat(s, '{'))
3862
0
    goto error;
3863
11
3864
11
  upa = read_union_pw_aff_with_dom(s, isl_set_copy(dom), v);
3865
11
3866
11
  if (isl_stream_eat(s, '}'))
3867
0
    goto error;
3868
11
3869
11
  vars_free(v);
3870
11
  isl_set_free(dom);
3871
11
  return upa;
3872
0
error:
3873
0
  vars_free(v);
3874
0
  isl_set_free(dom);
3875
0
  isl_union_pw_aff_free(upa);
3876
0
  return NULL;
3877
11
}
3878
3879
/* Read an isl_union_pw_aff from "str".
3880
 */
3881
__isl_give isl_union_pw_aff *isl_union_pw_aff_read_from_str(isl_ctx *ctx,
3882
  const char *str)
3883
11
{
3884
11
  isl_union_pw_aff *upa;
3885
11
  isl_stream *s = isl_stream_new_str(ctx, str);
3886
11
  if (!s)
3887
0
    return NULL;
3888
11
  upa = isl_stream_read_union_pw_aff(s);
3889
11
  isl_stream_free(s);
3890
11
  return upa;
3891
11
}
3892
3893
/* This function is called for each element in a tuple inside
3894
 * isl_stream_read_multi_union_pw_aff.
3895
 *
3896
 * Read a '{', the union piecewise affine expression body and a '}' and
3897
 * add the isl_union_pw_aff to *list.
3898
 */
3899
static __isl_give isl_space *read_union_pw_aff_el(__isl_keep isl_stream *s,
3900
  struct vars *v, __isl_take isl_space *space, int rational, void *user)
3901
144
{
3902
144
  isl_set *dom;
3903
144
  isl_union_pw_aff *upa;
3904
144
  isl_union_pw_aff_list **list = (isl_union_pw_aff_list **) user;
3905
144
3906
144
  dom = isl_set_universe(isl_space_params(isl_space_copy(space)));
3907
144
  if (isl_stream_eat(s, '{'))
3908
0
    goto error;
3909
144
  upa = read_union_pw_aff_with_dom(s, dom, v);
3910
144
  *list = isl_union_pw_aff_list_add(*list, upa);
3911
144
  if (isl_stream_eat(s, '}'))
3912
0
    return isl_space_free(space);
3913
144
  if (!*list)
3914
0
    return isl_space_free(space);
3915
144
  return space;
3916
0
error:
3917
0
  isl_set_free(dom);
3918
0
  return isl_space_free(space);
3919
144
}
3920
3921
/* Do the next tokens in "s" correspond to an empty tuple?
3922
 * In particular, does the stream start with a '[', followed by a ']',
3923
 * not followed by a "->"?
3924
 */
3925
static int next_is_empty_tuple(__isl_keep isl_stream *s)
3926
272
{
3927
272
  struct isl_token *tok, *tok2, *tok3;
3928
272
  int is_empty_tuple = 0;
3929
272
3930
272
  tok = isl_stream_next_token(s);
3931
272
  if (!tok)
3932
0
    return 0;
3933
272
  if (tok->type != '[') {
3934
122
    isl_stream_push_token(s, tok);
3935
122
    return 0;
3936
122
  }
3937
150
3938
150
  tok2 = isl_stream_next_token(s);
3939
150
  if (tok2 && tok2->type == ']') {
3940
12
    tok3 = isl_stream_next_token(s);
3941
12
    is_empty_tuple = !tok || tok->type != ISL_TOKEN_TO;
3942
12
    if (tok3)
3943
10
      isl_stream_push_token(s, tok3);
3944
12
  }
3945
150
  if (tok2)
3946
150
    isl_stream_push_token(s, tok2);
3947
150
  isl_stream_push_token(s, tok);
3948
150
3949
150
  return is_empty_tuple;
3950
150
}
3951
3952
/* Do the next tokens in "s" correspond to a tuple of parameters?
3953
 * In particular, does the stream start with a '[' that is not
3954
 * followed by a '{' or a nested tuple?
3955
 */
3956
static int next_is_param_tuple(__isl_keep isl_stream *s)
3957
260
{
3958
260
  struct isl_token *tok, *tok2;
3959
260
  int is_tuple;
3960
260
3961
260
  tok = isl_stream_next_token(s);
3962
260
  if (!tok)
3963
0
    return 0;
3964
260
  if (tok->type != '[' || 
next_is_tuple(s)138
) {
3965
134
    isl_stream_push_token(s, tok);
3966
134
    return 0;
3967
134
  }
3968
126
3969
126
  tok2 = isl_stream_next_token(s);
3970
126
  is_tuple = tok2 && tok2->type != '{';
3971
126
  if (tok2)
3972
126
    isl_stream_push_token(s, tok2);
3973
126
  isl_stream_push_token(s, tok);
3974
126
3975
126
  return is_tuple;
3976
126
}
3977
3978
/* Read the core of a body of an isl_multi_union_pw_aff from "s",
3979
 * i.e., everything except the parameter specification and
3980
 * without shared domain constraints.
3981
 * "v" contains a description of the identifiers parsed so far.
3982
 * The parameters, if any, are specified by "space".
3983
 *
3984
 * The body is of the form
3985
 *
3986
 *  [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
3987
 *
3988
 * Read the tuple, collecting the individual isl_union_pw_aff
3989
 * elements in a list and construct the result from the tuple space and
3990
 * the list.
3991
 */
3992
static __isl_give isl_multi_union_pw_aff *read_multi_union_pw_aff_body_core(
3993
  __isl_keep isl_stream *s, struct vars *v, __isl_take isl_space *space)
3994
260
{
3995
260
  isl_union_pw_aff_list *list;
3996
260
  isl_multi_union_pw_aff *mupa;
3997
260
3998
260
  list = isl_union_pw_aff_list_alloc(s->ctx, 0);
3999
260
  space = read_tuple_space(s, v, space, 1, 0,
4000
260
        &read_union_pw_aff_el, &list);
4001
260
  mupa = isl_multi_union_pw_aff_from_union_pw_aff_list(space, list);
4002
260
4003
260
  return mupa;
4004
260
}
4005
4006
/* Read the body of an isl_union_set from "s",
4007
 * i.e., everything except the parameter specification.
4008
 * "v" contains a description of the identifiers parsed so far.
4009
 * The parameters, if any, are specified by "space".
4010
 *
4011
 * First read a generic disjunction of object bodies and then try and extract
4012
 * an isl_union_set from that.
4013
 */
4014
static __isl_give isl_union_set *read_union_set_body(__isl_keep isl_stream *s,
4015
  struct vars *v, __isl_take isl_space *space)
4016
71
{
4017
71
  struct isl_obj obj = { isl_obj_set, NULL };
4018
71
  isl_map *map;
4019
71
4020
71
  map = isl_set_universe(space);
4021
71
  if (isl_stream_eat(s, '{') < 0)
4022
0
    goto error;
4023
71
  obj = obj_read_disjuncts(s, v, map);
4024
71
  if (isl_stream_eat(s, '}') < 0)
4025
0
    goto error;
4026
71
  isl_map_free(map);
4027
71
4028
71
  return extract_union_set(s->ctx, obj);
4029
0
error:
4030
0
  obj.type->free(obj.v);
4031
0
  isl_map_free(map);
4032
0
  return NULL;
4033
71
}
4034
4035
/* Read the body of an isl_multi_union_pw_aff from "s",
4036
 * i.e., everything except the parameter specification.
4037
 * "v" contains a description of the identifiers parsed so far.
4038
 * The parameters, if any, are specified by "space".
4039
 *
4040
 * In particular, handle the special case with shared domain constraints.
4041
 * These are specified as
4042
 *
4043
 *  ([...] : ...)
4044
 *
4045
 * and are especially useful for setting the explicit domain
4046
 * of a zero-dimensional isl_multi_union_pw_aff.
4047
 * The core isl_multi_union_pw_aff body ([...]) is read by
4048
 * read_multi_union_pw_aff_body_core.
4049
 */
4050
static __isl_give isl_multi_union_pw_aff *read_multi_union_pw_aff_body(
4051
  __isl_keep isl_stream *s, struct vars *v, __isl_take isl_space *space)
4052
260
{
4053
260
  isl_multi_union_pw_aff *mupa;
4054
260
4055
260
  if (!isl_stream_next_token_is(s, '('))
4056
187
    return read_multi_union_pw_aff_body_core(s, v, space);
4057
73
4058
73
  if (isl_stream_eat(s, '(') < 0)
4059
0
    goto error;
4060
73
  mupa = read_multi_union_pw_aff_body_core(s, v, isl_space_copy(space));
4061
73
  if (isl_stream_eat_if_available(s, ':')) {
4062
71
    isl_union_set *dom;
4063
71
4064
71
    dom = read_union_set_body(s, v, space);
4065
71
    mupa = isl_multi_union_pw_aff_intersect_domain(mupa, dom);
4066
71
  } else {
4067
2
    isl_space_free(space);
4068
2
  }
4069
73
  if (isl_stream_eat(s, ')') < 0)
4070
0
    return isl_multi_union_pw_aff_free(mupa);
4071
73
4072
73
  return mupa;
4073
0
error:
4074
0
  isl_space_free(space);
4075
0
  return NULL;
4076
73
}
4077
4078
/* Read an isl_multi_union_pw_aff from "s".
4079
 *
4080
 * The input has the form
4081
 *
4082
 *  [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4083
 *
4084
 * or
4085
 *
4086
 *  [..] -> [{ [..] : ... ; [..] : ... }, { [..] : ... ; [..] : ... }]
4087
 *
4088
 * Additionally, a shared domain may be specified as
4089
 *
4090
 *  ([..] : ...)
4091
 *
4092
 * or
4093
 *
4094
 *  [..] -> ([..] : ...)
4095
 *
4096
 * The first case is handled by the caller, the second case
4097
 * is handled by read_multi_union_pw_aff_body.
4098
 *
4099
 * We first check for the special case of an empty tuple "[]".
4100
 * Then we check if there are any parameters.
4101
 * Finally, read the tuple and construct the result.
4102
 */
4103
static __isl_give isl_multi_union_pw_aff *read_multi_union_pw_aff_core(
4104
  __isl_keep isl_stream *s)
4105
272
{
4106
272
  struct vars *v;
4107
272
  isl_set *dom = NULL;
4108
272
  isl_space *space;
4109
272
  isl_multi_union_pw_aff *mupa = NULL;
4110
272
4111
272
  if (next_is_empty_tuple(s)) {
4112
12
    if (isl_stream_eat(s, '['))
4113
0
      return NULL;
4114
12
    if (isl_stream_eat(s, ']'))
4115
0
      return NULL;
4116
12
    space = isl_space_set_alloc(s->ctx, 0, 0);
4117
12
    return isl_multi_union_pw_aff_zero(space);
4118
12
  }
4119
260
4120
260
  v = vars_new(s->ctx);
4121
260
  if (!v)
4122
0
    return NULL;
4123
260
4124
260
  dom = isl_set_universe(isl_space_params_alloc(s->ctx, 0));
4125
260
  if (next_is_param_tuple(s)) {
4126
93
    dom = read_map_tuple(s, dom, isl_dim_param, v, 1, 0);
4127
93
    if (isl_stream_eat(s, ISL_TOKEN_TO))
4128
0
      goto error;
4129
260
  }
4130
260
  space = isl_set_get_space(dom);
4131
260
  isl_set_free(dom);
4132
260
  mupa = read_multi_union_pw_aff_body(s, v, space);
4133
260
4134
260
  vars_free(v);
4135
260
4136
260
  return mupa;
4137
0
error:
4138
0
  vars_free(v);
4139
0
  isl_set_free(dom);
4140
0
  isl_multi_union_pw_aff_free(mupa);
4141
0
  return NULL;
4142
260
}
4143
4144
/* Read an isl_multi_union_pw_aff from "s".
4145
 *
4146
 * In particular, handle the special case with shared domain constraints.
4147
 * These are specified as
4148
 *
4149
 *  ([...] : ...)
4150
 *
4151
 * and are especially useful for setting the explicit domain
4152
 * of a zero-dimensional isl_multi_union_pw_aff.
4153
 * The core isl_multi_union_pw_aff ([...]) is read by
4154
 * read_multi_union_pw_aff_core.
4155
 */
4156
__isl_give isl_multi_union_pw_aff *isl_stream_read_multi_union_pw_aff(
4157
  __isl_keep isl_stream *s)
4158
272
{
4159
272
  isl_multi_union_pw_aff *mupa;
4160
272
4161
272
  if (!isl_stream_next_token_is(s, '('))
4162
215
    return read_multi_union_pw_aff_core(s);
4163
57
4164
57
  if (isl_stream_eat(s, '(') < 0)
4165
0
    return NULL;
4166
57
  mupa = read_multi_union_pw_aff_core(s);
4167
57
  if (isl_stream_eat_if_available(s, ':')) {
4168
57
    isl_union_set *dom;
4169
57
4170
57
    dom = isl_stream_read_union_set(s);
4171
57
    mupa = isl_multi_union_pw_aff_intersect_domain(mupa, dom);
4172
57
  }
4173
57
  if (isl_stream_eat(s, ')') < 0)
4174
0
    return isl_multi_union_pw_aff_free(mupa);
4175
57
  return mupa;
4176
57
}
4177
4178
/* Read an isl_multi_union_pw_aff from "str".
4179
 */
4180
__isl_give isl_multi_union_pw_aff *isl_multi_union_pw_aff_read_from_str(
4181
  isl_ctx *ctx, const char *str)
4182
272
{
4183
272
  isl_multi_union_pw_aff *mupa;
4184
272
  isl_stream *s = isl_stream_new_str(ctx, str);
4185
272
  if (!s)
4186
0
    return NULL;
4187
272
  mupa = isl_stream_read_multi_union_pw_aff(s);
4188
272
  isl_stream_free(s);
4189
272
  return mupa;
4190
272
}
4191
4192
__isl_give isl_union_pw_qpolynomial *isl_stream_read_union_pw_qpolynomial(
4193
  __isl_keep isl_stream *s)
4194
2
{
4195
2
  struct isl_obj obj;
4196
2
4197
2
  obj = obj_read(s);
4198
2
  if (obj.type == isl_obj_pw_qpolynomial) {
4199
1
    obj.type = isl_obj_union_pw_qpolynomial;
4200
1
    obj.v = isl_union_pw_qpolynomial_from_pw_qpolynomial(obj.v);
4201
1
  }
4202
2
  if (obj.v)
4203
2
    isl_assert(s->ctx, obj.type == isl_obj_union_pw_qpolynomial,
4204
2
         goto error);
4205
2
4206
2
  return obj.v;
4207
0
error:
4208
0
  obj.type->free(obj.v);
4209
0
  return NULL;
4210
2
}
4211
4212
__isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_read_from_str(
4213
  isl_ctx *ctx, const char *str)
4214
2
{
4215
2
  isl_union_pw_qpolynomial *upwqp;
4216
2
  isl_stream *s = isl_stream_new_str(ctx, str);
4217
2
  if (!s)
4218
0
    return NULL;
4219
2
  upwqp = isl_stream_read_union_pw_qpolynomial(s);
4220
2
  isl_stream_free(s);
4221
2
  return upwqp;
4222
2
}