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_extend_dim(bmap, isl_dim_copy(bmap->dim),
 178                         extra, 0, 0);
 179         total = isl_basic_map_total_dim(bmap);
 180         for (i = 0; i < extra; ++i) {
 181                 int k;
 182                 if ((k = isl_basic_map_alloc_div(bmap)) < 0)
 183                         goto error;
 184                 isl_seq_clr(bmap->div[k], 1+1+total);
 185         }
 186         if (!bmap)
 187                 return NULL;
 188         if (isl_stream_eat(s, ':'))
 189                 goto error;
 190         bmap = add_constraints(s, v, bmap);
 191         if (seen_paren && isl_stream_eat(s, ')'))
 192                 goto error;
 193         return bmap;
 194 error:
 195         isl_basic_map_free(bmap);
 196         return NULL;
 197 }
 198
 199 static struct isl_basic_map *add_constraint(struct isl_stream *s,
 200         struct vars **v, struct isl_basic_map *bmap)
 201 {
 202         unsigned total = isl_basic_map_total_dim(bmap);
 203         int k;
 204         int sign = 1;
 205         int equality = 0;
 206         int op = 0;
 207         struct isl_token *tok = NULL;
 208
 209         tok = isl_stream_next_token(s);
 210         if (!tok)
 211                 goto error;
 212         if (tok->type == ISL_TOKEN_EXISTS) {
 213                 isl_token_free(tok);
 214                 return add_exists(s, v, bmap);
 215         }
 216         isl_stream_push_token(s, tok);
 217
 218         bmap = isl_basic_map_extend_constraints(bmap, 0, 1);
 219         k = isl_basic_map_alloc_inequality(bmap);
 220         if (k < 0)
 221                 goto error;
 222         isl_seq_clr(bmap->ineq[k], 1+total);
 223
 224         for (;;) {
 225                 tok = isl_stream_next_token(s);
 226                 if (!tok) {
 227                         isl_stream_error(s, NULL, "unexpected EOF");
 228                         goto error;
 229                 }
 230                 if (tok->type == ISL_TOKEN_IDENT) {
 231                         int n = (*v)->n;
 232                         int pos = vars_pos(*v, tok->u.s, -1);
 233                         if (pos < 0)
 234                                 goto error;
 235                         if (pos >= n) {
 236                                 isl_stream_error(s, tok, "unknown identifier");
 237                                 goto error;
 238                         }
 239                         if (sign > 0)
 240                                 isl_int_add_ui(bmap->ineq[k][1+pos],
 241                                                 bmap->ineq[k][1+pos], 1);
 242                         else
 243                                 isl_int_sub_ui(bmap->ineq[k][1+pos],
 244                                                 bmap->ineq[k][1+pos], 1);
 245                 } else if (tok->type == ISL_TOKEN_VALUE) {
 246                         struct isl_token *tok2;
 247                         int n = (*v)->n;
 248                         int pos = -1;
 249                         tok2 = isl_stream_next_token(s);
 250                         if (tok2 && tok2->type == ISL_TOKEN_IDENT) {
 251                                 pos = vars_pos(*v, tok2->u.s, -1);
 252                                 if (pos < 0)
 253                                         goto error;
 254                                 if (pos >= n) {
 255                                         isl_stream_error(s, tok2,
 256                                                 "unknown identifier");
 257                                         isl_token_free(tok2);
 258                                         goto error;
 259                                 }
 260                                 isl_token_free(tok2);
 261                         } else if (tok2)
 262                                 isl_stream_push_token(s, tok2);
 263                         if (sign < 0)
 264                                 isl_int_neg(tok->u.v, tok->u.v);
 265                         isl_int_add(bmap->ineq[k][1+pos],
 266                                         bmap->ineq[k][1+pos], tok->u.v);
 267                 } else if (tok->type == ISL_TOKEN_LE) {
 268                         op = 1;
 269                         isl_seq_neg(bmap->ineq[k], bmap->ineq[k], 1+total);
 270                 } else if (tok->type == ISL_TOKEN_GE) {
 271                         op = 1;
 272                         sign = -1;
 273                 } else if (tok->type == '=') {
 274                         if (op) {
 275                                 isl_stream_error(s, tok, "too many operators");
 276                                 goto error;
 277                         }
 278                         op = 1;
 279                         equality = 1;
 280                         sign = -1;
 281                 } else {
 282                         isl_stream_push_token(s, tok);
 283                         break;
 284                 }
 285                 isl_token_free(tok);
 286         }
 287         tok = NULL;
 288         if (!op) {
 289                 isl_stream_error(s, tok, "missing operator");
 290                 goto error;
 291         }
 292         if (equality)
 293                 isl_basic_map_inequality_to_equality(bmap, k);
 294         return bmap;
 295 error:
 296         if (tok)
 297                 isl_token_free(tok);
 298         isl_basic_map_free(bmap);
 299         return NULL;
 300 }
 301
 302 static struct isl_basic_map *add_constraints(struct isl_stream *s,
 303         struct vars **v, struct isl_basic_map *bmap)
 304 {
 305         struct isl_token *tok;
 306
 307         for (;;) {
 308                 bmap = add_constraint(s, v, bmap);
 309                 if (!bmap)
 310                         return NULL;
 311                 tok = isl_stream_next_token(s);
 312                 if (!tok) {
 313                         isl_stream_error(s, NULL, "unexpected EOF");
 314                         goto error;
 315                 }
 316                 if (tok->type != ISL_TOKEN_AND)
 317                         break;
 318                 isl_token_free(tok);
 319         }
 320         isl_stream_push_token(s, tok);
 321
 322         return bmap;
 323 error:
 324         if (tok)
 325                 isl_token_free(tok);
 326         isl_basic_map_free(bmap);
 327         return NULL;
 328 }
 329
 330 static struct isl_basic_map *basic_map_read(struct isl_stream *s)
 331 {
 332         struct isl_basic_map *bmap = NULL;
 333         struct isl_token *tok;
 334         struct vars *v = NULL;
 335         int n1;
 336         int n2;
 337
 338         tok = isl_stream_next_token(s);
 339         if (!tok || tok->type != '{') {
 340                 isl_stream_error(s, tok, "expecting '{'");
 341                 if (tok)
 342                         isl_stream_push_token(s, tok);
 343                 goto error;
 344         }
 345         isl_token_free(tok);
 346         v = vars_new(s->ctx);
 347         v = read_tuple(s, v);
 348         if (!v)
 349                 return NULL;
 350         n1 = v->n;
 351         tok = isl_stream_next_token(s);
 352         if (tok && tok->type == ISL_TOKEN_TO) {
 353                 isl_token_free(tok);
 354                 v = read_tuple(s, v);
 355                 if (!v)
 356                         return NULL;
 357                 n2 = v->n - n1;
 358         } else {
 359                 if (tok)
 360                         isl_stream_push_token(s, tok);
 361                 n2 = n1;
 362                 n1 = 0;
 363         }
 364         bmap = isl_basic_map_alloc(s->ctx, 0, n1, n2, 0, 0,0);
 365         if (!bmap)
 366                 goto error;
 367         tok = isl_stream_next_token(s);
 368         if (tok && tok->type == ':') {
 369                 isl_token_free(tok);
 370                 bmap = add_constraints(s, &v, bmap);
 371                 tok = isl_stream_next_token(s);
 372         }
 373         if (tok && tok->type == '}') {
 374                 isl_token_free(tok);
 375         } else {
 376                 isl_stream_error(s, tok, "unexpected isl_token");
 377                 if (tok)
 378                         isl_token_free(tok);
 379                 goto error;
 380         }
 381         vars_free(v);
 382
 383         return bmap;
 384 error:
 385         isl_basic_map_free(bmap);
 386         if (v)
 387                 vars_free(v);
 388         return NULL;
 389 }
 390
 391 struct isl_basic_map *isl_basic_map_read_from_file_omega(
 392                 struct isl_ctx *ctx, FILE *input)
 393 {
 394         struct isl_basic_map *bmap;
 395         struct isl_stream *s = isl_stream_new_file(ctx, input);
 396         if (!s)
 397                 return NULL;
 398         bmap = basic_map_read(s);
 399         isl_stream_free(s);
 400         return bmap;
 401 }
 402
 403 struct isl_basic_set *isl_basic_set_read_from_file_omega(
 404                 struct isl_ctx *ctx, FILE *input)
 405 {
 406         struct isl_basic_map *bmap;
 407         bmap = isl_basic_map_read_from_file_omega(ctx, input);
 408         if (!bmap)
 409                 return NULL;
 410         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
 411         return (struct isl_basic_set *)bmap;
 412 error:
 413         isl_basic_map_free(bmap);
 414         return NULL;
 415 }
 416
 417 struct isl_basic_map *isl_basic_map_read_from_str_omega(
 418                 struct isl_ctx *ctx, const char *str)
 419 {
 420         struct isl_basic_map *bmap;
 421         struct isl_stream *s = isl_stream_new_str(ctx, str);
 422         if (!s)
 423                 return NULL;
 424         bmap = basic_map_read(s);
 425         isl_stream_free(s);
 426         return bmap;
 427 }
 428
 429 struct isl_basic_set *isl_basic_set_read_from_str_omega(
 430                 struct isl_ctx *ctx, const char *str)
 431 {
 432         struct isl_basic_map *bmap;
 433         bmap = isl_basic_map_read_from_str_omega(ctx, str);
 434         if (!bmap)
 435                 return NULL;
 436         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
 437         return (struct isl_basic_set *)bmap;
 438 error:
 439         isl_basic_map_free(bmap);
 440         return NULL;
 441 }