1 2 /*+-----------------------------------------------------------------** 3 ** OpenScop Library ** 4 **-----------------------------------------------------------------** 5 ** util.c ** 6 **-----------------------------------------------------------------** 7 ** First version: 08/10/2010 ** 8 **-----------------------------------------------------------------** 9 10 11 ***************************************************************************** 12 * OpenScop: Structures and formats for polyhedral tools to talk together * 13 ***************************************************************************** 14 * ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__, * 15 * / / / // // // // / / / // // / / // / /|,_, * 16 * / / / // // // // / / / // // / / // / / / /\ * 17 * |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/ \ * 18 * | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\ \ /\ * 19 * | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\ * 20 * | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \ \ * 21 * | P |n| l | = | s | t |=| = |d| = | = | = | | |=| o | | \# \ \ * 22 * | H | | y | | e | o | | = |l| | | = | | | | G | | \ \ \ * 23 * | I | | | | e | | | | | | | | | | | | | \ \ \ * 24 * | T | | | | | | | | | | | | | | | | | \ \ \ * 25 * | E | | | | | | | | | | | | | | | | | \ \ \ * 26 * | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | / \* \ \ * 27 * | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/ \ \ / * 28 * '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---' '--' * 29 * * 30 * Copyright (C) 2008 University Paris-Sud 11 and INRIA * 31 * * 32 * (3-clause BSD license) * 33 * Redistribution and use in source and binary forms, with or without * 34 * modification, are permitted provided that the following conditions * 35 * are met: * 36 * * 37 * 1. Redistributions of source code must retain the above copyright notice, * 38 * this list of conditions and the following disclaimer. * 39 * 2. Redistributions in binary form must reproduce the above copyright * 40 * notice, this list of conditions and the following disclaimer in the * 41 * documentation and/or other materials provided with the distribution. * 42 * 3. The name of the author may not be used to endorse or promote products * 43 * derived from this software without specific prior written permission. * 44 * * 45 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * 46 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * 47 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * 48 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * 49 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * 50 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * 51 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * 52 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * 53 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * 54 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * 55 * * 56 * OpenScop Library, a library to manipulate OpenScop formats and data * 57 * structures. Written by: * 58 * Cedric Bastoul <Cedric.Bastoul@u-psud.fr> and * 59 * Louis-Noel Pouchet <Louis-Noel.pouchet@inria.fr> * 60 * * 61 *****************************************************************************/ 62 63#include <stdlib.h> 64#include <stdio.h> 65#include <ctype.h> 66#include <string.h> 67 68#include <osl/macros.h> 69#include <osl/util.h> 70 71 72/*+*************************************************************************** 73 * Utility functions * 74 *****************************************************************************/ 75 76 77/** 78 * osl_util_skip_blank_and_comments "file skip" function: 79 * this function reads the open file 'file' line by line and skips 80 * blank/comment lines and spaces. The first line where there is some 81 * useful information is stored at the address 'str' (the memory to 82 * store the line must be allocated before the call to this function 83 * and must be at least OSL_MAX_STRING * sizeof(char)). The pointer 84 * to the first useful information in this line is returned by the 85 * function. 86 * \param[in] file The (opened) file to read. 87 * \param[in] str Address of an allocated space to store the first line 88 * that contains useful information. 89 * \return The address of the first useful digit in str. 90 */ 91char * osl_util_skip_blank_and_comments(FILE * file, char * str) { 92 char * start; 93 94 do { 95 start = fgets(str, OSL_MAX_STRING, file); 96 while ((start != NULL) && isspace(*start) && (*start != '\n')) 97 start++; 98 } 99 while (start != NULL && (*start == '#' || *start == '\n')); 100 101 return start; 102} 103 104 105/** 106 * osl_util_sskip_blank_and_comments "string skip" function: 107 * this function updates the str pointer, which initialy points to a string, 108 * to the first character in this string which is not a space or a comment 109 * (comments start at '#' and end at '\n'), or to the end of string. 110 * \param[in,out] str Address of a string, updated to the address of 111 * the first non-space or comment character. 112 */ 113void osl_util_sskip_blank_and_comments(char ** str) { 114 do { 115 // Skip spaces/blanc lines. 116 while (*str && **str && isspace(**str)) 117 (*str)++; 118 119 // Skip the comment if any. 120 if (*str && **str && **str == '#') { 121 while (**str && **str != '\n') { 122 (*str)++; 123 } 124 } 125 } 126 while (*str && **str && **str == '\n'); 127} 128 129 130/** 131 * osl_util_read_int function: 132 * reads an int on the input 'file' or the input string 'str' depending on 133 * which one is not NULL (exactly one of them must not be NULL). 134 * \param[in] file The file where to read an int (if not NULL). 135 * \param[in,out] str The string where to read an int (if not NULL). This 136 * pointer is updated to reflect the read and points 137 * after the int in the input string. 138 * \return The int that has been read. 139 */ 140int osl_util_read_int(FILE * file, char ** str) { 141 char s[OSL_MAX_STRING], * start; 142 int res; 143 int i = 0; 144 145 if ((file != NULL && str != NULL) || (file == NULL && str == NULL)) 146 OSL_error("one and only one of the two parameters can be non-NULL"); 147 148 if (file != NULL) { 149 // Parse from a file. 150 start = osl_util_skip_blank_and_comments(file, s); 151 if (sscanf(start, " %d", &res) != 1) 152 OSL_error("an int was expected"); 153 } 154 else { 155 // Parse from a string. 156 // Skip blank/commented lines. 157 osl_util_sskip_blank_and_comments(str); 158 159 // Build the chain to analyze. 160 while (**str && !isspace(**str) && **str != '\n' && **str != '#') 161 s[i++] = *((*str)++); 162 s[i] = '\0'; 163 if (sscanf(s, "%d", &res) != 1) 164 OSL_error("an int was expected"); 165 } 166 167 return res; 168} 169 170 171/** 172 * osl_util_read_string function: 173 * reads a string on the input 'file' or the input string 'str' depending on 174 * which one is not NULL (exactly one of them must not be NULL). 175 * \param[in] file The file where to read a string (if not NULL). 176 * \param[in,out] str The string where to read a string (if not NULL). This 177 * pointer is updated to reflect the read and points 178 * after the string in the input string. 179 * \return The string that has been read. 180 */ 181char * osl_util_read_string(FILE * file, char ** str) { 182 char s[OSL_MAX_STRING], * start; 183 char * res; 184 int i = 0; 185 186 if ((file != NULL && str != NULL) || (file == NULL && str == NULL)) 187 OSL_error("one and only one of the two parameters can be non-NULL"); 188 189 OSL_malloc(res, char *, OSL_MAX_STRING * sizeof(char)); 190 if (file != NULL) { 191 // Parse from a file. 192 start = osl_util_skip_blank_and_comments(file, s); 193 if (sscanf(start, " %s", res) != 1) 194 OSL_error("a string was expected"); 195 } 196 else { 197 // Parse from a string. 198 // Skip blank/commented lines. 199 osl_util_sskip_blank_and_comments(str); 200 201 // Build the chain to analyze. 202 while (**str && !isspace(**str) && **str != '\n' && **str != '#') 203 s[i++] = *((*str)++); 204 s[i] = '\0'; 205 if (sscanf(s, "%s", res) != 1) 206 OSL_error("a string was expected"); 207 } 208 209 OSL_realloc(res, char *, strlen(res) + 1); 210 return res; 211} 212 213 214/** 215 * osl_util_read_line function: 216 * reads a line on the input 'file' or the input string 'str' depending on 217 * which one is not NULL (exactly one of them must not be NULL). A line 218 * is defined as the array of characters before the comment tag or the end of 219 * line (it may include spaces). 220 * \param[in] file The file where to read a line (if not NULL). 221 * \param[in,out] str The string where to read a line (if not NULL). This 222 * pointer is updated to reflect the read and points 223 * after the line in the input string. 224 * \return The line that has been read. 225 */ 226char * osl_util_read_line(FILE * file, char ** str) { 227 char s[OSL_MAX_STRING], * start; 228 char * res; 229 int i = 0; 230 231 if ((file != NULL && str != NULL) || (file == NULL && str == NULL)) 232 OSL_error("one and only one of the two parameters can be non-NULL"); 233 234 OSL_malloc(res, char *, OSL_MAX_STRING * sizeof(char)); 235 if (file != NULL) { 236 // Parse from a file. 237 start = osl_util_skip_blank_and_comments(file, s); 238 while (*start && *start != '\n' && *start != '#' && i < OSL_MAX_STRING) 239 res[i++] = (*start)++; 240 } 241 else { 242 // Parse from a string. 243 osl_util_sskip_blank_and_comments(str); 244 while (**str && **str != '\n' && **str != '#' && i < OSL_MAX_STRING) 245 res[i++] = *((*str)++); 246 } 247 248 res[i] = '\0'; 249 OSL_realloc(res, char *, strlen(res) + 1); 250 return res; 251} 252 253 254/** 255 * osl_util_read_int internal function: 256 * reads a tag (the form of a tag with name "name" is \<name\>) on the input 257 * 'file' or the input string 'str' depending on which one is not NULL (exactly 258 * one of them must not be NULL). It returns the name of the tag (thus without 259 * the < and > as a string. Note that in the case of an ending tag, e.g., 260 * \</foo\>, the slash is returned as a part of the name, e.g., /foo. 261 * \param[in] file The file where to read a tag (if not NULL). 262 * \param[in,out] str The string where to read a tag (if not NULL). This 263 * pointer is updated to reflect the read and points 264 * after the tag in the input string. 265 * \return The tag name that has been read. 266 */ 267char * osl_util_read_tag(FILE * file, char ** str) { 268 char s[OSL_MAX_STRING], * start; 269 char * res; 270 int i = 0; 271 272 if ((file != NULL && str != NULL) || (file == NULL && str == NULL)) 273 OSL_error("one and only one of the two parameters can be non-NULL"); 274 275 // Skip blank/commented lines. 276 if (file != NULL) { 277 start = osl_util_skip_blank_and_comments(file, s); 278 str = &start; 279 } 280 else { 281 osl_util_sskip_blank_and_comments(str); 282 } 283 284 // Pass the starting '<'. 285 if (**str != '<') 286 OSL_error("a \"<\" to start a tag was expected"); 287 (*str)++; 288 289 // Read the tag. 290 OSL_malloc(res, char *, (OSL_MAX_STRING + 1) * sizeof(char)); 291 res[OSL_MAX_STRING] = '\0'; 292 293 while (**str && **str != '>') { 294 if (((**str >= 'A') && (**str <= 'Z')) || 295 ((**str >= 'a') && (**str <= 'z')) || 296 ((**str == '/') && (i == 0)) || 297 (**str == '_')) { 298 res[i++] = *((*str)++); 299 res[i] = '\0'; 300 } 301 else { 302 OSL_error("illegal character in the tag name"); 303 } 304 } 305 306 // Check we actually end up with a '>' and pass it. 307 if (**str != '>') 308 OSL_error("a \">\" to end a tag was expected"); 309 (*str)++; 310 311 return res; 312} 313 314 315/** 316 * osl_util_read_uptotag function: 317 * this function reads a file up to a given tag (the tag is read) or the 318 * end of file. It puts everything it reads, except the tag, in a string 319 * which is returned. However ot returns NULL is the tag is not found. 320 * \param[in] file The file where to read the tail. 321 * \param[in] tag The tag which, when reached, stops the file reading. 322 * \return The string that has been read from the file. 323 */ 324char * osl_util_read_uptotag(FILE * file, char * tag) { 325 int high_water_mark = OSL_MAX_STRING; 326 int nb_chars = 0; 327 int lentag = strlen(tag); 328 int tag_found = 0; 329 char * res; 330 331 OSL_malloc(res, char *, high_water_mark * sizeof(char)); 332 333 // - Copy everything to the res string. 334 while (!feof(file)) { 335 res[nb_chars] = fgetc(file); 336 nb_chars++; 337 338 if ((nb_chars >= lentag) && 339 (!strncmp(&res[nb_chars - lentag], tag, lentag))) { 340 tag_found = 1; 341 break; 342 } 343 344 if (nb_chars >= high_water_mark) { 345 high_water_mark += high_water_mark; 346 OSL_realloc(res, char *, high_water_mark * sizeof(char)); 347 } 348 } 349 350 if (!tag_found) { 351 OSL_debug("tag was not found, end of file reached"); 352 free(res); 353 return NULL; 354 } 355 356 // - 0-terminate the string. 357 OSL_realloc(res, char *, (nb_chars - strlen(tag) + 1) * sizeof(char)); 358 res[nb_chars - strlen(tag)] = '\0'; 359 360 return res; 361} 362 363 364/** 365 * osl_util_read_uptoendtag function: 366 * this function reads a file up to a given end tag (this end tag is read) 367 * or the end of file. The name of the tag is provided as parameter (hence 368 * without the starting "</" end the closing ">"). It puts everything it reads 369 * in a string which is returned. 370 * \param[in] file The file where to read the tail. 371 * \param[in] name The name of the end tag to the file reading. 372 * \return The string that has been read from the file. 373 */ 374char * osl_util_read_uptoendtag(FILE * file, char * name) { 375 char tag[strlen(name) + 4]; 376 377 sprintf(tag, "</%s>", name); 378 return osl_util_read_uptotag(file, tag); 379} 380 381 382/** 383 * osl_util_tag_content function: 384 * this function returns a freshly allocated string containing the 385 * content, in the given string 'str', between the tag '\<name\>' and 386 * the tag '\</name\>'. If the tag '\<name\>' is not found, it returns NULL. 387 * \param[in] str The string where to find a given content. 388 * \param[in] name The name of the tag we are looking for. 389 * \return The string between '\<name\>' and '\</name\>' in 'str'. 390 */ 391char * osl_util_tag_content(char * str, char * name) { 392 int i; 393 char * start; 394 char * stop; 395 char tag[strlen(name) + 3]; 396 char endtag[strlen(name) + 4]; 397 int size = 0; 398 int lentag; 399 char * res = NULL; 400 401 sprintf(tag, "<%s>", name); 402 sprintf(endtag, "</%s>", name); 403 404 if (str) { 405 start = str; 406 lentag = strlen(tag); 407 for (; start && *start && strncmp(start, tag, lentag); ++start) 408 continue; 409 410 // The tag 'tag' was not found. 411 if (! *start) 412 return NULL; 413 start += lentag; 414 stop = start; 415 lentag = strlen(endtag); 416 for (size = 0; *stop && strncmp(stop, endtag, lentag); ++stop, ++size) 417 continue; 418 419 // the tag 'endtag' was not found. 420 if (! *stop) 421 return NULL; 422 OSL_malloc(res, char *, (size + 1) * sizeof(char)); 423 424 // Copy the chain between the two tags. 425 for (++start, i = 0; start != stop; ++start, ++i) 426 res[i] = *start; 427 res[i] = '\0'; 428 } 429 430 return res; 431} 432 433 434/** 435 * osl_util_safe_strcat function: 436 * this function concatenates the string src to the string *dst 437 * and reallocates *dst if necessary. The current size of the 438 * *dst buffer must be *hwm (high water mark), if there is some 439 * reallocation, this value is updated. 440 * \param[in,out] dst pointer to the destination string (may be reallocated). 441 * \param[in] src string to concatenate to dst. 442 * \param[in,out] hwm pointer to the size of the *dst buffer (may be updated). 443 */ 444void osl_util_safe_strcat(char ** dst, char * src, int * hwm) { 445 446 while (strlen(*dst) + strlen(src) >= *hwm) { 447 *hwm += OSL_MAX_STRING; 448 OSL_realloc(*dst, char *, *hwm * sizeof(char)); 449 } 450 451 strcat(*dst, src); 452} 453 454 455/** 456 * osl_util_get_precision function: 457 * this function returns the precision defined by the precision environment 458 * variable or the highest available precision if it is not defined. 459 * \return environment precision if defined or highest available precision. 460 */ 461int osl_util_get_precision() { 462 int precision = OSL_PRECISION_DP; 463 char * precision_env; 464 465#ifdef OSL_GMP_IS_HERE 466 precision = OSL_PRECISION_MP; 467#endif 468 469 precision_env = getenv(OSL_PRECISION_ENV); 470 if (precision_env != NULL) { 471 if (!strcmp(precision_env, OSL_PRECISION_ENV_SP)) 472 precision = OSL_PRECISION_SP; 473 else if (!strcmp(precision_env, OSL_PRECISION_ENV_DP)) 474 precision = OSL_PRECISION_DP; 475 else if (!strcmp(precision_env, OSL_PRECISION_ENV_MP)) { 476#ifndef OSL_GMP_IS_HERE 477 OSL_warning("$OSL_PRECISION says GMP but osl not compiled with " 478 "GMP support, switching to double precision"); 479 precision = OSL_PRECISION_DP; 480#else 481 precision = OSL_PRECISION_MP; 482#endif 483 } 484 else 485 OSL_warning("bad OSL_PRECISION environment value, see osl's manual"); 486 } 487 488 return precision; 489} 490 491 492/** 493 * osl_util_print_provided function: 494 * this function prints a "provided" boolean in a file (file, possibly stdout), 495 * with a comment title according to the OpenScop specification. 496 * \param[in] file File where the information has to be printed. 497 * \param[in] provided The provided boolean to print. 498 * \param[in] title A string to use as a title for the provided booblean. 499 */ 500void osl_util_print_provided(FILE * file, int provided, char * title) { 501 if (provided) { 502 fprintf(file, "# %s provided\n", title); 503 fprintf(file, "1\n"); 504 } 505 else { 506 fprintf(file, "# %s not provided\n", title); 507 fprintf(file, "0\n\n"); 508 } 509} 510 511 512/** 513 * osl_util_identifier_is_here function: 514 * this function returns 1 if the input "identifier" is found at the 515 * "index" position in the "expression" input string, 0 otherwise. 516 * \param[in] expression The input expression. 517 * \param[in] identifier The identifier to look for. 518 * \param[in] index The position in the expression where to look. 519 * \return 1 if the identifier is found at the position in the expression. 520 */ 521static 522int osl_util_identifier_is_here(char * expression, char * identifier, 523 int index) { 524 // If there is no space enough to find the identifier: no. 525 if (strlen(identifier) + index > strlen(expression)) 526 return 0; 527 528 // If there is a character before and it is in [A-Za-z0-9]: no. 529 if ((index > 0) && 530 (((expression[index - 1] >= 'A') && (expression[index - 1] <= 'Z')) || 531 ((expression[index - 1] >= 'a') && (expression[index - 1] <= 'z')) || 532 ((expression[index - 1] >= '0') && (expression[index - 1] <= '9')))) 533 return 0; 534 535 // If there is a character after and it is in [A-Za-z0-9]: no. 536 if ((strlen(identifier) + index < strlen(expression)) && 537 (((expression[strlen(identifier) + index] >= 'A') && 538 (expression[strlen(identifier) + index] <= 'Z')) || 539 ((expression[strlen(identifier) + index] >= 'a') && 540 (expression[strlen(identifier) + index] <= 'z')) || 541 ((expression[strlen(identifier) + index] >= '0') && 542 (expression[strlen(identifier) + index] <= '9')))) 543 return 0; 544 545 // If the identifier string is not here: no. 546 if (strncmp(expression + index, identifier, strlen(identifier))) 547 return 0; 548 549 return 1; 550} 551 552 553/** 554 * osl_util_lazy_isolated_identifier function: 555 * this function returns 1 if the identifier at the "index" position in the 556 * "expression" is guaranteed not to need parenthesis around is we 557 * substitute it with anything. For instance the identifier "i" can be 558 * always substituted in "A[i]" with no need of parenthesis but not in 559 * "A[2*i]". This function is lazy in the sense that it just check obvious 560 * cases, not all of them. The identifier must already be at the indicated 561 * position, this function does not check that. 562 * \param[in] expression The input expression. 563 * \param[in] identifier The identifier to check. 564 * \param[in] index The position of the identifier in the expression. 565 * \return 1 if the identifier is isolated, 0 if unsure. 566 */ 567static 568int osl_util_lazy_isolated_identifier(char * expression, char * identifier, 569 int index) { 570 int look; 571 572 // If the first non-space character before is not in [\[(,\+=]: no. 573 look = index - 1; 574 while (look >= 0) { 575 if (isspace(expression[look])) 576 look--; 577 else 578 break; 579 } 580 581 if ((look >= 0) && 582 (expression[look] != '[') && 583 (expression[look] != '(') && 584 (expression[look] != '+') && 585 (expression[look] != '=') && 586 (expression[look] != ',')) 587 return 0; 588 589 // If the first non-space character after is not in [\]),;\+]: no. 590 look = index + strlen(identifier); 591 while (look < strlen(expression)) { 592 if (isspace(expression[look])) 593 look++; 594 else 595 break; 596 } 597 598 if ((look < strlen(expression)) && 599 (expression[look] != ']') && 600 (expression[look] != ')') && 601 (expression[look] != '+') && 602 (expression[look] != ',') && 603 (expression[look] != ';')) 604 return 0; 605 606 return 1; 607} 608 609 610/** 611 * osl_util_identifier_substitution function: 612 * this function replaces some identifiers in an input expression string and 613 * returns the final string. The list of identifiers to replace are provided 614 * as an array of strings. They are replaced from the input string with the 615 * new substring "@i@" or "(@i@)" where i is the rank of the identifier in the 616 * array of identifiers. The parentheses are added when it is not obvious that 617 * the identifier can be replaced with an arbitrary expression without the 618 * need of parentheses. For instance, let us consider the input expression 619 * "C[i+j]+=A[2*i]*B[j];" and the array of strings {"i", "j"}: the resulting 620 * string would be "C[@0@+@1@]+=A[2*(@0@)]*B[@1@];". 621 * \param[in] expression The original expression. 622 * \param[in] identifiers NULL-terminated array of identifiers. 623 * \return A new string where the ith identifier is replaced by \@i\@. 624 */ 625char * osl_util_identifier_substitution(char * expression, 626 char ** identifiers) { 627 int index, j, found; 628 int high_water_mark = OSL_MAX_STRING; 629 char buffer[OSL_MAX_STRING]; 630 char * string; 631 632 OSL_malloc(string, char *, high_water_mark * sizeof(char)); 633 string[0] = '\0'; 634 635 index = 0; 636 while (index < strlen(expression)) { 637 j = 0; 638 found = 0; 639 while (identifiers[j] != NULL) { 640 if (osl_util_identifier_is_here(expression, identifiers[j], index)) { 641 if (osl_util_lazy_isolated_identifier(expression,identifiers[j],index)) 642 sprintf(buffer, "@%d@", j); 643 else 644 sprintf(buffer, "(@%d@)", j); 645 osl_util_safe_strcat(&string, buffer, &high_water_mark); 646 index += strlen(identifiers[j]); 647 found = 1; 648 break; 649 } 650 j++; 651 } 652 if (!found) { 653 sprintf(buffer, "%c", expression[index]); 654 osl_util_safe_strcat(&string, buffer, &high_water_mark); 655 index++; 656 } 657 } 658 659 return string; 660} 661 662 663 664