isl_tab_pivot: fix typo that prevented normalization of rows
[isl.git] / isl_input_omega.c
blob4fe49bdb76019d40312d3904dfcc7499d812d9f6
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"
9 struct variable {
10 char *name;
11 int pos;
12 struct variable *next;
15 struct vars {
16 struct isl_ctx *ctx;
17 int n;
18 struct variable *v;
21 static struct vars *vars_new(struct isl_ctx *ctx)
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;
33 static void variable_free(struct variable *var)
35 while (var) {
36 struct variable *next = var->next;
37 free(var->name);
38 free(var);
39 var = next;
43 static void vars_free(struct vars *v)
45 if (!v)
46 return;
47 variable_free(v->v);
48 free(v);
51 static struct variable *variable_new(struct vars *v, const char *name, int len,
52 int pos)
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;
68 static int vars_pos(struct vars *v, const char *s, int len)
70 int pos;
71 struct variable *q;
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;
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++;
88 return pos;
91 static struct vars *read_var_list(struct isl_stream *s, struct vars *v)
93 struct isl_token *tok;
95 while ((tok = isl_stream_next_token(s)) != NULL) {
96 int p;
97 int n = v->n;
99 if (tok->type != ISL_TOKEN_IDENT)
100 break;
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;
109 isl_token_free(tok);
110 tok = isl_stream_next_token(s);
111 if (!tok || tok->type != ',')
112 break;
114 isl_token_free(tok);
116 if (tok)
117 isl_stream_push_token(s, tok);
119 return v;
120 error:
121 isl_token_free(tok);
122 vars_free(v);
123 return NULL;
126 static struct vars *read_tuple(struct isl_stream *s, struct vars *v)
128 struct isl_token *tok;
130 tok = isl_stream_next_token(s);
131 if (!tok || tok->type != '[') {
132 isl_stream_error(s, tok, "expecting '['");
133 goto error;
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;
142 isl_token_free(tok);
144 return v;
145 error:
146 if (tok)
147 isl_token_free(tok);
148 vars_free(v);
149 return NULL;
152 static struct isl_basic_map *add_constraints(struct isl_stream *s,
153 struct vars **v, struct isl_basic_map *bmap);
155 static struct isl_basic_map *add_exists(struct isl_stream *s,
156 struct vars **v, struct isl_basic_map *bmap)
158 struct isl_token *tok;
159 int n = (*v)->n;
160 int extra;
161 int seen_paren = 0;
162 int i;
163 unsigned total;
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);
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;
200 static struct isl_basic_map *add_constraint(struct isl_stream *s,
201 struct vars **v, struct isl_basic_map *bmap)
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;
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);
217 isl_stream_push_token(s, tok);
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);
226 for (;;) {
227 tok = isl_stream_next_token(s);
228 if (!tok) {
229 isl_stream_error(s, NULL, "unexpected EOF");
230 goto error;
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;
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;
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;
282 op = 1;
283 equality = 1;
284 sign = -1;
285 } else {
286 isl_stream_push_token(s, tok);
287 break;
289 isl_token_free(tok);
291 tok = NULL;
292 if (!op) {
293 isl_stream_error(s, tok, "missing operator");
294 goto error;
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;
306 static struct isl_basic_map *add_constraints(struct isl_stream *s,
307 struct vars **v, struct isl_basic_map *bmap)
309 struct isl_token *tok;
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;
320 if (tok->type != ISL_TOKEN_AND)
321 break;
322 isl_token_free(tok);
324 isl_stream_push_token(s, tok);
326 return bmap;
327 error:
328 if (tok)
329 isl_token_free(tok);
330 isl_basic_map_free(bmap);
331 return NULL;
334 static struct isl_basic_map *basic_map_read(struct isl_stream *s)
336 struct isl_basic_map *bmap = NULL;
337 struct isl_token *tok;
338 struct vars *v = NULL;
339 int n1;
340 int n2;
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;
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;
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);
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;
385 vars_free(v);
387 return bmap;
388 error:
389 isl_basic_map_free(bmap);
390 if (v)
391 vars_free(v);
392 return NULL;
395 struct isl_basic_map *isl_basic_map_read_from_file_omega(
396 struct isl_ctx *ctx, FILE *input)
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;
407 struct isl_basic_set *isl_basic_set_read_from_file_omega(
408 struct isl_ctx *ctx, FILE *input)
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;
421 struct isl_basic_map *isl_basic_map_read_from_str_omega(
422 struct isl_ctx *ctx, const char *str)
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;
433 struct isl_basic_set *isl_basic_set_read_from_str_omega(
434 struct isl_ctx *ctx, const char *str)
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;