isl_input_omega.c

   1 #include <ctype.h>
   2 #include <string.h>
   3 #include <strings.h>
   4 #include <isl_seq.h>
   5 #include "isl_stream.h"
   6 #include "isl_map_private.h"
   7 #include "isl_input_omega.h"
   8
   9 struct variable {
  10         char                    *name;
  11         int                      pos;
  12         struct variable         *next;
  13 };
  14
  15 struct vars {
  16         struct isl_ctx  *ctx;
  17         int              n;
  18         struct variable *v;
  19 };
  20
  21 static struct vars *vars_new(struct isl_ctx *ctx)
  22 {
  23         struct vars *v;
  24         v = isl_alloc_type(ctx, struct vars);
  25         if (!v)
  26                 return NULL;
  27         v->ctx = ctx;
  28         v->n = 0;
  29         v->v = NULL;
  30         return v;
  31 }
  32
  33 void variable_free(struct variable *var)
  34 {
  35         while (var) {
  36                 struct variable *next = var->next;
  37                 free(var->name);
  38                 free(var);
  39                 var = next;
  40         }
  41 }
  42
  43 static void vars_free(struct vars *v)
  44 {
  45         if (!v)
  46                 return;
  47         variable_free(v->v);
  48         free(v);
  49 }
  50
  51 struct variable *variable_new(struct vars *v, const char *name, int len,
  52                                 int pos)
  53 {
  54         struct variable *var;
  55         var = isl_alloc_type(v->ctx, struct variable);
  56         if (!var)
  57                 goto error;
  58         var->name = strdup(name);
  59         var->name[len] = '\0';
  60         var->pos = pos;
  61         var->next = v->v;
  62         return var;
  63 error:
  64         variable_free(v->v);
  65         return NULL;
  66 }
  67
  68 static int vars_pos(struct vars *v, const char *s, int len)
  69 {
  70         int pos;
  71         struct variable *q;
  72
  73         if (len == -1)
  74                 len = strlen(s);
  75         for (q = v->v; q; q = q->next) {
  76                 if (strncmp(q->name, s, len) == 0 && q->name[len] == '\0')
  77                         break;
  78         }
  79         if (q)
  80                 pos = q->pos;
  81         else {
  82                 pos = v->n;
  83                 v->v = variable_new(v, s, len, v->n);
  84                 if (!v)
  85                         return -1;
  86                 v->n++;
  87         }
  88         return pos;
  89 }
  90
  91 static struct vars *read_var_list(struct isl_stream *s, struct vars *v)
  92 {
  93         struct isl_token *tok;
  94
  95         while ((tok = isl_stream_next_token(s)) != NULL) {
  96                 int p;
  97                 int n = v->n;
  98
  99                 if (tok->type != ISL_TOKEN_IDENT)
 100                         break;
 101
 102                 p = vars_pos(v, tok->u.s, -1);
 103                 if (p < 0)
 104                         goto error;
 105                 if (p < n) {
 106                         isl_stream_error(s, tok, "expecting unique identifier");
 107                         goto error;
 108                 }
 109                 isl_token_free(tok);
 110                 tok = isl_stream_next_token(s);
 111                 if (!tok || tok->type != ',')
 112                         break;
 113
 114                 isl_token_free(tok);
 115         }
 116         if (tok)
 117                 isl_stream_push_token(s, tok);
 118
 119         return v;
 120 error:
 121         isl_token_free(tok);
 122         vars_free(v);
 123         return NULL;
 124 }
 125
 126 static struct vars *read_tuple(struct isl_stream *s, struct vars *v)
 127 {
 128         struct isl_token *tok;
 129
 130         tok = isl_stream_next_token(s);
 131         if (!tok || tok->type != '[') {
 132                 isl_stream_error(s, tok, "expecting '['");
 133                 goto error;
 134         }
 135         isl_token_free(tok);
 136         v = read_var_list(s, v);
 137         tok = isl_stream_next_token(s);
 138         if (!tok || tok->type != ']') {
 139                 isl_stream_error(s, tok, "expecting ']'");
 140                 goto error;
 141         }
 142         isl_token_free(tok);
 143
 144         return v;
 145 error:
 146         if (tok)
 147                 isl_token_free(tok);
 148         vars_free(v);
 149         return NULL;
 150 }
 151
 152 static struct isl_basic_map *add_constraints(struct isl_stream *s,
 153         struct vars **v, struct isl_basic_map *bmap);
 154
 155 static struct isl_basic_map *add_exists(struct isl_stream *s,
 156         struct vars **v, struct isl_basic_map *bmap)
 157 {
 158         struct isl_token *tok;
 159         int n = (*v)->n;
 160         int extra;
 161         int seen_paren = 0;
 162         int i;
 163         unsigned total;
 164
 165         tok = isl_stream_next_token(s);
 166         if (!tok)
 167                 goto error;
 168         if (tok->type == '(') {
 169                 seen_paren = 1;
 170                 isl_token_free(tok);
 171         } else
 172                 isl_stream_push_token(s, tok);
 173         *v = read_var_list(s, *v);
 174         if (!*v)
 175                 goto error;
 176         extra = (*v)->n - n;
 177         bmap = isl_basic_map_cow(bmap);
 178         bmap = isl_basic_map_extend_dim(bmap, isl_dim_copy(bmap->dim),
 179                         extra, 0, 0);
 180         total = isl_basic_map_total_dim(bmap);
 181         for (i = 0; i < extra; ++i) {
 182                 int k;
 183                 if ((k = isl_basic_map_alloc_div(bmap)) < 0)
 184                         goto error;
 185                 isl_seq_clr(bmap->div[k], 1+1+total);
 186         }
 187         if (!bmap)
 188                 return NULL;
 189         if (isl_stream_eat(s, ':'))
 190                 goto error;
 191         bmap = add_constraints(s, v, bmap);
 192         if (seen_paren && isl_stream_eat(s, ')'))
 193                 goto error;
 194         return bmap;
 195 error:
 196         isl_basic_map_free(bmap);
 197         return NULL;
 198 }
 199
 200 static struct isl_basic_map *add_constraint(struct isl_stream *s,
 201         struct vars **v, struct isl_basic_map *bmap)
 202 {
 203         unsigned total = isl_basic_map_total_dim(bmap);
 204         int k;
 205         int sign = 1;
 206         int equality = 0;
 207         int op = 0;
 208         struct isl_token *tok = NULL;
 209
 210         tok = isl_stream_next_token(s);
 211         if (!tok)
 212                 goto error;
 213         if (tok->type == ISL_TOKEN_EXISTS) {
 214                 isl_token_free(tok);
 215                 return add_exists(s, v, bmap);
 216         }
 217         isl_stream_push_token(s, tok);
 218
 219         bmap = isl_basic_map_cow(bmap);
 220         bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
 221         k = isl_basic_map_alloc_inequality(bmap);
 222         if (k < 0)
 223                 goto error;
 224         isl_seq_clr(bmap->ineq[k], 1+total);
 225
 226         for (;;) {
 227                 tok = isl_stream_next_token(s);
 228                 if (!tok) {
 229                         isl_stream_error(s, NULL, "unexpected EOF");
 230                         goto error;
 231                 }
 232                 if (tok->type == ISL_TOKEN_IDENT) {
 233                         int n = (*v)->n;
 234                         int pos = vars_pos(*v, tok->u.s, -1);
 235                         if (pos < 0)
 236                                 goto error;
 237                         if (pos >= n) {
 238                                 isl_stream_error(s, tok, "unknown identifier");
 239                                 goto error;
 240                         }
 241                         if (sign > 0)
 242                                 isl_int_add_ui(bmap->ineq[k][1+pos],
 243                                                 bmap->ineq[k][1+pos], 1);
 244                         else
 245                                 isl_int_sub_ui(bmap->ineq[k][1+pos],
 246                                                 bmap->ineq[k][1+pos], 1);
 247                 } else if (tok->type == ISL_TOKEN_VALUE) {
 248                         struct isl_token *tok2;
 249                         int n = (*v)->n;
 250                         int pos = -1;
 251                         tok2 = isl_stream_next_token(s);
 252                         if (tok2 && tok2->type == ISL_TOKEN_IDENT) {
 253                                 pos = vars_pos(*v, tok2->u.s, -1);
 254                                 if (pos < 0)
 255                                         goto error;
 256                                 if (pos >= n) {
 257                                         isl_stream_error(s, tok2,
 258                                                 "unknown identifier");
 259                                         isl_token_free(tok2);
 260                                         goto error;
 261                                 }
 262                                 isl_token_free(tok2);
 263                         } else if (tok2)
 264                                 isl_stream_push_token(s, tok2);
 265                         if (sign < 0)
 266                                 isl_int_neg(tok->u.v, tok->u.v);
 267                         isl_int_add(bmap->ineq[k][1+pos],
 268                                         bmap->ineq[k][1+pos], tok->u.v);
 269                 } else if (tok->type == ISL_TOKEN_LE) {
 270                         op = 1;
 271                         isl_seq_neg(bmap->ineq[k], bmap->ineq[k], 1+total);
 272                 } else if (tok->type == ISL_TOKEN_GE) {
 273                         op = 1;
 274                         sign = -1;
 275                 } else if (tok->type == '=') {
 276                         if (op) {
 277                                 isl_stream_error(s, tok, "too many operators");
 278                                 goto error;
 279                         }
 280                         op = 1;
 281                         equality = 1;
 282                         sign = -1;
 283                 } else {
 284                         isl_stream_push_token(s, tok);
 285                         break;
 286                 }
 287                 isl_token_free(tok);
 288         }
 289         tok = NULL;
 290         if (!op) {
 291                 isl_stream_error(s, tok, "missing operator");
 292                 goto error;
 293         }
 294         if (equality)
 295                 isl_basic_map_inequality_to_equality(bmap, k);
 296         return bmap;
 297 error:
 298         if (tok)
 299                 isl_token_free(tok);
 300         isl_basic_map_free(bmap);
 301         return NULL;
 302 }
 303
 304 static struct isl_basic_map *add_constraints(struct isl_stream *s,
 305         struct vars **v, struct isl_basic_map *bmap)
 306 {
 307         struct isl_token *tok;
 308
 309         for (;;) {
 310                 bmap = add_constraint(s, v, bmap);
 311                 if (!bmap)
 312                         return NULL;
 313                 tok = isl_stream_next_token(s);
 314                 if (!tok) {
 315                         isl_stream_error(s, NULL, "unexpected EOF");
 316                         goto error;
 317                 }
 318                 if (tok->type != ISL_TOKEN_AND)
 319                         break;
 320                 isl_token_free(tok);
 321         }
 322         isl_stream_push_token(s, tok);
 323
 324         return bmap;
 325 error:
 326         if (tok)
 327                 isl_token_free(tok);
 328         isl_basic_map_free(bmap);
 329         return NULL;
 330 }
 331
 332 static struct isl_basic_map *basic_map_read(struct isl_stream *s)
 333 {
 334         struct isl_basic_map *bmap = NULL;
 335         struct isl_token *tok;
 336         struct vars *v = NULL;
 337         int n1;
 338         int n2;
 339
 340         tok = isl_stream_next_token(s);
 341         if (!tok || tok->type != '{') {
 342                 isl_stream_error(s, tok, "expecting '{'");
 343                 if (tok)
 344                         isl_stream_push_token(s, tok);
 345                 goto error;
 346         }
 347         isl_token_free(tok);
 348         v = vars_new(s->ctx);
 349         v = read_tuple(s, v);
 350         if (!v)
 351                 return NULL;
 352         n1 = v->n;
 353         tok = isl_stream_next_token(s);
 354         if (tok && tok->type == ISL_TOKEN_TO) {
 355                 isl_token_free(tok);
 356                 v = read_tuple(s, v);
 357                 if (!v)
 358                         return NULL;
 359                 n2 = v->n - n1;
 360         } else {
 361                 if (tok)
 362                         isl_stream_push_token(s, tok);
 363                 n2 = n1;
 364                 n1 = 0;
 365         }
 366         bmap = isl_basic_map_alloc(s->ctx, 0, n1, n2, 0, 0,0);
 367         if (!bmap)
 368                 goto error;
 369         tok = isl_stream_next_token(s);
 370         if (tok && tok->type == ':') {
 371                 isl_token_free(tok);
 372                 bmap = add_constraints(s, &v, bmap);
 373                 tok = isl_stream_next_token(s);
 374         }
 375         if (tok && tok->type == '}') {
 376                 isl_token_free(tok);
 377         } else {
 378                 isl_stream_error(s, tok, "unexpected isl_token");
 379                 if (tok)
 380                         isl_token_free(tok);
 381                 goto error;
 382         }
 383         vars_free(v);
 384
 385         return bmap;
 386 error:
 387         isl_basic_map_free(bmap);
 388         if (v)
 389                 vars_free(v);
 390         return NULL;
 391 }
 392
 393 struct isl_basic_map *isl_basic_map_read_from_file_omega(
 394                 struct isl_ctx *ctx, FILE *input)
 395 {
 396         struct isl_basic_map *bmap;
 397         struct isl_stream *s = isl_stream_new_file(ctx, input);
 398         if (!s)
 399                 return NULL;
 400         bmap = basic_map_read(s);
 401         isl_stream_free(s);
 402         return bmap;
 403 }
 404
 405 struct isl_basic_set *isl_basic_set_read_from_file_omega(
 406                 struct isl_ctx *ctx, FILE *input)
 407 {
 408         struct isl_basic_map *bmap;
 409         bmap = isl_basic_map_read_from_file_omega(ctx, input);
 410         if (!bmap)
 411                 return NULL;
 412         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
 413         return (struct isl_basic_set *)bmap;
 414 error:
 415         isl_basic_map_free(bmap);
 416         return NULL;
 417 }
 418
 419 struct isl_basic_map *isl_basic_map_read_from_str_omega(
 420                 struct isl_ctx *ctx, const char *str)
 421 {
 422         struct isl_basic_map *bmap;
 423         struct isl_stream *s = isl_stream_new_str(ctx, str);
 424         if (!s)
 425                 return NULL;
 426         bmap = basic_map_read(s);
 427         isl_stream_free(s);
 428         return bmap;
 429 }
 430
 431 struct isl_basic_set *isl_basic_set_read_from_str_omega(
 432                 struct isl_ctx *ctx, const char *str)
 433 {
 434         struct isl_basic_map *bmap;
 435         bmap = isl_basic_map_read_from_str_omega(ctx, str);
 436         if (!bmap)
 437                 return NULL;
 438         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
 439         return (struct isl_basic_set *)bmap;
 440 error:
 441         isl_basic_map_free(bmap);
 442         return NULL;
 443 }