Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
73279a41e80eb3d9d22017d726427f01279b659a
[simgrid.git] / src / xbt / xbt_str.c
1 /* $Id$ */
2
3 /* xbt_str.c - various helping functions to deal with strings               */
4
5 /* Copyright (C) 2005-2008 The SimGrid Team.                                */
6 /* All rights reserved.                                                     */
7
8 /* This program is free software; you can redistribute it and/or modify it
9  * under the terms of the license (GNU LGPL) which comes with this package.
10  */
11
12 #include "xbt/misc.h"
13 #include "xbt/sysdep.h"
14 #include "xbt/str.h"            /* headers of these functions */
15 #include "xbt/strbuff.h"
16 #include "portable.h"
17 #include "xbt/matrix.h"         /* for the diff */
18
19 /**  @brief Strip whitespace (or other characters) from the end of a string.
20  *
21  * Strips the whitespaces from the end of s.
22  * By default (when char_list=NULL), these characters get stripped:
23  *
24  *      - " "           (ASCII 32       (0x20)) space.
25  *      - "\t"          (ASCII 9        (0x09)) tab.
26  *      - "\n"          (ASCII 10       (0x0A)) line feed.
27  *      - "\r"          (ASCII 13       (0x0D)) carriage return.
28  *      - "\0"          (ASCII 0        (0x00)) NULL.
29  *      - "\x0B"        (ASCII 11       (0x0B)) vertical tab.
30  *
31  * @param s The string to strip. Modified in place.
32  * @param char_list A string which contains the characters you want to strip.
33  *
34  */
35 void xbt_str_rtrim(char *s, const char *char_list)
36 {
37   char *cur = s;
38   const char *__char_list = " \t\n\r\x0B";
39   char white_char[256] = { 1, 0 };
40
41   if (!s)
42     return;
43
44   if (!char_list) {
45     while (*__char_list) {
46       white_char[(unsigned char) *__char_list++] = 1;
47     }
48   } else {
49     while (*char_list) {
50       white_char[(unsigned char) *char_list++] = 1;
51     }
52   }
53
54   while (*cur)
55     ++cur;
56
57   while ((cur >= s) && white_char[(unsigned char) *cur])
58     --cur;
59
60   *++cur = '\0';
61 }
62
63 /**  @brief Strip whitespace (or other characters) from the beginning of a string.
64  *
65  * Strips the whitespaces from the begining of s.
66  * By default (when char_list=NULL), these characters get stripped:
67  *
68  *      - " "           (ASCII 32       (0x20)) space.
69  *      - "\t"          (ASCII 9        (0x09)) tab.
70  *      - "\n"          (ASCII 10       (0x0A)) line feed.
71  *      - "\r"          (ASCII 13       (0x0D)) carriage return.
72  *      - "\0"          (ASCII 0        (0x00)) NULL.
73  *      - "\x0B"        (ASCII 11       (0x0B)) vertical tab.
74  *
75  * @param s The string to strip. Modified in place.
76  * @param char_list A string which contains the characters you want to strip.
77  *
78  */
79 void xbt_str_ltrim(char *s, const char *char_list)
80 {
81   char *cur = s;
82   const char *__char_list = " \t\n\r\x0B";
83   char white_char[256] = { 1, 0 };
84
85   if (!s)
86     return;
87
88   if (!char_list) {
89     while (*__char_list) {
90       white_char[(unsigned char) *__char_list++] = 1;
91     }
92   } else {
93     while (*char_list) {
94       white_char[(unsigned char) *char_list++] = 1;
95     }
96   }
97
98   while (*cur && white_char[(unsigned char) *cur])
99     ++cur;
100
101   memmove(s, cur, strlen(cur) + 1);
102 }
103
104 /**  @brief Strip whitespace (or other characters) from the end and the begining of a string.
105  *
106  * Strips the whitespaces from both the beginning and the end of s.
107  * By default (when char_list=NULL), these characters get stripped:
108  *
109  *      - " "           (ASCII 32       (0x20)) space.
110  *      - "\t"          (ASCII 9        (0x09)) tab.
111  *      - "\n"          (ASCII 10       (0x0A)) line feed.
112  *      - "\r"          (ASCII 13       (0x0D)) carriage return.
113  *      - "\0"          (ASCII 0        (0x00)) NULL.
114  *      - "\x0B"        (ASCII 11       (0x0B)) vertical tab.
115  *
116  * @param s The string to strip.
117  * @param char_list A string which contains the characters you want to strip.
118  *
119  */
120 void xbt_str_trim(char *s, const char *char_list)
121 {
122
123   if (!s)
124     return;
125
126   xbt_str_rtrim(s, char_list);
127   xbt_str_ltrim(s, char_list);
128 }
129
130 /**  @brief Replace double whitespaces (but no other characters) from the string.
131  *
132  * The function modifies the string so that each time that several spaces appear,
133  * they are replaced by a single space. It will only do so for spaces (ASCII 32, 0x20).
134  *
135  * @param s The string to strip. Modified in place.
136  *
137  */
138 void xbt_str_strip_spaces(char *s)
139 {
140   char *p = s;
141   int e = 0;
142
143   if (!s)
144     return;
145
146   while (1) {
147     if (!*p)
148       goto end;
149
150     if (*p != ' ')
151       break;
152
153     p++;
154   }
155
156   e = 1;
157
158   do {
159     if (e)
160       *s++ = *p;
161
162     if (!*++p)
163       goto end;
164
165     if (e ^ (*p != ' '))
166       if ((e = !e))
167         *s++ = ' ';
168   } while (1);
169
170 end:
171   *s = '\0';
172 }
173
174 /** @brief Substitutes a char for another in a string
175  *
176  * @param str the string to modify
177  * @param from char to search
178  * @param to char to put instead
179  * @param amount amount of changes to do (=0 means all)
180  */
181 void xbt_str_subst(char *str, char from, char to, int occurence)
182 {
183   char *p = str;
184   while (*p != '\0') {
185     if (*p == from) {
186       *p = to;
187       if (occurence == 1)
188         return;
189       occurence--;
190     }
191     p++;
192   }
193 }
194
195 /** @brief Replaces a set of variables by their values
196  *
197  * @param str where to apply the change
198  * @param patterns what to change
199  * @return The string modified
200  *
201  * Check xbt_strbuff_varsubst() for more details, and remember that the string may be reallocated (moved) in the process.
202  */
203
204 char *xbt_str_varsubst(char *str, xbt_dict_t patterns)
205 {
206   xbt_strbuff_t buff = xbt_strbuff_new_from(str);
207   char *res;
208   xbt_strbuff_varsubst(buff, patterns);
209   res = buff->data;
210   xbt_strbuff_free_container(buff);
211   return res;
212 }
213
214
215 /** @brief Splits a string into a dynar of strings
216  *
217  * @param s: the string to split
218  * @param sep: a string of all chars to consider as separator.
219  *
220  * By default (with sep=NULL), these characters are used as separator:
221  *
222  *      - " "           (ASCII 32       (0x20)) space.
223  *      - "\t"          (ASCII 9        (0x09)) tab.
224  *      - "\n"          (ASCII 10       (0x0A)) line feed.
225  *      - "\r"          (ASCII 13       (0x0D)) carriage return.
226  *      - "\0"          (ASCII 0        (0x00)) NULL.
227  *      - "\x0B"        (ASCII 11       (0x0B)) vertical tab.
228  */
229
230 xbt_dynar_t xbt_str_split(const char *s, const char *sep)
231 {
232   xbt_dynar_t res = xbt_dynar_new(sizeof(char *), xbt_free_ref);
233   const char *p, *q;
234   int done;
235   const char *sep_dflt = " \t\n\r\x0B";
236   char is_sep[256] = { 1, 0 };
237
238   /* check what are the separators */
239   memset(is_sep, 0, sizeof(is_sep));
240   if (!sep) {
241     while (*sep_dflt)
242       is_sep[(unsigned char) *sep_dflt++] = 1;
243   } else {
244     while (*sep)
245       is_sep[(unsigned char) *sep++] = 1;
246   }
247   is_sep[0] = 1;                /* End of string is also separator */
248
249   /* Do the job */
250   p = q = s;
251   done = 0;
252
253   if (s[0] == '\0')
254     return res;
255
256   while (!done) {
257     char *topush;
258     while (!is_sep[(unsigned char) *q]) {
259       q++;
260     }
261     if (*q == '\0')
262       done = 1;
263
264     topush = xbt_malloc(q - p + 1);
265     memcpy(topush, p, q - p);
266     topush[q - p] = '\0';
267     xbt_dynar_push(res, &topush);
268     p = ++q;
269   }
270
271   return res;
272 }
273
274 /**
275  * \brief This functions splits a string after using another string as separator
276  * For example A!!B!!C splitted after !! will return the dynar {A,B,C}
277  * \return An array of dynars containing the string tokens
278  */
279 xbt_dynar_t xbt_str_split_str(const char *s, const char *sep)
280 {
281   xbt_dynar_t res = xbt_dynar_new(sizeof(char *), xbt_free_ref);
282   int done;
283   const char *p, *q;
284
285   p = q = s;
286   done = 0;
287
288   if (s[0] == '\0')
289     return res;
290   if (sep[0] == '\0') {
291     s = xbt_strdup(s);
292     xbt_dynar_push(res, &s);
293     return res;
294   }
295
296   while (!done) {
297     char *to_push;
298     int v = 0;
299     //get the start of the first occurence of the substring
300     q = strstr(p, sep);
301     //if substring was not found add the entire string
302     if (NULL == q) {
303       v = strlen(p);
304       to_push = malloc(v + 1);
305       memcpy(to_push, p, v);
306       to_push[v] = '\0';
307       xbt_dynar_push(res, &to_push);
308       done = 1;
309     } else {
310       //get the appearance
311       to_push = malloc(q - p + 1);
312       memcpy(to_push, p, q - p);
313       //add string terminator
314       to_push[q - p] = '\0';
315       xbt_dynar_push(res, &to_push);
316       p = q + strlen(sep);
317     }
318   }
319   return res;
320 }
321
322 /** @brief Splits a string into a dynar of strings, taking quotes into account
323  *
324  * It basically does the same argument separation than the shell, where white
325  * spaces can be escaped and where arguments are never splitted within a
326  * quote group.
327  * Several subsequent spaces are ignored (unless within quotes, of course).
328  *
329  */
330
331 xbt_dynar_t xbt_str_split_quoted(const char *s)
332 {
333   xbt_dynar_t res = xbt_dynar_new(sizeof(char *), xbt_free_ref);
334   char *str_to_free;            /* we have to copy the string before, to handle backslashes */
335   char *beg, *end;              /* pointers around the parsed chunk */
336   int in_simple_quote = 0, in_double_quote = 0;
337   int done = 0;
338   int ctn = 0;                  /* Got something in this block */
339
340   if (s[0] == '\0')
341     return res;
342   beg = str_to_free = xbt_strdup(s);
343
344   /* trim leading spaces */
345   xbt_str_ltrim(beg, " ");
346   end = beg;
347
348   while (!done) {
349
350
351     switch (*end) {
352     case '\\':
353       ctn = 1;
354       /* Protected char; move it closer */
355       memmove(end, end + 1, strlen(end));
356       if (*end == '\0')
357         THROW0(arg_error, 0, "String ends with \\");
358       end++;                    /* Pass the protected char */
359       break;
360
361     case '\'':
362       ctn = 1;
363       if (!in_double_quote) {
364         in_simple_quote = !in_simple_quote;
365         memmove(end, end + 1, strlen(end));
366       } else {
367         /* simple quote protected by double ones */
368         end++;
369       }
370       break;
371     case '"':
372       ctn = 1;
373       if (!in_simple_quote) {
374         in_double_quote = !in_double_quote;
375         memmove(end, end + 1, strlen(end));
376       } else {
377         /* double quote protected by simple ones */
378         end++;
379       }
380       break;
381
382     case ' ':
383     case '\t':
384     case '\n':
385     case '\0':
386       if (*end == '\0' && (in_simple_quote || in_double_quote)) {
387         THROW2(arg_error, 0,
388                "End of string found while searching for %c in %s",
389                (in_simple_quote ? '\'' : '"'), s);
390       }
391       if (in_simple_quote || in_double_quote) {
392         end++;
393       } else {
394         if (ctn) {
395           /* Found a separator. Push the string if contains something */
396           char *topush = xbt_malloc(end - beg + 1);
397           memcpy(topush, beg, end - beg);
398           topush[end - beg] = '\0';
399           xbt_dynar_push(res, &topush);
400         }
401         ctn = 0;
402
403         if (*end == '\0') {
404           done = 1;
405           break;
406         }
407
408         beg = ++end;
409         xbt_str_ltrim(beg, " ");
410         end = beg;
411       }
412       break;
413
414     default:
415       ctn = 1;
416       end++;
417     }
418   }
419   free(str_to_free);
420   return res;
421 }
422
423 #ifdef SIMGRID_TEST
424 #include "xbt/str.h"
425
426 #define mytest(name, input, expected) \
427   xbt_test_add0(name); \
428   d=xbt_str_split_quoted(input); \
429   s=xbt_str_join(d,"XXX"); \
430   xbt_test_assert3(!strcmp(s,expected),\
431                    "Input (%s) leads to (%s) instead of (%s)", \
432                    input,s,expected);\
433                    free(s); \
434                    xbt_dynar_free(&d);
435
436 XBT_TEST_SUITE("xbt_str", "String Handling");
437 XBT_TEST_UNIT("xbt_str_split_quoted", test_split_quoted,
438               "test the function xbt_str_split_quoted")
439 {
440   xbt_dynar_t d;
441   char *s;
442
443   mytest("Empty", "", "");
444   mytest("Basic test", "toto tutu", "totoXXXtutu");
445   mytest("Useless backslashes", "\\t\\o\\t\\o \\t\\u\\t\\u", "totoXXXtutu");
446   mytest("Protected space", "toto\\ tutu", "toto tutu");
447   mytest("Several spaces", "toto   tutu", "totoXXXtutu");
448   mytest("LTriming", "  toto tatu", "totoXXXtatu");
449   mytest("Triming", "  toto   tutu  ", "totoXXXtutu");
450   mytest("Single quotes", "'toto tutu' tata", "toto tutuXXXtata");
451   mytest("Double quotes", "\"toto tutu\" tata", "toto tutuXXXtata");
452   mytest("Mixed quotes", "\"toto' 'tutu\" tata", "toto' 'tutuXXXtata");
453   mytest("Backslashed quotes", "\\'toto tutu\\' tata",
454          "'totoXXXtutu'XXXtata");
455   mytest("Backslashed quotes + quotes", "'toto \\'tutu' tata",
456          "toto 'tutuXXXtata");
457
458 }
459
460 #define mytest_str(name, input, separator, expected) \
461   xbt_test_add0(name); \
462   d=xbt_str_split_str(input, separator); \
463   s=xbt_str_join(d,"XXX"); \
464   xbt_test_assert3(!strcmp(s,expected),\
465                    "Input (%s) leads to (%s) instead of (%s)", \
466                    input,s,expected);\
467                    free(s); \
468                    xbt_dynar_free(&d);
469
470 XBT_TEST_UNIT("xbt_str_split_str", test_split_str,
471               "test the function xbt_str_split_str")
472 {
473   xbt_dynar_t d;
474   char *s;
475
476   mytest_str("Empty string and separator", "", "", "");
477   mytest_str("Empty string", "", "##", "");
478   mytest_str("Empty separator", "toto", "", "toto");
479   mytest_str("String with no separator in it", "toto", "##", "toto");
480   mytest_str("Basic test", "toto##tutu", "##", "totoXXXtutu");
481 }
482 #endif /* SIMGRID_TEST */
483
484 /** @brief Join a set of strings as a single string */
485
486 char *xbt_str_join(xbt_dynar_t dyn, const char *sep)
487 {
488   int len = 1, dyn_len = xbt_dynar_length(dyn);
489   unsigned int cpt;
490   char *cursor;
491   char *res, *p;
492
493   if (!dyn_len)
494     return xbt_strdup("");
495
496   /* compute the length */
497   xbt_dynar_foreach(dyn, cpt, cursor) {
498     len += strlen(cursor);
499   }
500   len += strlen(sep) * dyn_len;
501   /* Do the job */
502   res = xbt_malloc(len);
503   p = res;
504   xbt_dynar_foreach(dyn, cpt, cursor) {
505     if ((int) cpt < dyn_len - 1)
506       p += sprintf(p, "%s%s", cursor, sep);
507     else
508       p += sprintf(p, "%s", cursor);
509   }
510   return res;
511 }
512
513 #if !defined(HAVE_GETLINE) || defined(DOXYGEN)
514 /* prototype here, just in case */
515 long getline(char **buf, size_t * n, FILE * stream);
516
517 /** @brief Get a single line from the stream (reimplementation of the GNU getline)
518  *
519  * This is a redefinition of the GNU getline function, used on platforms where it does not exists.
520  *
521  * getline() reads an entire line from stream, storing the address of the buffer
522  * containing the text into *buf.  The buffer is null-terminated and includes
523  * the newline character, if one was found.
524  *
525  * If *buf is NULL, then getline() will allocate a buffer for storing the line,
526  * which should be freed by the user program.  Alternatively, before calling getline(),
527  * *buf can contain a pointer to a malloc()-allocated buffer *n bytes in size.  If the buffer
528  * is not large enough to hold the line, getline() resizes it with realloc(), updating *buf and *n
529  * as necessary.  In either case, on a successful call, *buf and *n will be updated to
530  * reflect the buffer address and allocated size respectively.
531  */
532 long getline(char **buf, size_t * n, FILE * stream)
533 {
534
535   size_t i;
536   int ch;
537
538   if (!*buf) {
539     *buf = xbt_malloc(512);
540     *n = 512;
541   }
542
543   if (feof(stream))
544     return (ssize_t) - 1;
545
546   for (i = 0; (ch = fgetc(stream)) != EOF; i++) {
547
548     if (i >= (*n) + 1)
549       *buf = xbt_realloc(*buf, *n += 512);
550
551     (*buf)[i] = ch;
552
553     if ((*buf)[i] == '\n') {
554       i++;
555       (*buf)[i] = '\0';
556       break;
557     }
558   }
559
560   if (i == *n)
561     *buf = xbt_realloc(*buf, *n += 1);
562
563   (*buf)[i] = '\0';
564
565   return (ssize_t) i;
566 }
567
568 #endif /* HAVE_GETLINE */
569
570 /*
571  * Diff related functions
572  */
573 static xbt_matrix_t diff_build_LCS(xbt_dynar_t da, xbt_dynar_t db)
574 {
575   xbt_matrix_t C = xbt_matrix_new(xbt_dynar_length(da), xbt_dynar_length(db),
576                                   sizeof(int), NULL);
577   unsigned long i, j;
578
579   /* Compute the LCS */
580   /*
581      C = array(0..m, 0..n)
582      for i := 0..m
583      C[i,0] = 0
584      for j := 1..n
585      C[0,j] = 0
586      for i := 1..m
587      for j := 1..n
588      if X[i] = Y[j]
589      C[i,j] := C[i-1,j-1] + 1
590      else:
591      C[i,j] := max(C[i,j-1], C[i-1,j])
592      return C[m,n]
593    */
594   if (xbt_dynar_length(db) != 0)
595     for (i = 0; i < xbt_dynar_length(da); i++)
596       *((int *) xbt_matrix_get_ptr(C, i, 0)) = 0;
597
598   if (xbt_dynar_length(da) != 0)
599     for (j = 0; j < xbt_dynar_length(db); j++)
600       *((int *) xbt_matrix_get_ptr(C, 0, j)) = 0;
601
602   for (i = 1; i < xbt_dynar_length(da); i++)
603     for (j = 1; j < xbt_dynar_length(db); j++) {
604
605       if (!strcmp
606           (xbt_dynar_get_as(da, i, char *), xbt_dynar_get_as(db, j, char *)))
607          *((int *) xbt_matrix_get_ptr(C, i, j)) =
608           xbt_matrix_get_as(C, i - 1, j - 1, int) + 1;
609       else
610         *((int *) xbt_matrix_get_ptr(C, i, j)) =
611           max(xbt_matrix_get_as(C, i, j - 1, int),
612               xbt_matrix_get_as(C, i - 1, j, int));
613     }
614   return C;
615 }
616
617 static void diff_build_diff(xbt_dynar_t res,
618                             xbt_matrix_t C,
619                             xbt_dynar_t da, xbt_dynar_t db, int i, int j)
620 {
621   char *topush;
622   /* Construct the diff
623      function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
624      if i > 0 and j > 0 and X[i] = Y[j]
625      printDiff(C, X, Y, i-1, j-1)
626      print "  " + X[i]
627      else
628      if j > 0 and (i = 0 or C[i,j-1] >= C[i-1,j])
629      printDiff(C, X, Y, i, j-1)
630      print "+ " + Y[j]
631      else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])
632      printDiff(C, X, Y, i-1, j)
633      print "- " + X[i]
634    */
635
636   if (i >= 0 && j >= 0 && !strcmp(xbt_dynar_get_as(da, i, char *),
637                                   xbt_dynar_get_as(db, j, char *))) {
638     diff_build_diff(res, C, da, db, i - 1, j - 1);
639     topush = bprintf("  %s", xbt_dynar_get_as(da, i, char *));
640     xbt_dynar_push(res, &topush);
641   } else if (j >= 0 &&
642              (i <= 0 || j == 0
643               || xbt_matrix_get_as(C, i, j - 1, int) >= xbt_matrix_get_as(C,
644                                                                           i -
645                                                                           1,
646                                                                           j,
647                                                                           int)))
648   {
649     diff_build_diff(res, C, da, db, i, j - 1);
650     topush = bprintf("+ %s", xbt_dynar_get_as(db, j, char *));
651     xbt_dynar_push(res, &topush);
652   } else if (i >= 0 &&
653              (j <= 0
654               || xbt_matrix_get_as(C, i, j - 1, int) < xbt_matrix_get_as(C,
655                                                                          i -
656                                                                          1, j,
657                                                                          int)))
658   {
659     diff_build_diff(res, C, da, db, i - 1, j);
660     topush = bprintf("- %s", xbt_dynar_get_as(da, i, char *));
661     xbt_dynar_push(res, &topush);
662   } else if (i <= 0 && j <= 0) {
663     return;
664   } else {
665     THROW2(arg_error, 0, "Invalid values: i=%d, j=%d", i, j);
666   }
667
668 }
669
670 /** @brief Compute the unified diff of two strings */
671 char *xbt_str_diff(char *a, char *b)
672 {
673   xbt_dynar_t da = xbt_str_split(a, "\n");
674   xbt_dynar_t db = xbt_str_split(b, "\n");
675
676   xbt_matrix_t C = diff_build_LCS(da, db);
677   xbt_dynar_t diff = xbt_dynar_new(sizeof(char *), xbt_free_ref);
678   char *res = NULL;
679
680   diff_build_diff(diff, C, da, db, xbt_dynar_length(da) - 1,
681                   xbt_dynar_length(db) - 1);
682   /* Clean empty lines at the end */
683   while (xbt_dynar_length(diff) > 0) {
684     char *str;
685     xbt_dynar_pop(diff, &str);
686     if (str[0] == '\0' || !strcmp(str, "  ")) {
687       free(str);
688     } else {
689       xbt_dynar_push(diff, &str);
690       break;
691     }
692   }
693   res = xbt_str_join(diff, "\n");
694
695   xbt_dynar_free(&da);
696   xbt_dynar_free(&db);
697   xbt_dynar_free(&diff);
698   xbt_matrix_free(C);
699
700   return res;
701 }