compiler2/string.cc

   1 /******************************************************************************
   2  * Copyright (c) 2000-2016 Ericsson Telecom AB
   3  * All rights reserved. This program and the accompanying materials
   4  * are made available under the terms of the Eclipse Public License v1.0
   5  * which accompanies this distribution, and is available at
   6  * http://www.eclipse.org/legal/epl-v10.html
   7  *
   8  * Contributors:
   9  *   Balasko, Jeno
  10  *   Forstner, Matyas
  11  *   Gecse, Roland
  12  *   Kremer, Peter
  13  *   Raduly, Csaba
  14  *   Szabados, Kristof
  15  *   Szabo, Janos Zoltan – initial implementation
  16  *   Zalanyi, Balazs Andor
  17  *
  18  ******************************************************************************/
  19 #include <stdio.h>
  20 #include <string.h>
  21 #include <stddef.h>
  22 #include <ctype.h>
  23
  24 #include "../common/memory.h"
  25 #include "error.h"
  26
  27 #include "string.hh"
  28 #include "ustring.hh"
  29
  30 #include "Int.hh"
  31
  32 /** Parameters for tuning memory usage of class stringpool */
  33 #define STRINGPOOL_INITIAL_SIZE 8
  34 #define STRINGPOOL_INCREMENT_FACTOR 2
  35
  36 /** The amount of memory needed for a string containing n characters. */
  37 #define MEMORY_SIZE(n) (sizeof(string_struct) - sizeof(size_t) + 1 + (n))
  38
  39 void string::init_struct(size_t n_chars)
  40 {
  41   if (n_chars == 0) {
  42     /** This will represent the empty strings so they won't need allocated
  43      * memory, this delays the memory allocation until it is really needed. */
  44     static string_struct empty_string = { 1, 0, "" };
  45     val_ptr = &empty_string;
  46     empty_string.ref_count++;
  47   } else {
  48     val_ptr = static_cast<string_struct*>(Malloc(MEMORY_SIZE(n_chars)));
  49     val_ptr->ref_count = 1;
  50     val_ptr->n_chars = n_chars;
  51     val_ptr->chars_ptr[n_chars] = '\0';
  52   }
  53 }
  54
  55 void string::copy_value_and_append(const char *s, size_t n)
  56 {
  57   if (n > max_string_len - val_ptr->n_chars)
  58     FATAL_ERROR("string::copy_value_and_append(const char*, size_t): " \
  59       "length overflow");
  60   if (val_ptr->ref_count == 1) {
  61     ptrdiff_t offset = s - val_ptr->chars_ptr;
  62     val_ptr = static_cast<string_struct*>
  63       (Realloc(val_ptr, MEMORY_SIZE(val_ptr->n_chars + n)));
  64     // check whether the source buffer s is (part of) our existing buffer
  65     if (offset >= 0 && static_cast<size_t>(offset) < val_ptr->n_chars)
  66       memcpy(val_ptr->chars_ptr + val_ptr->n_chars,
  67              val_ptr->chars_ptr + offset, n);
  68     else memcpy(val_ptr->chars_ptr + val_ptr->n_chars, s, n);
  69     val_ptr->n_chars += n;
  70     val_ptr->chars_ptr[val_ptr->n_chars] = '\0';
  71   } else {
  72     string_struct *old_ptr = val_ptr;
  73     old_ptr->ref_count--;
  74     init_struct(old_ptr->n_chars + n);
  75     memcpy(val_ptr->chars_ptr, old_ptr->chars_ptr, old_ptr->n_chars);
  76     memcpy(val_ptr->chars_ptr + old_ptr->n_chars, s, n);
  77   }
  78 }
  79
  80 /** Internal worker for various replace() methods.
  81  *
  82  * @param pos   the index of the first character to replace
  83  * @param n     the number of characters to replace
  84  * @param s     the replacement
  85  * @param s_len the length of the replacement
  86  *
  87  * @pre \p pos        must point inside the string
  88  * @pre \p pos + \p n must point inside the string
  89  * @pre the resulting string must not exceed max_string_len
  90  */
  91 void string::replace(size_t pos, size_t n, const char *s, size_t s_len)
  92 {
  93   if (pos > val_ptr->n_chars)
  94     FATAL_ERROR("string::replace(): start position is outside the string");
  95   if (pos + n > val_ptr->n_chars)
  96     FATAL_ERROR("string::replace(): end position is outside the string");
  97   if (s_len > max_string_len - val_ptr->n_chars + n)
  98     FATAL_ERROR("string::replace(): length overflow");
  99   // do nothing if we are replacing with the same string
 100   if (n == s_len && memcmp(val_ptr->chars_ptr + pos, s, n) == 0) return;
 101   size_t new_size = val_ptr->n_chars - n + s_len;
 102   if (new_size == 0) {
 103     // the result is an empty string
 104     clean_up(val_ptr);
 105     init_struct(0);
 106   } else if (val_ptr->ref_count == 1 && (s < val_ptr->chars_ptr ||
 107       s >= val_ptr->chars_ptr + val_ptr->n_chars)) {
 108     // check whether this string is not referenced by others and we are not
 109     // replacing with ourselves
 110     if (val_ptr->n_chars < new_size) val_ptr = static_cast<string_struct*>
 111         (Realloc(val_ptr, MEMORY_SIZE(new_size)));
 112     memmove(val_ptr->chars_ptr + pos + s_len,
 113             val_ptr->chars_ptr + pos + n, val_ptr->n_chars - pos - n);
 114     memcpy(val_ptr->chars_ptr + pos, s, s_len);
 115     if (val_ptr->n_chars > new_size) val_ptr = static_cast<string_struct*>
 116         (Realloc(val_ptr, MEMORY_SIZE(new_size)));
 117     val_ptr->n_chars = new_size;
 118     val_ptr->chars_ptr[new_size] = '\0';
 119   } else {
 120     // the result must be copied into a new memory area
 121     string_struct *old_ptr = val_ptr;
 122     old_ptr->ref_count--;
 123     init_struct(new_size);
 124     memcpy(val_ptr->chars_ptr, old_ptr->chars_ptr, pos);
 125     memcpy(val_ptr->chars_ptr + pos, s, s_len);
 126     memcpy(val_ptr->chars_ptr + pos + s_len, old_ptr->chars_ptr + pos + n,
 127       old_ptr->n_chars - pos - n);
 128     if (old_ptr->ref_count == 0) Free(old_ptr);
 129   }
 130 }
 131
 132 void string::clean_up(string_struct *ptr)
 133 {
 134   if (ptr->ref_count > 1) ptr->ref_count--;
 135   else if (ptr->ref_count == 1) Free(ptr);
 136   else FATAL_ERROR("string::clean_up()");
 137 }
 138
 139 int string::compare(const string& s) const
 140 {
 141   if (val_ptr == s.val_ptr) return 0;
 142   else return strcmp(val_ptr->chars_ptr, s.val_ptr->chars_ptr);
 143 }
 144
 145 int string::compare(const char *s) const
 146 {
 147   if (val_ptr->chars_ptr == s) return 0;
 148   else return strcmp(val_ptr->chars_ptr, s);
 149 }
 150
 151 string::string(const char *s)
 152 {
 153   if (s == NULL) FATAL_ERROR("string::string(const char*): called with NULL");
 154   size_t n_chars = strlen(s);
 155   init_struct(n_chars);
 156   memcpy(val_ptr->chars_ptr, s, n_chars);
 157 }
 158
 159 string::string(size_t n, const char *s)
 160 {
 161   if (s == NULL && n > 0)
 162     FATAL_ERROR("string::string(size_t, const char*): called with NULL");
 163   init_struct(n);
 164   memcpy(val_ptr->chars_ptr, s, n);
 165 }
 166
 167 string::string(const ustring& s)
 168 {
 169   size_t s_len = s.size();
 170   init_struct(s_len);
 171   const ustring::universal_char *src = s.u_str();
 172   for (size_t i = 0; i < s_len; i++) {
 173     if (src[i].group != 0 || src[i].plane != 0 || src[i].row != 0)
 174       FATAL_ERROR("string::string(const ustring&)");
 175     val_ptr->chars_ptr[i] = src[i].cell;
 176   }
 177 }
 178
 179 bool string::is_cstr() const
 180 {
 181   for (size_t i = 0; i < val_ptr->n_chars; i++)
 182     if ((unsigned char)val_ptr->chars_ptr[i] > 127) return false;
 183   return true;
 184 }
 185
 186 void string::clear()
 187 {
 188   if (val_ptr->n_chars > 0) {
 189     clean_up(val_ptr);
 190     init_struct(0);
 191   }
 192 }
 193
 194 string string::substr(size_t pos, size_t n) const
 195 {
 196   if (pos > val_ptr->n_chars)
 197     FATAL_ERROR("string::substr(size_t, size_t): position is outside the " \
 198       "string");
 199   size_t n_chars = val_ptr->n_chars - pos;
 200   if (n_chars > n) n_chars = n;
 201   if (n_chars == val_ptr->n_chars) return *this;
 202   else return string(n_chars, val_ptr->chars_ptr + pos);
 203 }
 204
 205 void string::resize(size_t n, char c)
 206 {
 207   size_t old_length = val_ptr->n_chars;
 208   if (old_length == n) return;
 209   if (val_ptr->ref_count == 1) {
 210     if (n > 0) {
 211       val_ptr = static_cast<string_struct*>(Realloc(val_ptr, MEMORY_SIZE(n)));
 212       if (n > old_length) {
 213         memset(val_ptr->chars_ptr + old_length, c, n - old_length);
 214       }
 215       val_ptr->chars_ptr[n] = '\0';
 216       val_ptr->n_chars = n;
 217     } else {
 218       clean_up(val_ptr);
 219       init_struct(0);
 220     }
 221   } else {
 222     val_ptr->ref_count--;
 223     string_struct *tmp_ptr = val_ptr;
 224     init_struct(n);
 225     if (n > old_length) {
 226       memcpy(val_ptr->chars_ptr, tmp_ptr->chars_ptr, old_length);
 227       memset(val_ptr->chars_ptr + old_length, c, n - old_length);
 228     } else {
 229       memcpy(val_ptr->chars_ptr, tmp_ptr->chars_ptr, n);
 230     }
 231   }
 232 }
 233
 234 void string::replace(size_t pos, size_t n, const char *s)
 235 {
 236   if (s == NULL) FATAL_ERROR("string::replace(size_t, size_t, const char*): " \
 237     "called with NULL");
 238   replace(pos, n, s, strlen(s));
 239 }
 240
 241 void string::replace(size_t pos, size_t n, const string& s)
 242 {
 243   if (pos == 0 && n == val_ptr->n_chars) *this = s;
 244   else replace(pos, n, s.val_ptr->chars_ptr, s.val_ptr->n_chars);
 245 }
 246
 247 size_t string::find(char c, size_t pos) const
 248 {
 249   if (pos > val_ptr->n_chars)
 250     FATAL_ERROR("string::find(char, size_t): position is outside of string");
 251   for (size_t r = pos; r < val_ptr->n_chars; r++)
 252     if (c == val_ptr->chars_ptr[r]) return r;
 253   return val_ptr->n_chars;
 254 }
 255
 256 size_t string::find(const char *s, size_t pos) const
 257 {
 258   if (s == NULL)
 259     FATAL_ERROR("string::find(const char *, size_t): called with NULL");
 260   if (pos >= val_ptr->n_chars)
 261     FATAL_ERROR("string::find(const char *, size_t): position outside of string");
 262   const char *ptr = strstr(val_ptr->chars_ptr + pos, s);
 263   if (ptr != NULL) return ptr - val_ptr->chars_ptr;
 264   else return val_ptr->n_chars;
 265 }
 266
 267 size_t string::rfind(char c, size_t pos) const
 268 {
 269   if (pos > val_ptr->n_chars) pos = val_ptr->n_chars;
 270   for (size_t i = pos; i > 0; i--)
 271     if (c == val_ptr->chars_ptr[i - 1]) return i - 1;
 272   return val_ptr->n_chars;
 273 }
 274
 275 size_t string::find_if(size_t first, size_t last, int (*pred)(int)) const
 276 {
 277   if (first > last) FATAL_ERROR("string::find_if(): first greater than last");
 278   else if (last > val_ptr->n_chars)
 279     FATAL_ERROR("string::find_if(): last greater than string length");
 280   for (size_t r = first; r < last; r++)
 281     if (pred(val_ptr->chars_ptr[r])) return r;
 282   return last;
 283 }
 284
 285 bool string::is_whitespace(unsigned char c)
 286 {
 287   switch (c) {
 288   case ' ':
 289   case '\t':
 290   case '\n':
 291   case '\r':
 292   case '\v':
 293   case '\f':
 294     return true;
 295   default:
 296     return false;
 297   }
 298 }
 299
 300 bool string::is_printable(unsigned char c)
 301 {
 302   if (isprint(c)) return true;
 303   else {
 304     switch (c) {
 305     case '\a':
 306     case '\b':
 307     case '\t':
 308     case '\n':
 309     case '\v':
 310     case '\f':
 311     case '\r':
 312       return true;
 313     default:
 314       return false;
 315     }
 316   }
 317 }
 318
 319 void string::append_stringRepr(char c)
 320 {
 321   switch (c) {
 322   case '\a':
 323     *this += "\\a";
 324     break;
 325   case '\b':
 326     *this += "\\b";
 327     break;
 328   case '\t':
 329     *this += "\\t";
 330     break;
 331   case '\n':
 332     *this += "\\n";
 333     break;
 334   case '\v':
 335     *this += "\\v";
 336     break;
 337   case '\f':
 338     *this += "\\f";
 339     break;
 340   case '\r':
 341     *this += "\\r";
 342     break;
 343   case '\\':
 344     *this += "\\\\";
 345     break;
 346   case '"':
 347     *this += "\\\"";
 348     break;
 349   default:
 350     if (is_printable(c)) *this += c;
 351     else FATAL_ERROR("string::append_stringRepr()");
 352     break;
 353   }
 354 }
 355
 356 string string::get_stringRepr() const
 357 {
 358   string ret_val;
 359   enum { INIT, PCHAR, NPCHAR } state = INIT;
 360   for (size_t i = 0; i < val_ptr->n_chars; i++) {
 361     char c = val_ptr->chars_ptr[i];
 362     if (is_printable(c)) {
 363       // the actual character is printable
 364       switch (state) {
 365       case NPCHAR: // concatenation sign if previous part was not printable
 366         ret_val += " & ";
 367         // no break
 368       case INIT: // opening "
 369         ret_val += '"';
 370         // no break
 371       case PCHAR: // the character itself
 372         ret_val.append_stringRepr(c);
 373         break;
 374       }
 375       state = PCHAR;
 376     } else {
 377       // the actual character is not printable
 378       switch (state) {
 379       case PCHAR: // closing " if previous part was printable
 380         ret_val += '"';
 381         // no break
 382       case NPCHAR: // concatenation sign
 383         ret_val += " & ";
 384         // no break
 385       case INIT: // the character itself in quadruple notation
 386         ret_val += "char(0, 0, 0, ";
 387         ret_val += Common::Int2string((unsigned char)c);
 388         ret_val += ')';
 389         break;
 390       }
 391       state = NPCHAR;
 392     }
 393   }
 394   // final steps
 395   switch (state) {
 396   case INIT: // the string was empty
 397     ret_val += "\"\"";
 398     break;
 399   case PCHAR: // last character was printable -> closing "
 400     ret_val += '"';
 401     break;
 402   default:
 403     break;
 404   }
 405   return ret_val;
 406 }
 407
 408 ustring string::convert_stringRepr_for_pattern() const {
 409   ustring ret_val;
 410
 411   if (val_ptr->n_chars % 8 != 0)
 412     FATAL_ERROR("string::convert_stringRepr_for_pattern(): Cannot create"
 413       "universal string. Length must be a multiple of 8.");
 414
 415   unsigned char c1, c2;
 416   unsigned char array[4];
 417   size_t index = 0;
 418   while (index < val_ptr->n_chars) {
 419     for (size_t j = 0; j < 4; j++) {
 420       c1 = (unsigned char)val_ptr->chars_ptr[index++];
 421       c2 = (unsigned char)val_ptr->chars_ptr[index++];
 422       if (c1 >= 'A' && c1 <= 'P' && c2 >= 'A' && c2 <= 'P') {
 423         array[j] = ((c1 - 'A') << 4) | (c2 - 'A');
 424       } else
 425         FATAL_ERROR("string::convert_stringRepr_for_pattern(): Cannot create"
 426           "universal string. Source contains illegal character.");
 427     }
 428     ret_val += ustring(array[0], array[1], array[2], array[3]);
 429   }
 430   return ret_val;
 431 }
 432
 433 string& string::operator=(const string& s)
 434 {
 435   if (&s != this) {
 436     clean_up(val_ptr);
 437     val_ptr = s.val_ptr;
 438     val_ptr->ref_count++;
 439   }
 440   return *this;
 441 }
 442
 443 string& string::operator=(const char *s)
 444 {
 445   if (s == NULL)
 446     FATAL_ERROR("string::operator=(const char*): called with NULL");
 447   if (val_ptr->chars_ptr != s) {
 448       clean_up(val_ptr);
 449       size_t n_chars = strlen(s);
 450       init_struct(n_chars);
 451       memcpy(val_ptr->chars_ptr, s, n_chars);
 452   }
 453   return *this;
 454 }
 455
 456 char& string::operator[](size_t n)
 457 {
 458   if (n >= val_ptr->n_chars)
 459     FATAL_ERROR("string::operator[](size_t): position is outside the string");
 460   if (val_ptr->ref_count > 1) {
 461     string_struct *old_ptr = val_ptr;
 462     old_ptr->ref_count--;
 463     init_struct(old_ptr->n_chars);
 464     memcpy(val_ptr->chars_ptr, old_ptr->chars_ptr, old_ptr->n_chars);
 465   }
 466   return val_ptr->chars_ptr[n];
 467 }
 468
 469 char string::operator[](size_t n) const
 470 {
 471   if (n >= val_ptr->n_chars)
 472     FATAL_ERROR("string::operator[](size_t) const: position is outside the string");
 473   return val_ptr->chars_ptr[n];
 474 }
 475
 476 string string::operator+(const string& s) const
 477 {
 478   if (s.val_ptr->n_chars > max_string_len - val_ptr->n_chars)
 479     FATAL_ERROR("string::operator+(const string&): length overflow");
 480   if (val_ptr->n_chars == 0) return s;
 481   else if (s.val_ptr->n_chars == 0) return *this;
 482   else {
 483     string ret_val(val_ptr->n_chars + s.val_ptr->n_chars);
 484     memcpy(ret_val.val_ptr->chars_ptr, val_ptr->chars_ptr, val_ptr->n_chars);
 485     memcpy(ret_val.val_ptr->chars_ptr + val_ptr->n_chars,
 486            s.val_ptr->chars_ptr, s.val_ptr->n_chars);
 487     return ret_val;
 488   }
 489 }
 490
 491 string string::operator+(const char *s) const
 492 {
 493   if (s == NULL)
 494     FATAL_ERROR("string::operator+(const char*): called with NULL)");
 495   size_t s_len = strlen(s);
 496   if (s_len > max_string_len - val_ptr->n_chars)
 497     FATAL_ERROR("string::operator+(const char*): length overflow");
 498   if (s_len == 0) return *this;
 499   else {
 500     string ret_val(val_ptr->n_chars + s_len);
 501     memcpy(ret_val.val_ptr->chars_ptr, val_ptr->chars_ptr, val_ptr->n_chars);
 502     memcpy(ret_val.val_ptr->chars_ptr + val_ptr->n_chars, s, s_len);
 503     return ret_val;
 504   }
 505 }
 506
 507 string& string::operator+=(const string& s)
 508 {
 509   if (s.val_ptr->n_chars > 0) {
 510     if (val_ptr->n_chars > 0) {
 511       copy_value_and_append(s.val_ptr->chars_ptr, s.val_ptr->n_chars);
 512     } else {
 513       clean_up(val_ptr);
 514       val_ptr = s.val_ptr;
 515       val_ptr->ref_count++;
 516     }
 517   }
 518   return *this;
 519 }
 520
 521 string& string::operator+=(const char *s)
 522 {
 523   if (s == NULL)
 524     FATAL_ERROR("string::operator+=(const char*): called with NULL");
 525   size_t s_len = strlen(s);
 526   if (s_len > 0) copy_value_and_append(s, s_len);
 527   return *this;
 528 }
 529
 530 bool string::operator==(const string& s) const
 531 {
 532   if (val_ptr == s.val_ptr) return true;
 533   else if (val_ptr->n_chars != s.val_ptr->n_chars) return false;
 534   else return memcmp(val_ptr->chars_ptr, s.val_ptr->chars_ptr,
 535     val_ptr->n_chars) == 0;
 536 }
 537
 538 bool string::operator==(const char *s) const
 539 {
 540   if (s == NULL)
 541     FATAL_ERROR("string::operator==(const char*): called with NULL");
 542   if (s == val_ptr->chars_ptr) return true;
 543   else return strcmp(val_ptr->chars_ptr, s) == 0;
 544 }
 545
 546 string operator+(const char *s1, const string& s2)
 547 {
 548   if (s1 == NULL)
 549     FATAL_ERROR("operator+(const char *, const string&): called with NULL");
 550   size_t s1_len = strlen(s1);
 551   if (s1_len > string::max_string_len - s2.val_ptr->n_chars)
 552     FATAL_ERROR("operator+(const char *,const string&): length overflow");
 553   if (s1_len > 0) {
 554     string s(s1_len + s2.val_ptr->n_chars);
 555     memcpy(s.val_ptr->chars_ptr, s1, s1_len);
 556     memcpy(s.val_ptr->chars_ptr + s1_len, s2.val_ptr->chars_ptr,
 557             s2.val_ptr->n_chars);
 558     return s;
 559   } else return s2;
 560 }
 561
 562 void stringpool::clear()
 563 {
 564   for (size_t i = 0; i < list_len; i++) string::clean_up(string_list[i]);
 565   Free(string_list);
 566   string_list = NULL;
 567   list_size = 0;
 568   list_len = 0;
 569 }
 570
 571 const char *stringpool::add(const string& s)
 572 {
 573   if (list_len > list_size) FATAL_ERROR("stringpool::add()");
 574   else if (list_len == list_size) {
 575     if (list_size == 0) {
 576       string_list = static_cast<string::string_struct**>
 577         (Malloc(STRINGPOOL_INITIAL_SIZE * sizeof(*string_list)));
 578       list_size = STRINGPOOL_INITIAL_SIZE;
 579     } else {
 580       list_size *= STRINGPOOL_INCREMENT_FACTOR;
 581       string_list = static_cast<string::string_struct**>
 582         (Realloc(string_list, list_size * sizeof(*string_list)));
 583     }
 584     if (list_len >= list_size) FATAL_ERROR("stringpool::add()");
 585   }
 586   string::string_struct *val_ptr = s.val_ptr;
 587   string_list[list_len++] = val_ptr;
 588   val_ptr->ref_count++;
 589   return val_ptr->chars_ptr;
 590 }
 591
 592 const char *stringpool::get_str(size_t n) const
 593 {
 594   if (n >= list_len) FATAL_ERROR("stringpool::get_str()");
 595   return string_list[n]->chars_ptr;
 596 }
 597
 598 string stringpool::get_string(size_t n) const
 599 {
 600   if (n >= list_len) FATAL_ERROR("stringpool::get_string()");
 601   return string(string_list[n]);
 602 }