libanjuta/anjuta-token.c

   1 /* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
   2 /*
   3  * anjuta-token.c
   4  * Copyright (C) Sébastien Granjoux 2009 <seb.sfo@free.fr>
   5  *
   6  * This program is free software: you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License as published by the
   8  * Free Software Foundation, either version 3 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  14  * See the GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License along
  17  * with this program.  If not, see <http://www.gnu.org/licenses/>.
  18  */
  19
  20 #include "anjuta-token.h"
  21
  22 #include "anjuta-debug.h"
  23
  24 #include <glib-object.h>
  25
  26 #include <stdio.h>
  27 #include <string.h>
  28 #include <stdlib.h>
  29
  30 /**
  31  * SECTION:anjuta-token
  32  * @title: Anjuta token
  33  * @short_description: Anjuta token
  34  * @see_also:
  35  * @stability: Unstable
  36  * @include: libanjuta/anjuta-token.h
  37  *
  38  * A #AnjutaToken represents a token. It is a sequence of characters associated
  39  * with a type representing its meaning. By example, a token can represent
  40  * a keyword, a comment, a variable...
  41  *
  42  * The token can own the string or has only a pointer on some data allocated
  43  * somewhere else with a length.
  44  *
  45  * A token is linked with other tokens using three double linked lists.
  46  *
  47  * The first list using next and prev fields is used to keep the token in the
  48  * order where there are in the file. The first character of the first token is
  49  * the first character in the file.
  50  *
  51  * A second list is used to represent included
  52  * files. Such file is represented by a special token in the first list which
  53  * has a pointer, named children to a token list. Each token in this secondary
  54  * list has a pointer to its parent, it means the token representing the file
  55  * where is the token. It looks like a tree. In fact, every file is represented
  56  * by a special token, so the root node is normally a file token and has as
  57  * children all the token representing the file content. This parent/child list
  58  * is used for expanded variable too.
  59  *
  60  * A third list is used to group several tokens. A token can have a pointer to
  61  * another last token. It means that this token is a group starting from this
  62  * token to the one indicated by the last field. In addition each token in this
  63  * group has a pointer on the first token of the group. This grouping is
  64  * independent of the parent/child list. So a group can start in one file and
  65  * end in another included file. The grouping can be nested too. Typically
  66  * we can have a group representing a command, a sub group representing the
  67  * arguments and then one sub group for each argument.
  68  */
  69
  70 /*
  71  * A token with its pointer can be put in one of the following case:
  72  *
  73  * * Simple token:
  74  *              children = NULL && last = NULL
  75  *              This is the case of a simple token without any children.
  76  *
  77  * * Composite token:
  78  *              children = NULL && last != NULL
  79  *              This is the case of a token grouping several other tokens, representing
  80  *              by example an item in a list.
  81  *
  82  * * Parent token:
  83  *              children != NULL && last == NULL
  84  *              This is the case of a token having children, by example a variable where
  85  *              the children represent the content. Most of the time the value of the
  86  *              parent token is ignored.
  87  *
  88  * * Composite parent token:
  89  *              children != NULL && last != NULL && (last in list)
  90  *              This case represents a variable which is split into several tokens. The
  91  *              children represents the content of the variable. The token up to last
  92  *              corresponds to the variable name. After getting the variable content, the
  93  *              next token is after the last token of the variable.
  94  *
  95  * * Composite parent token:
  96  *              children != NULL && last != NULL && (last in children)
  97  *              This case would represent a variable which is split into several token
  98  *              with one inside the children of the variable. This is not possible as
  99  *              the complete name of the variable is needed to get the children.
 100  *
 101  * * Composite parent token:
 102  *              children != NULL && last != NULL && (last in parent)
 103  *              This case represents a variable split into several token where the
 104  *              last element is a sibling of one parent of the token. I think this case
 105  *              is possible.
 106  *
 107  */
 108
 109 typedef struct _AnjutaTokenData AnjutaTokenData;
 110
 111 struct _AnjutaTokenData
 112 {
 113         AnjutaTokenData *data;
 114         AnjutaTokenType type;
 115         gint flags;
 116         gchar *pos;
 117         gsize length;
 118 };
 119
 120 struct _AnjutaToken
 121 {
 122         AnjutaToken     *next;
 123         AnjutaToken     *prev;
 124         AnjutaToken     *parent;
 125         AnjutaToken *last;
 126         AnjutaToken *group;
 127         AnjutaToken     *children;
 128         AnjutaTokenData data;
 129 };
 130
 131 /* Helpers functions
 132  *---------------------------------------------------------------------------*/
 133
 134 /* Private functions
 135  *---------------------------------------------------------------------------*/
 136
 137 static AnjutaToken *
 138 anjuta_token_next_child (AnjutaToken *child, AnjutaToken **last)
 139 {
 140         if (child == NULL) return child;
 141
 142         if (child->children != NULL)
 143         {
 144                 child = child->children;
 145         }
 146         else
 147         {
 148                 for (;;)
 149                 {
 150                         if ((*last == NULL) || (child == *last))
 151                         {
 152                                 if (child->last == NULL)
 153                                 {
 154                                         child = NULL;
 155                                         break;
 156                                 }
 157                                 *last = child->last;
 158                         }
 159                         if (child->next != NULL)
 160                         {
 161                                 child = child->next;
 162                                 break;
 163                         }
 164                         child = child->parent;
 165                 }
 166         }
 167
 168         return child;
 169 }
 170
 171 AnjutaToken *
 172 anjuta_token_next_after_children (AnjutaToken *token)
 173 {
 174         while (token->next == NULL)
 175         {
 176                 token = token->parent;
 177                 if (token == NULL) return NULL;
 178         };
 179
 180         return token->next;
 181 }
 182
 183 static AnjutaToken *
 184 anjuta_token_copy (AnjutaToken *token)
 185 {
 186         AnjutaToken *copy = NULL;
 187
 188         if (token != NULL)
 189         {
 190                 copy = g_slice_new0 (AnjutaToken);
 191                 copy->data.type = token->data.type;
 192                 copy->data.flags = token->data.flags;
 193                 if ((copy->data.flags & ANJUTA_TOKEN_STATIC) || (token->data.pos == NULL))
 194                 {
 195                         copy->data.pos = token->data.pos;
 196                 }
 197                 else
 198                 {
 199                         copy->data.pos = g_strdup (token->data.pos);
 200                 }
 201                 copy->data.length = token->data.length;
 202         }
 203
 204         return copy;
 205 }
 206
 207 /**
 208  * anjuta_token_unlink_token:
 209  * @token: a #AnjutaToken object.
 210  *
 211  * Unlink a single token, not the complete item, from the token tree.
 212  *
 213  * Return value: the removed token tree
 214  */
 215 static AnjutaToken *
 216 anjuta_token_unlink_token (AnjutaToken *token)
 217 {
 218
 219         if (token->prev != NULL)
 220         {
 221                 token->prev->next = token->next;
 222         }
 223         else if ((token->parent != NULL) && (token->parent->children == token))
 224         {
 225                 token->parent->children = token->next;
 226         }
 227         token->parent = NULL;
 228
 229         if ((token->group != NULL) && (token->group->last == token))
 230         {
 231                 AnjutaToken *prev;
 232
 233                 for (prev = token->prev; prev != NULL; prev = prev->prev)
 234                 {
 235                         if (prev->group == token->group)
 236                         {
 237                                 /* Find previous token in the same group */
 238                                 token->group->last = prev;
 239                                 break;
 240                         }
 241                         else if (prev == token->group)
 242                         {
 243                                 /* No more token in group */
 244                                 token->group->last = NULL;
 245                                 break;
 246                         }
 247                 }
 248         }
 249
 250         if (token->next != NULL)
 251         {
 252                 token->next->prev = token->prev;
 253                 token->next = NULL;
 254         }
 255         token->prev = NULL;
 256
 257         return token;
 258 }
 259
 260 /**
 261  * anjuta_token_insert_token_before:
 262  * @sibling: a #AnjutaToken object.
 263  * @token: a #AnjutaToken object.
 264  *
 265  * Insert token before sibling.
 266  *
 267  * Return value: inserted token
 268  */
 269 static AnjutaToken *
 270 anjuta_token_insert_token_before (AnjutaToken *sibling, AnjutaToken *token)
 271 {
 272         token->prev = sibling->prev;
 273         token->next = sibling;
 274
 275         if (token->prev != NULL)
 276         {
 277                 token->prev->next = token;
 278         }
 279         sibling->prev = token;
 280
 281         if ((sibling->parent != NULL) && (sibling->parent->children == sibling))
 282         {
 283                 sibling->parent->children = token;
 284         }
 285         token->parent = sibling->parent;
 286
 287         return token;
 288 }
 289
 290 static void
 291 anjuta_token_evaluate_token (AnjutaToken *token, GString *value, gboolean raw)
 292 {
 293         if ((token != NULL) && (token->data.length != 0))
 294         {
 295                 if (!raw)
 296                 {
 297                         switch (anjuta_token_get_type (token))
 298                         {
 299                         case ANJUTA_TOKEN_COMMENT:
 300                         case ANJUTA_TOKEN_OPEN_QUOTE:
 301                         case ANJUTA_TOKEN_CLOSE_QUOTE:
 302                         case ANJUTA_TOKEN_ESCAPE:
 303                         case ANJUTA_TOKEN_MACRO:
 304                         case ANJUTA_TOKEN_EOV:
 305                                 return;
 306                         default:
 307                                 break;
 308                         }
 309                 }
 310                 g_string_append_len (value, anjuta_token_get_string (token), anjuta_token_get_length (token));
 311         }
 312 }
 313
 314 static void
 315 anjuta_token_show (AnjutaToken *token, gint indent, gchar parent)
 316 {
 317         static gchar type[] = "\0";
 318         const gchar *string;
 319         gsize length;
 320         const gchar *newline;
 321
 322         type[0] = parent;
 323         fprintf (stderr, "%*s%s %p", indent, "", type, token);
 324         fprintf (stderr, ": %d ",
 325             anjuta_token_get_type (token));
 326         string = anjuta_token_get_string (token);
 327         length = anjuta_token_get_length (token);
 328         newline = string == NULL ? NULL : g_strrstr_len (string, length, "\n");
 329         if (newline == NULL)
 330         {
 331                 /* Value doesn't contain a newline */
 332                 fprintf (stderr, "\"%.*s\"",
 333                 length,
 334                 string);
 335         }
 336         else
 337         {
 338                 /* Value contains a newline, take care of indentation */
 339                 newline++;
 340                 fprintf (stderr, "\"%.*s",
 341                 newline - string,
 342                 string);
 343                 for (;;)
 344                 {
 345                         length -= newline - string;
 346                         string = newline;
 347
 348                         newline = g_strrstr_len (string, length, "\n");
 349                         if (newline == NULL) break;
 350
 351                         newline++;
 352                         fprintf (stderr, "%*s  %.*s",
 353                             indent, "",
 354                             newline - string,
 355                         string);
 356                 }
 357                 fprintf (stderr, "%*s  %.*s\"",
 358                             indent, "",
 359                             length,
 360                         string);
 361         }
 362         fprintf (stderr, " %p/%p (%p/%p) %s\n",
 363             token->last, token->children,
 364                 token->group, token->parent,
 365             anjuta_token_get_flags (token) & ANJUTA_TOKEN_REMOVED ? " (removed)" : "");
 366 }
 367
 368 static AnjutaToken*
 369 anjuta_token_dump_child (AnjutaToken *token, gint indent, gchar type)
 370 {
 371         AnjutaToken *last;
 372         AnjutaToken *child;
 373
 374         anjuta_token_show (token, indent, type);
 375         indent += 4;
 376
 377         last = token;
 378         if (token->last != NULL)
 379         {
 380                 do
 381                 {
 382                         child = last->next;
 383                         if (child == NULL) break;
 384                         last = anjuta_token_dump_child (child, indent, '+');
 385                 }
 386                 while (child != token->last);
 387         }
 388
 389         if (token->children != NULL)
 390         {
 391                 for (child = token->children; child != NULL; child = child->next)
 392                 {
 393                         child = anjuta_token_dump_child (child, indent, '*');
 394                 }
 395         }
 396
 397         return last;
 398 }
 399
 400 static gboolean
 401 anjuta_token_check_child (AnjutaToken *token, AnjutaToken *parent)
 402 {
 403         if (token->parent != parent)
 404         {
 405                 anjuta_token_show (token, 0, 0);
 406                 fprintf(stderr, "Error: Children has %p as parent instead of %p\n", token->parent, parent);
 407                 return FALSE;
 408         }
 409
 410         return anjuta_token_check (token);
 411 }
 412
 413 /* Get and set functions
 414  *---------------------------------------------------------------------------*/
 415
 416 void
 417 anjuta_token_set_type (AnjutaToken *token, gint type)
 418 {
 419         token->data.type = type;
 420 }
 421
 422 gint
 423 anjuta_token_get_type (AnjutaToken *token)
 424 {
 425         return token->data.type;
 426 }
 427
 428 void
 429 anjuta_token_set_flags (AnjutaToken *token, gint flags)
 430 {
 431         AnjutaToken *child;
 432         AnjutaToken *last = token->last;
 433
 434         for (child = token; child != NULL; child = anjuta_token_next_child (child, &last))
 435         {
 436                 child->data.flags |= flags;
 437         }
 438 }
 439
 440 void
 441 anjuta_token_clear_flags (AnjutaToken *token, gint flags)
 442 {
 443         token->data.flags &= ~flags;
 444 }
 445
 446 gint
 447 anjuta_token_get_flags (AnjutaToken *token)
 448 {
 449         return token->data.flags;
 450 }
 451
 452 void
 453 anjuta_token_set_string (AnjutaToken *token, const gchar *data, guint length)
 454 {
 455         if (!(token->data.flags & ANJUTA_TOKEN_STATIC))
 456         {
 457                 g_free (token->data.pos);
 458                 token->data.flags |= ANJUTA_TOKEN_STATIC;
 459         }
 460         token->data.pos = (gchar *)data;
 461         token->data.length = length;
 462 }
 463
 464 const gchar *
 465 anjuta_token_get_string (AnjutaToken *token)
 466 {
 467         return token->data.pos;
 468 }
 469
 470 guint
 471 anjuta_token_get_length (AnjutaToken *token)
 472 {
 473         return token->data.length;
 474 }
 475
 476 /* Basic move functions
 477  *---------------------------------------------------------------------------*/
 478
 479 AnjutaToken *
 480 anjuta_token_next (AnjutaToken *token)
 481 {
 482         if (token->children != NULL)
 483         {
 484                 return token->children;
 485         }
 486         else if (token->next != NULL)
 487         {
 488                 return token->next;
 489         }
 490         else if (token->parent != NULL)
 491         {
 492                 return anjuta_token_next_after_children (token->parent);
 493         }
 494         else
 495         {
 496                 return NULL;
 497         }
 498 }
 499
 500 AnjutaToken *
 501 anjuta_token_previous (AnjutaToken *token)
 502 {
 503         if (token->prev != NULL)
 504         {
 505                 return token->prev;
 506         }
 507         else
 508         {
 509                 return token->parent;
 510         }
 511 }
 512
 513 AnjutaToken *
 514 anjuta_token_last (AnjutaToken *token)
 515 {
 516         AnjutaToken *last;
 517
 518         for (last = token; last->last != NULL; last = last->last);
 519         if (last->children != NULL)
 520         {
 521                 for (last = last->children; last->next != NULL; last = last->next);
 522         }
 523
 524         return last;
 525 }
 526
 527 AnjutaToken *
 528 anjuta_token_parent (AnjutaToken *token)
 529 {
 530         return token->parent;
 531 }
 532
 533 AnjutaToken *
 534 anjuta_token_list (AnjutaToken *token)
 535 {
 536         return token->group;
 537 }
 538
 539 /* Item move functions
 540  *---------------------------------------------------------------------------*/
 541
 542 AnjutaToken *
 543 anjuta_token_last_item (AnjutaToken *list)
 544 {
 545         return list->last;
 546 }
 547
 548 AnjutaToken *
 549 anjuta_token_first_item (AnjutaToken *list)
 550 {
 551         AnjutaToken *first = NULL;
 552
 553         if (list != NULL)
 554         {
 555                 if (list->children != NULL)
 556                 {
 557                         first = list->children;
 558                 }
 559                 else if (list->last != NULL)
 560                 {
 561                         first = list->next;
 562                 }
 563         }
 564
 565         return first;
 566 }
 567
 568 AnjutaToken *
 569 anjuta_token_next_item (AnjutaToken *item)
 570 {
 571         AnjutaToken *next;
 572
 573         if (item != NULL)
 574         {
 575                 do
 576                 {
 577                         next = NULL;
 578                         if ((item->group == NULL) || (item->group->last != item))
 579                         {
 580                                 AnjutaToken *last;
 581                                 for (last = item; last->last != NULL; last = last->last);
 582                                 next = anjuta_token_next (last);
 583                                 if ((next != NULL) && (next->group != item->group)) next = NULL;
 584                         }
 585                         item = next;
 586                 }
 587                 /* Loop if the current item has been deleted */
 588                 while ((next != NULL) && (anjuta_token_get_flags (next) & ANJUTA_TOKEN_REMOVED));
 589         }
 590
 591         return next;
 592 }
 593
 594 AnjutaToken *
 595 anjuta_token_previous_item (AnjutaToken *item)
 596 {
 597         AnjutaToken *prev = NULL;
 598
 599
 600         if (item != NULL)
 601         {
 602                 do
 603                 {
 604                         for (prev = item->prev; (prev != NULL) && (prev->group != item->group); prev = prev->group);
 605                         item = prev;
 606                 }
 607                 /* Loop if the current item has been deleted */
 608                 while ((prev != NULL) && (anjuta_token_get_flags (prev) & ANJUTA_TOKEN_REMOVED));
 609         }
 610
 611         return prev;
 612 }
 613
 614 /* Add/Insert/Remove tokens
 615  *---------------------------------------------------------------------------*/
 616
 617 /**
 618  * anjuta_token_append_child:
 619  * @parent: a #AnjutaToken object used as parent.
 620  * @children: a #AnjutaToken object.
 621  *
 622  * Insert all tokens in children as the last children of the given parent.
 623  *
 624  * Return value: The first token append.
 625  */
 626 AnjutaToken *
 627 anjuta_token_append_child (AnjutaToken *parent, AnjutaToken *children)
 628 {
 629         AnjutaToken *token;
 630         AnjutaToken *last;
 631         AnjutaToken *old_group;
 632         AnjutaToken *old_parent;
 633
 634         g_return_val_if_fail (parent != NULL, NULL);
 635         g_return_val_if_fail (children != NULL, NULL);
 636
 637         old_group = children->group;
 638         old_parent = children->parent;
 639
 640         if (parent->children == NULL)
 641         {
 642                 parent->children = children;
 643
 644                 children->prev = NULL;
 645         }
 646         else
 647         {
 648                 /* Find last children */
 649                 for (last = parent->children; last->next != NULL;)
 650                 {
 651                         if ((last->last != NULL) && (last->last->parent == last->parent))
 652                         {
 653                                 last = last->last;
 654                         }
 655                         else
 656                         {
 657                                 last = last->next;
 658                         }
 659                 }
 660
 661                 last->next = children;
 662                 children->prev = last;
 663         }
 664
 665         /* Update each token */
 666         for (token = children;;)
 667         {
 668                 if (token->parent == old_parent) token->parent = parent;
 669                 if (token->group == old_group) token->group = parent->group;
 670
 671                 if (token->children != NULL)
 672                 {
 673                         token = token->children;
 674                 }
 675                 else if (token->next != NULL)
 676                 {
 677                         token = token->next;
 678                 }
 679                 else
 680                 {
 681                         while (token->parent != parent)
 682                         {
 683                                 token = token->parent;
 684                                 if (token->next != NULL) break;
 685                         }
 686                         if (token->next == NULL) break;
 687                         token = token->next;
 688                 }
 689         }
 690
 691         return children;
 692 }
 693
 694 /**
 695  * anjuta_token_prepend_child:
 696  * @parent: a #AnjutaToken object used as parent.
 697  * @children: a #AnjutaToken object.
 698  *
 699  * Insert all tokens in children as the first children of the given parent.
 700  *
 701  * Return value: The first token append.
 702  */
 703 AnjutaToken *
 704 anjuta_token_prepend_child (AnjutaToken *parent, AnjutaToken *children)
 705 {
 706         AnjutaToken *child;
 707         AnjutaToken *last = NULL;
 708
 709         g_return_val_if_fail (parent != NULL, NULL);
 710         g_return_val_if_fail (children != NULL, NULL);
 711
 712         /* Update each token */
 713         for (child = children;;)
 714         {
 715                 AnjutaToken *next;
 716
 717                 if (child->parent == children->parent) child->parent = parent;
 718                 if (child->group == children->group) child->group = parent->group;
 719
 720                 next = anjuta_token_next_child (child, &last);
 721                 if (next == NULL) break;
 722                 child = next;
 723         }
 724
 725         child->next = parent->children;
 726         if (child->next) child->next->prev = child;
 727         parent->children = children;
 728
 729         return children;
 730 }
 731
 732 /**
 733  * anjuta_token_prepend_items:
 734  * @list: a #AnjutaToken object used as list.
 735  * @item: a #AnjutaToken object.
 736  *
 737  * Insert all tokens in item as item of the given list.
 738  *
 739  * Return value: The first token append.
 740  */
 741 AnjutaToken *
 742 anjuta_token_prepend_items (AnjutaToken *list, AnjutaToken *item)
 743 {
 744         AnjutaToken *token;
 745         AnjutaToken *old_group;
 746         AnjutaToken *old_parent;
 747
 748         g_return_val_if_fail (list != NULL, NULL);
 749         g_return_val_if_fail (item != NULL, NULL);
 750
 751         old_group = item->group;
 752         old_parent = item->parent;
 753
 754         /* Update each token */
 755         for (token = item;;)
 756         {
 757                 if (token->parent == old_parent) token->parent = list->parent;
 758                 if (token->group == old_group) token->group = list;
 759
 760                 if (token->children != NULL)
 761                 {
 762                         token = token->children;
 763                 }
 764                 else if (token->next != NULL)
 765                 {
 766                         token = token->next;
 767                 }
 768                 else
 769                 {
 770                         while (token->parent != list->parent)
 771                         {
 772                                 token = token->parent;
 773                                 if (token->next != NULL) break;
 774                         }
 775                         if (token->next == NULL) break;
 776                         token = token->next;
 777                 }
 778         }
 779
 780         token->next = list->next;
 781         if (token->next) token->next->prev = token;
 782
 783         list->next = item;
 784         item->prev = list;
 785
 786         if (list->last == NULL)
 787         {
 788                 while (token->group != list) token = token->group;
 789                 list->last = token;
 790         }
 791
 792         return item;
 793 }
 794
 795 /**
 796  * anjuta_token_insert_after:
 797  * @sibling: a #AnjutaToken object.
 798  * @item: a #AnjutaToken object.
 799  *
 800  * Insert all tokens after sibling.
 801  *
 802  * Return value: The first token inserted.
 803  */
 804 AnjutaToken *
 805 anjuta_token_insert_after (AnjutaToken *sibling, AnjutaToken *list)
 806 {
 807         AnjutaToken *last;
 808         AnjutaToken *token;
 809         AnjutaToken *old_group;
 810         AnjutaToken *old_parent;
 811
 812         g_return_val_if_fail (sibling != NULL, NULL);
 813         g_return_val_if_fail (list != NULL, NULL);
 814
 815         old_group = list->group;
 816         old_parent = list->parent;
 817
 818         /* Update each token */
 819         for (token = list;;)
 820         {
 821                 if (token->parent == old_parent) token->parent = sibling->parent;
 822                 if (token->group == old_group) token->group = sibling->group;
 823
 824                 if (token->children != NULL)
 825                 {
 826                         token = token->children;
 827                 }
 828                 else if (token->next != NULL)
 829                 {
 830                         token = token->next;
 831                 }
 832                 else
 833                 {
 834                         while (token->parent != sibling->parent)
 835                         {
 836                                 token = token->parent;
 837                                 if (token->next != NULL) break;
 838                         }
 839                         if (token->next == NULL) break;
 840                         token = token->next;
 841                 }
 842         }
 843
 844         for (last = sibling; last->last != NULL; last = last->last);
 845
 846         token->next = last->next;
 847         if (token->next) token->next->prev = token;
 848
 849         last->next = list;
 850         list->prev = last;
 851
 852         if ((sibling->group != NULL) && (sibling->group->last == sibling))
 853         {
 854                 while (token->group != sibling->group) token = token->group;
 855                 sibling->group->last = token;
 856         }
 857
 858         return list;
 859 }
 860
 861 /**
 862  * anjuta_token_insert_before:
 863  * @sibling: a #AnjutaToken object.
 864  * @item: a #AnjutaToken object.
 865  *
 866  * Insert all tokens before sibling.
 867  *
 868  * Return value: The first token inserted.
 869  */
 870 AnjutaToken *
 871 anjuta_token_insert_before (AnjutaToken *sibling, AnjutaToken *list)
 872 {
 873         AnjutaToken *last;
 874         AnjutaToken *token;
 875         AnjutaToken *old_group;
 876         AnjutaToken *old_parent;
 877
 878         g_return_val_if_fail (sibling != NULL, NULL);
 879         g_return_val_if_fail (list != NULL, NULL);
 880
 881         old_group = list->group;
 882         old_parent = list->parent;
 883
 884         /* Update each token */
 885         for (token = list;;)
 886         {
 887                 if (token->parent == old_parent) token->parent = sibling->parent;
 888                 if (token->group == old_group) token->group = sibling->group;
 889
 890                 if (token->children != NULL)
 891                 {
 892                         token = token->children;
 893                 }
 894                 else if (token->next != NULL)
 895                 {
 896                         token = token->next;
 897                 }
 898                 else
 899                 {
 900                         while (token->parent != sibling->parent)
 901                         {
 902                                 token = token->parent;
 903                                 if (token->next != NULL) break;
 904                         }
 905                         if (token->next == NULL) break;
 906                         token = token->next;
 907                 }
 908         }
 909
 910         for (last = sibling; last->last != NULL; last = last->last);
 911
 912         token->next = sibling;
 913         list->prev = sibling->prev;
 914         sibling->prev = token;
 915
 916         if (list->prev) list->prev->next = list;
 917
 918         if ((list->parent != NULL) && (list->parent->children == sibling)) list->parent->children = list;
 919
 920         return list;
 921 }
 922
 923 /**
 924  * anjuta_token_delete_parent:
 925  * @parent: a #AnjutaToken object used as parent.
 926  *
 927  * Delete only the parent token.
 928  *
 929  * Return value: the first children
 930  */
 931 AnjutaToken *
 932 anjuta_token_delete_parent (AnjutaToken *parent)
 933 {
 934         AnjutaToken *token;
 935
 936         g_return_val_if_fail (parent != NULL, NULL);
 937
 938         if (parent->children == NULL) return NULL;
 939
 940         /* Update each token */
 941         for (token = parent->children;;)
 942         {
 943                 if (token->parent == parent) token->parent = parent->parent;
 944
 945                 if (token->children != NULL)
 946                 {
 947                         token = token->children;
 948                 }
 949                 else if (token->next != NULL)
 950                 {
 951                         token = token->next;
 952                 }
 953                 else
 954                 {
 955                         while (token->parent != parent->parent)
 956                         {
 957                                 token = token->parent;
 958                                 if (token->next != NULL) break;
 959                         }
 960                         if (token->next == NULL) break;
 961                         token = token->next;
 962                 }
 963         }
 964
 965         token->next = parent->next;
 966         if (token->next) token->next->prev = token;
 967
 968         parent->next = parent->children;
 969         parent->children->prev = parent;
 970         parent->children = NULL;
 971
 972         return anjuta_token_free (parent);
 973 }
 974
 975 /* Merge function
 976  *---------------------------------------------------------------------------*/
 977
 978 AnjutaToken *
 979 anjuta_token_merge (AnjutaToken *first, AnjutaToken *end)
 980 {
 981         if ((first == end) || (end == NULL)) return first;
 982
 983         if (first->parent == NULL)
 984         {
 985                 first->parent = end->parent;
 986         }
 987         if (first->next == NULL)
 988         {
 989                 anjuta_token_insert_before (end, first);
 990         }
 991         first->last = end;
 992         end->group = first;
 993
 994         return first;
 995 }
 996
 997 AnjutaToken *
 998 anjuta_token_merge_own_children (AnjutaToken *group)
 999 {
1000         AnjutaToken *token;
1001         AnjutaToken *next = NULL;
1002
1003         if (group->last != NULL) return group;
1004
1005         if (group->last->last != NULL) group->last = group->last->last;
1006
1007         for (token = anjuta_token_next (group); (token != NULL) && (token != group->last); token = anjuta_token_next (token))
1008         {
1009                 if (next == NULL)
1010                 {
1011                         if (token->last != NULL)
1012                         {
1013                                 next = token->last;
1014                                 //token->last = NULL;
1015                         }
1016                         token->group = group;
1017                 }
1018                 else if (next == token)
1019                 {
1020                         next = NULL;
1021                 }
1022         }
1023
1024         return group;
1025 }
1026
1027 AnjutaToken *
1028 anjuta_token_merge_children (AnjutaToken *first, AnjutaToken *end)
1029 {
1030         if ((first == end) || (end == NULL))
1031         {
1032                 return first;
1033         }
1034
1035         if (first->parent == NULL)
1036         {
1037                 first->parent = end->parent;
1038         }
1039         if (first->next == NULL)
1040         {
1041                 anjuta_token_insert_before (end, first);
1042         }
1043         anjuta_token_unlink_token (end);
1044         if (end->last != NULL)
1045         {
1046                 first->last = end->last;
1047                 end->last->group = first;
1048         }
1049         end->group = first;
1050         anjuta_token_free (end);
1051
1052         return first;
1053 }
1054
1055 /**
1056  * anjuta_token_merge_previous:
1057  * @list: a #AnjutaToken object representing a list
1058  * @first: a #AnjutaToken object for the new beginning of the list
1059  *
1060  * If the list token is not already linked with first, it is inserted
1061  * just before first.
1062  * If the list token is already linked, it must be in the same list after
1063  * first token. It it possible to have several tokens beweent list and
1064  * first.
1065  *
1066  * Return value: the new list
1067  */
1068 AnjutaToken *
1069 anjuta_token_merge_previous (AnjutaToken *list, AnjutaToken *first)
1070 {
1071         AnjutaToken *token;
1072
1073         if ((first == NULL) || (list == first)) return list;
1074
1075         /* Change group of all tokens from end to first
1076          * if the list is already linked */
1077         if ((list->prev != NULL) || (list->parent != NULL))
1078         {
1079                 for (token = first; token != NULL; token = anjuta_token_next_item (token))
1080                 {
1081                         token->group = list;
1082                 }
1083         }
1084
1085         token = anjuta_token_next (list);
1086         anjuta_token_unlink_token (list);
1087         anjuta_token_insert_token_before (first, list);
1088
1089         return list;
1090 }
1091
1092 AnjutaToken *anjuta_token_split (AnjutaToken *token, guint size)
1093 {
1094         if (token->data.length > size)
1095         {
1096                 AnjutaToken *copy;
1097
1098                 copy = anjuta_token_copy (token);
1099                 anjuta_token_insert_before (token, copy);
1100
1101                 copy->data.length = size;
1102                 if (token->data.flags & ANJUTA_TOKEN_STATIC)
1103                 {
1104                         token->data.pos += size;
1105                         token->data.length -= size;
1106                 }
1107                 else
1108                 {
1109                         memcpy(token->data.pos, token->data.pos + size, token->data.length - size);
1110                 }
1111
1112                 return copy;
1113         }
1114         else
1115         {
1116                 return token;
1117         }
1118 }
1119
1120 AnjutaToken *anjuta_token_cut (AnjutaToken *token, guint pos, guint size)
1121 {
1122         AnjutaToken *copy;
1123
1124         copy = anjuta_token_copy (token);
1125
1126         if (pos >= token->data.length)
1127         {
1128                 if (!(copy->data.flags & ANJUTA_TOKEN_STATIC))
1129                 {
1130                         g_free (copy->data.pos);
1131                 }
1132                 copy->data.pos = NULL;
1133                 copy->data.length = 0;
1134         }
1135         if ((pos + size) > token->data.length)
1136         {
1137                 size = token->data.length - pos;
1138         }
1139
1140         if (copy->data.flags & ANJUTA_TOKEN_STATIC)
1141         {
1142                 copy->data.pos += pos;
1143         }
1144         else
1145         {
1146                 memcpy(copy->data.pos, copy->data.pos + pos, size);
1147         }
1148         copy->data.length = size;
1149
1150         return copy;
1151 }
1152
1153 /* Token foreach
1154  *---------------------------------------------------------------------------*/
1155
1156 void
1157 anjuta_token_foreach_content (AnjutaToken *token, AnjutaTokenForeachFunc func, gpointer user_data)
1158 {
1159         if (token != NULL)
1160         {
1161                 AnjutaToken *last_parent;       /* If not NULL, token belong to a parent and
1162                                                                          * are not taken into account */
1163                 AnjutaToken *last_token;
1164                 gboolean expand = TRUE;
1165
1166                 last_parent = NULL;
1167                 last_token = token->last == NULL ? token : token->last;
1168                 while (token != NULL)
1169                 {
1170                         if (expand && (token->children != NULL))
1171                         {
1172                                 /* Check if we have found the last token */
1173                                 if (token == last_token)
1174                                 {
1175                                         /* Find last token */
1176                                         if (token->last == NULL)
1177                                         {
1178                                                 break;
1179                                         }
1180                                         /* Last token still include additional tokens */
1181                                         last_token = token->last;
1182                                 }
1183
1184                                 /* Enumerate children */
1185                                 token = token->children;
1186                         }
1187                         else
1188                         {
1189                                 if (token->children == NULL)
1190                                 {
1191                                         /* Take into account only the content of token having no children */
1192                                         if (last_parent == NULL)
1193                                         {
1194                                                 /* Take into account only the content of group having no children */
1195                                                 func (token, user_data);
1196                                         }
1197                                 }
1198
1199                                 /* Check if we have found the last token */
1200                                 if (token == last_token)
1201                                 {
1202                                         /* Find last token */
1203                                         if (token->last == NULL)
1204                                         {
1205                                                 break;
1206                                         }
1207                                         /* Last token still include additional tokens */
1208                                         last_token = token->last;
1209                                 }
1210
1211                                 if (token == last_parent)
1212                                 {
1213                                         /* Find last parent */
1214                                         if (token->last == NULL)
1215                                         {
1216                                                 /* Found complete group having children */
1217                                                 last_parent = NULL;
1218                                         }
1219                                         else
1220                                         {
1221                                                 /* Parent group has additional token */
1222                                                 last_parent = token->last;
1223                                         }
1224                                 }
1225
1226                                 if (token->next != NULL)
1227                                 {
1228                                         /* Get next sibling */
1229                                         token = token->next;
1230                                         expand = TRUE;
1231                                 }
1232                                 else
1233                                 {
1234                                         /* Get parent */
1235                                         token = token->parent;
1236                                         if (token != NULL) last_parent = token->last;
1237                                         expand = FALSE;
1238                                 }
1239                         }
1240                 }
1241         }
1242
1243         return;
1244 }
1245
1246 AnjutaToken *
1247 anjuta_token_foreach_post_order (AnjutaToken *token, AnjutaTokenForeachFunc func, gpointer user_data)
1248 {
1249         if (token != NULL)
1250         {
1251                 AnjutaToken *last_parent;       /* If not NULL, token belong to a parent */
1252                 AnjutaToken *last_token;
1253                 AnjutaToken buffer;                     /* Temporary token allowing func to destroy
1254                                                                          * the current token */
1255                 gboolean expand = TRUE;
1256
1257                 last_parent = NULL;
1258                 last_token = token->last == NULL ? token : token->last;
1259                 while (token != NULL)
1260                 {
1261                         if (expand && (token->children != NULL))
1262                         {
1263                                 /* Check if we have found the last token */
1264                                 if (token == last_token)
1265                                 {
1266                                         /* Find last token */
1267                                         if (token->last == NULL)
1268                                         {
1269                                                 break;
1270                                         }
1271                                         /* Last token still include additional tokens */
1272                                         last_token = token->last;
1273                                 }
1274
1275                                 /* Enumerate children */
1276                                 token = token->children;
1277                         }
1278                         else
1279                         {
1280                                 /* Save token data in case it is destroyed */
1281                                 memcpy (&buffer, token, sizeof (buffer));
1282                                 /* Take into account all token */
1283                                 func (token, user_data);
1284
1285                                 /* Check if we have found the last token */
1286                                 if (token == last_token)
1287                                 {
1288                                         /* Find last token */
1289                                         if (buffer.last == NULL)
1290                                         {
1291                                                 token = &buffer;
1292                                                 break;
1293                                         }
1294                                         /* Last token still include additional tokens */
1295                                         last_token = buffer.last;
1296                                 }
1297
1298                                 if (token == last_parent)
1299                                 {
1300                                         /* Find last parent */
1301                                         if (buffer.last == NULL)
1302                                         {
1303                                                 /* Found complete group having children */
1304                                                 last_parent = NULL;
1305                                         }
1306                                         else
1307                                         {
1308                                                 /* Parent group has additional token */
1309                                                 last_parent = buffer.last;
1310                                         }
1311                                 }
1312
1313                                 if (buffer.next != NULL)
1314                                 {
1315                                         /* Get next sibling */
1316                                         token = buffer.next;
1317                                         expand = TRUE;
1318                                 }
1319                                 else
1320                                 {
1321                                         /* Get parent */
1322                                         token = buffer.parent;
1323                                         if (token != NULL) last_parent = token->last;
1324                                         expand = FALSE;
1325                                 }
1326                         }
1327                 }
1328
1329                 while ((token != NULL) && (token->next == NULL))
1330                 {
1331                         token = token->parent;
1332                 };
1333
1334                 if (token != NULL) token = token->next;
1335         }
1336
1337         return token;
1338 }
1339
1340 /* Token evaluation
1341  *---------------------------------------------------------------------------*/
1342
1343 static void
1344 evaluate_raw_token (AnjutaToken *token, gpointer user_data)
1345 {
1346         GString *value = (GString *)user_data;
1347
1348         anjuta_token_evaluate_token (token, value, TRUE);
1349 }
1350
1351 static void
1352 evaluate_token (AnjutaToken *token, gpointer user_data)
1353 {
1354         GString *value = (GString *)user_data;
1355
1356         anjuta_token_evaluate_token (token, value, FALSE);
1357 }
1358
1359
1360 gchar *
1361 anjuta_token_evaluate (AnjutaToken *token)
1362 {
1363         GString *value = g_string_new (NULL);
1364
1365         anjuta_token_foreach_content (token, evaluate_token, value);
1366
1367         /* Return NULL and free data for an empty string */
1368         return g_string_free (value, *(value->str) == '\0');
1369 }
1370
1371 gboolean
1372 anjuta_token_is_empty (AnjutaToken *token)
1373 {
1374         return (token == NULL) || ((token->data.length == 0) && (token->last == NULL) && (token->children == NULL));
1375 }
1376
1377
1378 /* Other functions
1379  *---------------------------------------------------------------------------*/
1380
1381 gboolean
1382 anjuta_token_compare (AnjutaToken *toka, AnjutaToken *tokb)
1383 {
1384         if (tokb->data.type)
1385         {
1386                 if (tokb->data.type != toka->data.type) return FALSE;
1387         }
1388
1389         if (tokb->data.type != ANJUTA_TOKEN_NONE)
1390         {
1391                 if (tokb->data.length != 0)
1392                 {
1393                         if (toka->data.length != tokb->data.length) return FALSE;
1394
1395                         if ((toka->data.flags & ANJUTA_TOKEN_CASE_INSENSITIVE)  && (tokb->data.flags & ANJUTA_TOKEN_CASE_INSENSITIVE))
1396                         {
1397                                 if (g_ascii_strncasecmp (toka->data.pos, tokb->data.pos, toka->data.length) != 0) return FALSE;
1398                         }
1399                         else
1400                         {
1401                                 if (strncmp (toka->data.pos, tokb->data.pos, toka->data.length) != 0) return FALSE;
1402                         }
1403                 }
1404         }
1405
1406         if (tokb->data.flags & ANJUTA_TOKEN_PUBLIC_FLAGS)
1407         {
1408                 if ((toka->data.flags & tokb->data.flags & ANJUTA_TOKEN_PUBLIC_FLAGS) == 0)
1409                         return FALSE;
1410         }
1411
1412         return TRUE;
1413 }
1414
1415 void
1416 anjuta_token_dump (AnjutaToken *token)
1417 {
1418         if (token == NULL) return;
1419
1420         anjuta_token_dump_child (token, 0, 0);
1421 }
1422
1423 void
1424 anjuta_token_dump_link (AnjutaToken *token)
1425 {
1426         AnjutaToken *last = token;
1427
1428         while (last->last != NULL) last = last->last;
1429
1430         for (; token != last; token = anjuta_token_next (token))
1431         {
1432                 anjuta_token_show (token, 0, 0);
1433         }
1434 }
1435
1436 gboolean
1437 anjuta_token_check (AnjutaToken *token)
1438 {
1439         if ((token->children != NULL) && (token->last != NULL))
1440         {
1441                 anjuta_token_show (token, 0, 0);
1442                 fprintf(stderr, "Error: Previous token has both non NULL children and last\n");
1443
1444                 return FALSE;
1445         }
1446
1447         if (token->children != NULL)
1448         {
1449                 AnjutaToken *child;
1450
1451                 for (child = token->children; child != NULL; child = child->next)
1452                 {
1453                         if (!anjuta_token_check_child (child, token)) return FALSE;
1454                 }
1455         }
1456
1457         if (token->last != NULL)
1458         {
1459                 AnjutaToken *child;
1460
1461                 for (child = anjuta_token_next (token); child != NULL; child = anjuta_token_next (child))
1462                 {
1463                         if (!anjuta_token_check (child)) return FALSE;
1464                         if (child == token->last) break;
1465                 }
1466         }
1467
1468         return TRUE;
1469 }
1470
1471 /* Constructor & Destructor
1472  *---------------------------------------------------------------------------*/
1473
1474 AnjutaToken *anjuta_token_new_string (AnjutaTokenType type, const gchar *value)
1475 {
1476         AnjutaToken *token;
1477
1478         if (value == NULL)
1479         {
1480                 token = anjuta_token_new_static (type, NULL);
1481         }
1482         else
1483         {
1484                 token = g_slice_new0 (AnjutaToken);
1485                 token->data.type = type  & ANJUTA_TOKEN_TYPE;
1486                 token->data.flags = type & ANJUTA_TOKEN_FLAGS;
1487                 token->data.pos = g_strdup (value);
1488                 token->data.length = strlen (value);
1489         }
1490
1491         return token;
1492 }
1493
1494 AnjutaToken*
1495 anjuta_token_new_with_string (AnjutaTokenType type, gchar *value, gsize length)
1496 {
1497         AnjutaToken *token;
1498
1499         if (value == NULL)
1500         {
1501                 token = anjuta_token_new_static (type, NULL);
1502         }
1503         else
1504         {
1505                 token = g_slice_new0 (AnjutaToken);
1506                 token->data.type = type  & ANJUTA_TOKEN_TYPE;
1507                 token->data.flags = type & ANJUTA_TOKEN_FLAGS;
1508                 token->data.pos = value;
1509                 token->data.length = length;
1510         }
1511
1512         return token;
1513 }
1514
1515 AnjutaToken *
1516 anjuta_token_new_fragment (gint type, const gchar *pos, gsize length)
1517 {
1518         AnjutaToken *token;
1519
1520         token = g_slice_new0 (AnjutaToken);
1521         token->data.type = type  & ANJUTA_TOKEN_TYPE;
1522         token->data.flags = (type & ANJUTA_TOKEN_FLAGS) | ANJUTA_TOKEN_STATIC;
1523         token->data.pos = (gchar *)pos;
1524         token->data.length = length;
1525
1526         return token;
1527 };
1528
1529 AnjutaToken *anjuta_token_new_static (AnjutaTokenType type, const char *value)
1530 {
1531         return anjuta_token_new_fragment (type, value, value == NULL ? 0 : strlen (value));
1532 }
1533
1534 AnjutaToken*
1535 anjuta_token_free_children (AnjutaToken *token)
1536 {
1537         AnjutaToken *child;
1538         AnjutaToken *last;
1539
1540         if (token == NULL) return NULL;
1541
1542         for (child = token->children; child != NULL; child = token->children)
1543         {
1544                 anjuta_token_free (child);
1545         }
1546         token->children = NULL;
1547
1548         if (token->last != NULL)
1549         {
1550                 last = token->last;
1551                 for (child = anjuta_token_next (token); child != NULL; child = anjuta_token_next (token))
1552                 {
1553                         anjuta_token_free (child);
1554                         if (child == last) break;
1555                 }
1556         }
1557         token->last = NULL;
1558
1559         return token;
1560 }
1561
1562 static void
1563 free_token (AnjutaToken *token, gpointer user_data)
1564 {
1565         anjuta_token_unlink_token (token);
1566         if ((token->data.pos != NULL) && !(token->data.flags & ANJUTA_TOKEN_STATIC))
1567         {
1568                 g_free (token->data.pos);
1569         }
1570         g_slice_free (AnjutaToken, token);
1571 }
1572
1573
1574 AnjutaToken*
1575 anjuta_token_free (AnjutaToken *token)
1576 {
1577         AnjutaToken *next;
1578
1579         if (token == NULL) return NULL;
1580
1581         next = anjuta_token_foreach_post_order (token, free_token, NULL);
1582
1583         return next;
1584 }