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 static 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 static 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 == '+') {
 270                         /* nothing */
 271                 } else if (tok->type == ISL_TOKEN_LE) {
 272                         op = 1;
 273                         isl_seq_neg(bmap->ineq[k], bmap->ineq[k], 1+total);
 274                 } else if (tok->type == ISL_TOKEN_GE) {
 275                         op = 1;
 276                         sign = -1;
 277                 } else if (tok->type == '=') {
 278                         if (op) {
 279                                 isl_stream_error(s, tok, "too many operators");
 280                                 goto error;
 281                         }
 282                         op = 1;
 283                         equality = 1;
 284                         sign = -1;
 285                 } else {
 286                         isl_stream_push_token(s, tok);
 287                         break;
 288                 }
 289                 isl_token_free(tok);
 290         }
 291         tok = NULL;
 292         if (!op) {
 293                 isl_stream_error(s, tok, "missing operator");
 294                 goto error;
 295         }
 296         if (equality)
 297                 isl_basic_map_inequality_to_equality(bmap, k);
 298         return bmap;
 299 error:
 300         if (tok)
 301                 isl_token_free(tok);
 302         isl_basic_map_free(bmap);
 303         return NULL;
 304 }
 305
 306 static struct isl_basic_map *add_constraints(struct isl_stream *s,
 307         struct vars **v, struct isl_basic_map *bmap)
 308 {
 309         struct isl_token *tok;
 310
 311         for (;;) {
 312                 bmap = add_constraint(s, v, bmap);
 313                 if (!bmap)
 314                         return NULL;
 315                 tok = isl_stream_next_token(s);
 316                 if (!tok) {
 317                         isl_stream_error(s, NULL, "unexpected EOF");
 318                         goto error;
 319                 }
 320                 if (tok->type != ISL_TOKEN_AND)
 321                         break;
 322                 isl_token_free(tok);
 323         }
 324         isl_stream_push_token(s, tok);
 325
 326         return bmap;
 327 error:
 328         if (tok)
 329                 isl_token_free(tok);
 330         isl_basic_map_free(bmap);
 331         return NULL;
 332 }
 333
 334 static struct isl_basic_map *basic_map_read(struct isl_stream *s)
 335 {
 336         struct isl_basic_map *bmap = NULL;
 337         struct isl_token *tok;
 338         struct vars *v = NULL;
 339         int n1;
 340         int n2;
 341
 342         tok = isl_stream_next_token(s);
 343         if (!tok || tok->type != '{') {
 344                 isl_stream_error(s, tok, "expecting '{'");
 345                 if (tok)
 346                         isl_stream_push_token(s, tok);
 347                 goto error;
 348         }
 349         isl_token_free(tok);
 350         v = vars_new(s->ctx);
 351         v = read_tuple(s, v);
 352         if (!v)
 353                 return NULL;
 354         n1 = v->n;
 355         tok = isl_stream_next_token(s);
 356         if (tok && tok->type == ISL_TOKEN_TO) {
 357                 isl_token_free(tok);
 358                 v = read_tuple(s, v);
 359                 if (!v)
 360                         return NULL;
 361                 n2 = v->n - n1;
 362         } else {
 363                 if (tok)
 364                         isl_stream_push_token(s, tok);
 365                 n2 = n1;
 366                 n1 = 0;
 367         }
 368         bmap = isl_basic_map_alloc(s->ctx, 0, n1, n2, 0, 0,0);
 369         if (!bmap)
 370                 goto error;
 371         tok = isl_stream_next_token(s);
 372         if (tok && tok->type == ':') {
 373                 isl_token_free(tok);
 374                 bmap = add_constraints(s, &v, bmap);
 375                 tok = isl_stream_next_token(s);
 376         }
 377         if (tok && tok->type == '}') {
 378                 isl_token_free(tok);
 379         } else {
 380                 isl_stream_error(s, tok, "unexpected isl_token");
 381                 if (tok)
 382                         isl_token_free(tok);
 383                 goto error;
 384         }
 385         vars_free(v);
 386
 387         return bmap;
 388 error:
 389         isl_basic_map_free(bmap);
 390         if (v)
 391                 vars_free(v);
 392         return NULL;
 393 }
 394
 395 struct isl_basic_map *isl_basic_map_read_from_file_omega(
 396                 struct isl_ctx *ctx, FILE *input)
 397 {
 398         struct isl_basic_map *bmap;
 399         struct isl_stream *s = isl_stream_new_file(ctx, input);
 400         if (!s)
 401                 return NULL;
 402         bmap = basic_map_read(s);
 403         isl_stream_free(s);
 404         return bmap;
 405 }
 406
 407 struct isl_basic_set *isl_basic_set_read_from_file_omega(
 408                 struct isl_ctx *ctx, FILE *input)
 409 {
 410         struct isl_basic_map *bmap;
 411         bmap = isl_basic_map_read_from_file_omega(ctx, input);
 412         if (!bmap)
 413                 return NULL;
 414         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
 415         return (struct isl_basic_set *)bmap;
 416 error:
 417         isl_basic_map_free(bmap);
 418         return NULL;
 419 }
 420
 421 struct isl_basic_map *isl_basic_map_read_from_str_omega(
 422                 struct isl_ctx *ctx, const char *str)
 423 {
 424         struct isl_basic_map *bmap;
 425         struct isl_stream *s = isl_stream_new_str(ctx, str);
 426         if (!s)
 427                 return NULL;
 428         bmap = basic_map_read(s);
 429         isl_stream_free(s);
 430         return bmap;
 431 }
 432
 433 struct isl_basic_set *isl_basic_set_read_from_str_omega(
 434                 struct isl_ctx *ctx, const char *str)
 435 {
 436         struct isl_basic_map *bmap;
 437         bmap = isl_basic_map_read_from_str_omega(ctx, str);
 438         if (!bmap)
 439                 return NULL;
 440         isl_assert(ctx, isl_basic_map_n_in(bmap) == 0, goto error);
 441         return (struct isl_basic_set *)bmap;
 442 error:
 443         isl_basic_map_free(bmap);
 444         return NULL;
 445 }