ctags/libreadtags/readtags.c

   1 /*
   2 *   Copyright (c) 1996-2003, Darren Hiebert
   3 *
   4 *   This source code is released into the public domain.
   5 *
   6 *   This module contains functions for reading tag files.
   7 */
   8
   9 /*
  10 *   INCLUDE FILES
  11 */
  12 #include <stdlib.h>
  13 #include <string.h>
  14 #include <ctype.h>
  15 #include <stdio.h>
  16 #include <errno.h>
  17 #include <sys/types.h>  /* to declare off_t */
  18
  19 #include "readtags.h"
  20
  21 /*
  22 *   MACROS
  23 */
  24 #define TAB '\t'
  25
  26
  27 /*
  28 *   DATA DECLARATIONS
  29 */
  30 typedef struct {
  31         size_t size;
  32         char *buffer;
  33 } vstring;
  34
  35 /* Information about current tag file */
  36 struct sTagFile {
  37                 /* has the file been opened and this structure initialized? */
  38         short initialized;
  39                 /* format of tag file */
  40         short format;
  41                 /* how is the tag file sorted? */
  42         tagSortType sortMethod;
  43                 /* pointer to file structure */
  44         FILE* fp;
  45                 /* file position of first character of `line' */
  46         off_t pos;
  47                 /* size of tag file in seekable positions */
  48         off_t size;
  49                 /* last line read */
  50         vstring line;
  51                 /* name of tag in last line read */
  52         vstring name;
  53                 /* defines tag search state */
  54         struct {
  55                                 /* file position of last match for tag */
  56                         off_t pos;
  57                                 /* name of tag last searched for */
  58                         char *name;
  59                                 /* length of name for partial matches */
  60                         size_t nameLength;
  61                                 /* performing partial match */
  62                         short partial;
  63                                 /* ignoring case */
  64                         short ignorecase;
  65         } search;
  66                 /* miscellaneous extension fields */
  67         struct {
  68                                 /* number of entries in `list' */
  69                         unsigned short max;
  70                                 /* list of key value pairs */
  71                         tagExtensionField *list;
  72         } fields;
  73                 /* buffers to be freed at close */
  74         struct {
  75                         /* name of program author */
  76                 char *author;
  77                         /* name of program */
  78                 char *name;
  79                         /* URL of distribution */
  80                 char *url;
  81                         /* program version */
  82                 char *version;
  83         } program;
  84                 /* 0 (initial state set by calloc), errno value,
  85                  * or tagErrno typed value */
  86         int err;
  87 };
  88
  89 /*
  90 *   DATA DEFINITIONS
  91 */
  92 static const char *const EmptyString = "";
  93 static const char *const PseudoTagPrefix = "!_";
  94 static const size_t PseudoTagPrefixLength = 2;
  95
  96 /*
  97 *   FUNCTION DEFINITIONS
  98 */
  99
 100 /* Converts a hexadecimal digit to its value */
 101 static int xdigitValue (char digit)
 102 {
 103         if (digit >= '0' && digit <= '9')
 104                 return digit - '0';
 105         else if (digit >= 'a' && digit <= 'f')
 106                 return 10 + digit - 'a';
 107         else if (digit >= 'A' && digit <= 'F')
 108                 return 10 + digit - 'A';
 109         else
 110                 return 0;
 111 }
 112
 113 /*
 114  * Reads the first character from the string, possibly un-escaping it, and
 115  * advances *s to the start of the next character.
 116  */
 117 static int readTagCharacter (const char **s)
 118 {
 119         int c = **(const unsigned char **)s;
 120
 121         (*s)++;
 122
 123         if (c == '\\')
 124         {
 125                 switch (**s)
 126                 {
 127                         case 't': c = '\t'; (*s)++; break;
 128                         case 'r': c = '\r'; (*s)++; break;
 129                         case 'n': c = '\n'; (*s)++; break;
 130                         case '\\': c = '\\'; (*s)++; break;
 131                         /* Universal-CTags extensions */
 132                         case 'a': c = '\a'; (*s)++; break;
 133                         case 'b': c = '\b'; (*s)++; break;
 134                         case 'v': c = '\v'; (*s)++; break;
 135                         case 'f': c = '\f'; (*s)++; break;
 136                         case 'x':
 137                                 if (isxdigit ((*s)[1]) && isxdigit ((*s)[2]))
 138                                 {
 139                                         int val = (xdigitValue ((*s)[1]) << 4) | xdigitValue ((*s)[2]);
 140                                         if (val < 0x80)
 141                                         {
 142                                                 (*s) += 3;
 143                                                 c = val;
 144                                         }
 145                                 }
 146                                 break;
 147                 }
 148         }
 149
 150         return c;
 151 }
 152
 153 /*
 154  * Compare two strings, ignoring case.
 155  * Return 0 for match, < 0 for smaller, > 0 for bigger
 156  * Make sure case is folded to uppercase in comparison (like for 'sort -f')
 157  * This makes a difference when one of the chars lies between upper and lower
 158  * ie. one of the chars [ \ ] ^ _ ` for ascii. (The '_' in particular !)
 159  */
 160 static int taguppercmp (const char *s1, const char *s2)
 161 {
 162         int result;
 163         int c1, c2;
 164         do
 165         {
 166                 c1 = (unsigned char)*s1++;
 167                 c2 = readTagCharacter (&s2);
 168
 169                 result = toupper (c1) - toupper (c2);
 170         } while (result == 0  &&  c1 != '\0'  &&  c2 != '\0');
 171         return result;
 172 }
 173
 174 static int tagnuppercmp (const char *s1, const char *s2, size_t n)
 175 {
 176         int result;
 177         int c1, c2;
 178         do
 179         {
 180                 c1 = (unsigned char)*s1++;
 181                 c2 = readTagCharacter (&s2);
 182
 183                 result = toupper (c1) - toupper (c2);
 184         } while (result == 0  &&  --n > 0  &&  c1 != '\0'  &&  c2 != '\0');
 185         return result;
 186 }
 187
 188 static int tagcmp (const char *s1, const char *s2)
 189 {
 190         int result;
 191         int c1, c2;
 192         do
 193         {
 194                 c1 = (unsigned char)*s1++;
 195                 c2 = readTagCharacter (&s2);
 196
 197                 result = c1 - c2;
 198         } while (result == 0  &&  c1 != '\0'  &&  c2 != '\0');
 199         return result;
 200 }
 201
 202 static int tagncmp (const char *s1, const char *s2, size_t n)
 203 {
 204         int result;
 205         int c1, c2;
 206         do
 207         {
 208                 c1 = *s1++;
 209                 c2 = readTagCharacter (&s2);
 210
 211                 result = c1 - c2;
 212         } while (result == 0  &&  --n > 0  &&  c1 != '\0'  &&  c2 != '\0');
 213         return result;
 214 }
 215
 216 static tagResult growString (vstring *s)
 217 {
 218         tagResult result = TagFailure;
 219         size_t newLength;
 220         char *newLine;
 221         if (s->size == 0)
 222         {
 223                 newLength = 128;
 224                 newLine = (char*) malloc (newLength);
 225                 if (newLine)
 226                         *newLine = '\0';
 227         }
 228         else
 229         {
 230                 newLength = 2 * s->size;
 231                 newLine = (char*) realloc (s->buffer, newLength);
 232         }
 233         if (newLine == NULL)
 234                 perror ("string too large");
 235         else
 236         {
 237                 s->buffer = newLine;
 238                 s->size = newLength;
 239                 result = TagSuccess;
 240         }
 241         return result;
 242 }
 243
 244 /* Copy name of tag out of tag line */
 245 static tagResult copyName (tagFile *const file)
 246 {
 247         size_t length;
 248         const char *end = strchr (file->line.buffer, '\t');
 249         if (end == NULL)
 250         {
 251                 end = strchr (file->line.buffer, '\n');
 252                 if (end == NULL)
 253                         end = strchr (file->line.buffer, '\r');
 254         }
 255         if (end != NULL)
 256                 length = end - file->line.buffer;
 257         else
 258                 length = strlen (file->line.buffer);
 259         while (length >= file->name.size)
 260         {
 261                 if (growString (&file->name) != TagSuccess)
 262                         return TagFailure;
 263         }
 264         strncpy (file->name.buffer, file->line.buffer, length);
 265         file->name.buffer [length] = '\0';
 266         return TagSuccess;
 267 }
 268
 269 /* Return 1 on success.
 270  * Return 0 on failure or EOF.
 271  * errno is set to *err unless EOF.
 272  */
 273 static int readTagLineRaw (tagFile *const file, int *err)
 274 {
 275         int result = 1;
 276         int reReadLine;
 277
 278         /*  If reading the line places any character other than a null or a
 279          *  newline at the last character position in the buffer (one less than
 280          *  the buffer size), then we must resize the buffer and reattempt to read
 281          *  the line.
 282          */
 283         do
 284         {
 285                 char *const pLastChar = file->line.buffer + file->line.size - 2;
 286                 char *line;
 287
 288                 file->pos = ftell (file->fp);
 289                 if (file->pos < 0)
 290                 {
 291                         *err = errno;
 292                         result = 0;
 293                         break;
 294                 }
 295                 reReadLine = 0;
 296                 *pLastChar = '\0';
 297                 line = fgets (file->line.buffer, (int) file->line.size, file->fp);
 298                 if (line == NULL)
 299                 {
 300                         /* read error */
 301                         *err = 0;
 302                         if (! feof (file->fp))
 303                                 *err = errno;
 304                         result = 0;
 305                 }
 306                 else if (*pLastChar != '\0'  &&
 307                                         *pLastChar != '\n'  &&  *pLastChar != '\r')
 308                 {
 309                         /*  buffer overflow */
 310                         if (growString (&file->line) != TagSuccess)
 311                         {
 312                                 *err = ENOMEM;
 313                                 result = 0;
 314                         }
 315                         if (fseek (file->fp, file->pos, SEEK_SET) < 0)
 316                         {
 317                                 *err = errno;
 318                                 result = 0;
 319                         }
 320                         reReadLine = 1;
 321                 }
 322                 else
 323                 {
 324                         size_t i = strlen (file->line.buffer);
 325                         while (i > 0  &&
 326                                    (file->line.buffer [i - 1] == '\n' || file->line.buffer [i - 1] == '\r'))
 327                         {
 328                                 file->line.buffer [i - 1] = '\0';
 329                                 --i;
 330                         }
 331                 }
 332         } while (reReadLine  &&  result);
 333         if (result)
 334         {
 335                 if (copyName (file) != TagSuccess)
 336                 {
 337                         *err = ENOMEM;
 338                         result = 0;
 339                 }
 340         }
 341         return result;
 342 }
 343
 344 /* Return 1 on success.
 345  * Return 0 on failure or EOF.
 346  * errno is set to *err unless EOF.
 347  */
 348 static int readTagLine (tagFile *const file, int *err)
 349 {
 350         int result;
 351         do
 352         {
 353                 result = readTagLineRaw (file, err);
 354         } while (result && *file->name.buffer == '\0');
 355         return result;
 356 }
 357
 358 static tagResult growFields (tagFile *const file)
 359 {
 360         tagResult result = TagFailure;
 361         unsigned short newCount = (unsigned short) 2 * file->fields.max;
 362         tagExtensionField *newFields = (tagExtensionField*)
 363                         realloc (file->fields.list, newCount * sizeof (tagExtensionField));
 364         if (newFields == NULL)
 365                 perror ("too many extension fields");
 366         else
 367         {
 368                 file->fields.list = newFields;
 369                 file->fields.max = newCount;
 370                 result = TagSuccess;
 371         }
 372         return result;
 373 }
 374
 375 static tagResult parseExtensionFields (tagFile *const file, tagEntry *const entry,
 376                                                                            char *const string, int *err)
 377 {
 378         char *p = string;
 379         char *tail = string + (string? strlen(string):0);
 380         size_t q_len;
 381
 382         while (p != NULL  &&  *p != '\0')
 383         {
 384                 while (*p == TAB)
 385                         *p++ = '\0';
 386                 if (*p != '\0')
 387                 {
 388                         char *colon;
 389                         char *field = p;
 390                         p = strchr (p, TAB);
 391                         if (p != NULL)
 392                                 *p++ = '\0';
 393                         colon = strchr (field, ':');
 394                         if (colon == NULL)
 395                                 entry->kind = field;
 396                         else
 397                         {
 398                                 const char *key = field;
 399                                 char *q = colon + 1;
 400                                 const char *value = q;
 401                                 const int key_len = colon - key;
 402                                 *colon = '\0';
 403
 404                                 q_len = tail - q;
 405
 406                                 /* Unescaping */
 407                                 while (*q != '\0')
 408                                 {
 409                                         const char *next = q;
 410                                         int ch = readTagCharacter (&next);
 411                                         size_t skip = next - q;
 412
 413                                         *q = (char) ch;
 414                                         q++;
 415                                         q_len -= skip;
 416                                         if (skip > 1)
 417                                         {
 418                                                 /* + 1 is for moving the area including the last '\0'. */
 419                                                 memmove (q, next, q_len + 1);
 420                                                 if (p)
 421                                                         p -= skip - 1;
 422                                                 if (tail != string)
 423                                                         tail -= skip - 1;
 424                                         }
 425                                 }
 426
 427                                 if (key_len == 4)
 428                                 {
 429                                         if (memcmp (key, "kind", 4) == 0)
 430                                                 entry->kind = value;
 431                                         else if (memcmp (key, "file", 4) == 0)
 432                                                 entry->fileScope = 1;
 433                                         else if (memcmp (key, "line", 4) == 0)
 434                                         {
 435                                                 char *endptr = NULL;
 436                                                 long m = strtol (value, &endptr, 10);
 437                                                 if (*endptr != '\0' || m < 0)
 438                                                 {
 439                                                         *err = TagErrnoUnexpectedLineno;
 440                                                         return TagFailure;
 441                                                 }
 442                                                 entry->address.lineNumber = m;
 443                                         }
 444                                         else
 445                                                 goto normalField;
 446                                 }
 447                                 else
 448                                 {
 449                                 normalField:
 450                                         if (entry->fields.count == file->fields.max)
 451                                         {
 452                                                 if (growFields (file) != TagSuccess)
 453                                                 {
 454                                                         *err = ENOMEM;
 455                                                         return TagFailure;
 456                                                 }
 457                                         }
 458                                         file->fields.list [entry->fields.count].key = key;
 459                                         file->fields.list [entry->fields.count].value = value;
 460                                         ++entry->fields.count;
 461                                 }
 462                         }
 463                 }
 464         }
 465         return TagSuccess;
 466 }
 467
 468 static int isOdd (unsigned int i)
 469 {
 470         return  (i % 2);
 471 }
 472
 473 static unsigned int countContinuousBackslashesBackward(const char *from,
 474                                                      const char *till)
 475 {
 476         unsigned int counter = 0;
 477
 478         for (; from > till; from--)
 479         {
 480                 if (*from == '\\')
 481                         counter++;
 482                 else
 483                         break;
 484         }
 485         return counter;
 486 }
 487
 488 static tagResult parseTagLine (tagFile *file, tagEntry *const entry, int *err)
 489 {
 490         int i;
 491         char *p = file->line.buffer;
 492         size_t p_len = strlen (p);
 493         char *tab = strchr (p, TAB);
 494
 495         memset(entry, 0, sizeof(*entry));
 496
 497         entry->name = p;
 498         if (tab != NULL)
 499         {
 500                 *tab = '\0';
 501         }
 502
 503         /* When unescaping, the input string becomes shorter.
 504          * e.g. \t occupies two bytes on the tag file.
 505          * It is converted to 0x9 and occupies one byte.
 506          * memmove called here for shortening the line
 507          * buffer. */
 508         while (*p != '\0')
 509         {
 510                 const char *next = p;
 511                 int ch = readTagCharacter (&next);
 512                 size_t skip = next - p;
 513
 514                 *p = (char) ch;
 515                 p++;
 516                 p_len -= skip;
 517                 if (skip > 1)
 518                 {
 519                         /* + 1 is for moving the area including the last '\0'. */
 520                         memmove (p, next, p_len + 1);
 521                         if (tab)
 522                                 tab -= skip - 1;
 523                 }
 524         }
 525
 526         if (tab != NULL)
 527         {
 528                 p = tab + 1;
 529                 entry->file = p;
 530                 tab = strchr (p, TAB);
 531                 if (tab != NULL)
 532                 {
 533                         int fieldsPresent;
 534                         int combinedPattern;
 535                         *tab = '\0';
 536                         p = tab + 1;
 537                         if (*p == '/'  ||  *p == '?')
 538                         {
 539                                 /* parse pattern */
 540                                 int delimiter = *(unsigned char*) p;
 541                                 entry->address.lineNumber = 0;
 542                                 entry->address.pattern = p;
 543                                 do
 544                                 {
 545                                         p = strchr (p + 1, delimiter);
 546                                 } while (p != NULL
 547                                          &&  isOdd (countContinuousBackslashesBackward (p - 1,
 548                                                                                         entry->address.pattern)));
 549
 550                                 if (p == NULL)
 551                                 {
 552                                         /* TODO: invalid pattern */
 553                                 }
 554                                 else
 555                                         ++p;
 556                         }
 557                         else if (isdigit ((int) *(unsigned char*) p))
 558                         {
 559                                 /* parse line number */
 560                                 entry->address.pattern = p;
 561                                 entry->address.lineNumber = atol (p);
 562                                 while (isdigit ((int) *(unsigned char*) p))
 563                                         ++p;
 564                                 if (p)
 565                                 {
 566                                         combinedPattern = (strncmp (p, ";/", 2) == 0) ||
 567                                                                                         (strncmp (p, ";?", 2) == 0);
 568                                         if (combinedPattern)
 569                                         {
 570                                                 ++p;
 571                                                 /* parse pattern */
 572                                                 int delimiter = *(unsigned char*) p;
 573                                                 do
 574                                                 {
 575                                                         p = strchr (p + 1, delimiter);
 576                                                 } while (p != NULL
 577                                                          &&  isOdd (countContinuousBackslashesBackward (p - 1,
 578                                                                                                         entry->address.pattern)));
 579
 580                                                 if (p == NULL)
 581                                                 {
 582                                                         /* TODO: invalid pattern */
 583                                                 }
 584                                                 else
 585                                                         ++p;
 586                                         }
 587                                 }
 588                         }
 589                         else
 590                         {
 591                                 /* TODO: invalid pattern */
 592                         }
 593
 594                         if (p)
 595                         {
 596                                 fieldsPresent = (strncmp (p, ";\"", 2) == 0);
 597                                 *p = '\0';
 598                                 if (fieldsPresent)
 599                                 {
 600                                         if (parseExtensionFields (file, entry, p + 2, err) != TagSuccess)
 601                                                 return TagFailure;
 602                                 }
 603                         }
 604                 }
 605         }
 606         if (entry->fields.count > 0)
 607                 entry->fields.list = file->fields.list;
 608         for (i = entry->fields.count  ;  i < file->fields.max  ;  ++i)
 609         {
 610                 file->fields.list [i].key = NULL;
 611                 file->fields.list [i].value = NULL;
 612         }
 613         return TagSuccess;
 614 }
 615
 616 static char *duplicate (const char *str)
 617 {
 618         char *result = NULL;
 619         if (str != NULL)
 620         {
 621                 result = strdup (str);
 622                 if (result == NULL)
 623                         perror (NULL);
 624         }
 625         return result;
 626 }
 627
 628 static int isPseudoTagLine (const char *buffer)
 629 {
 630         return (strncmp (buffer, PseudoTagPrefix, PseudoTagPrefixLength) == 0);
 631 }
 632
 633 static tagResult readPseudoTags (tagFile *const file, tagFileInfo *const info)
 634 {
 635         fpos_t startOfLine;
 636         int err = 0;
 637         tagResult result = TagSuccess;
 638         const size_t prefixLength = strlen (PseudoTagPrefix);
 639
 640         info->file.format     = 1;
 641         info->file.sort       = TAG_UNSORTED;
 642         info->program.author  = NULL;
 643         info->program.name    = NULL;
 644         info->program.url     = NULL;
 645         info->program.version = NULL;
 646
 647         while (1)
 648         {
 649                 if (fgetpos (file->fp, &startOfLine) < 0)
 650                 {
 651                         err = errno;
 652                         break;
 653                 }
 654                 if (! readTagLine (file, &err))
 655                         break;
 656                 if (!isPseudoTagLine (file->line.buffer))
 657                         break;
 658                 else
 659                 {
 660                         tagEntry entry;
 661                         const char *key, *value;
 662                         if (parseTagLine (file, &entry, &err) != TagSuccess)
 663                                 break;
 664                         key = entry.name + prefixLength;
 665                         value = entry.file;
 666                         if (strcmp (key, "TAG_FILE_SORTED") == 0)
 667                         {
 668                                 char *endptr = NULL;
 669                                 long m = strtol (value, &endptr, 10);
 670                                 if (*endptr != '\0' || m < 0 || m > 2)
 671                                 {
 672                                         err = TagErrnoUnexpectedSortedMethod;
 673                                         break;
 674                                 }
 675                                 file->sortMethod = (tagSortType) m;
 676                         }
 677                         else if (strcmp (key, "TAG_FILE_FORMAT") == 0)
 678                         {
 679                                 char *endptr = NULL;
 680                                 long m = strtol (value, &endptr, 10);
 681                                 if (*endptr != '\0' || m < 1 || m > 2)
 682                                 {
 683                                         err = TagErrnoUnexpectedFormat;
 684                                         break;
 685                                 }
 686                                 file->format = (short) m;
 687                         }
 688                         else if (strcmp (key, "TAG_PROGRAM_AUTHOR") == 0)
 689                         {
 690                                 file->program.author = duplicate (value);
 691                                 if (value && file->program.author == NULL)
 692                                 {
 693                                         err = ENOMEM;
 694                                         break;
 695                                 }
 696                         }
 697                         else if (strcmp (key, "TAG_PROGRAM_NAME") == 0)
 698                         {
 699                                 file->program.name = duplicate (value);
 700                                 if (value && file->program.name == NULL)
 701                                 {
 702                                         err = ENOMEM;
 703                                         break;
 704                                 }
 705                         }
 706                         else if (strcmp (key, "TAG_PROGRAM_URL") == 0)
 707                         {
 708                                 file->program.url = duplicate (value);
 709                                 if (value && file->program.url == NULL)
 710                                 {
 711                                         err = ENOMEM;
 712                                         break;
 713                                 }
 714                         }
 715                         else if (strcmp (key, "TAG_PROGRAM_VERSION") == 0)
 716                         {
 717                                 file->program.version = duplicate (value);
 718                                 if (value && file->program.version == NULL)
 719                                 {
 720                                         err = ENOMEM;
 721                                         break;
 722                                 }
 723                         }
 724
 725                         info->file.format     = file->format;
 726                         info->file.sort       = file->sortMethod;
 727                         info->program.author  = file->program.author;
 728                         info->program.name    = file->program.name;
 729                         info->program.url     = file->program.url;
 730                         info->program.version = file->program.version;
 731                 }
 732         }
 733         if (fsetpos (file->fp, &startOfLine) < 0)
 734                 err = errno;
 735
 736         info->status.error_number = err;
 737         if (err)
 738                 result = TagFailure;
 739         return result;
 740 }
 741
 742 static int doesFilePointPseudoTag (tagFile *const file, void *unused)
 743 {
 744         return isPseudoTagLine (file->name.buffer);
 745 }
 746
 747 static tagResult gotoFirstLogicalTag (tagFile *const file)
 748 {
 749         fpos_t startOfLine;
 750
 751         if (fseek(file->fp, 0L, SEEK_SET) == -1)
 752         {
 753                 file->err = errno;
 754                 return TagFailure;
 755         }
 756
 757         while (1)
 758         {
 759                 if (fgetpos (file->fp, &startOfLine) < 0)
 760                 {
 761                         file->err = errno;
 762                         return TagFailure;
 763                 }
 764                 if (! readTagLine (file, &file->err))
 765                 {
 766                         if (file->err)
 767                                 return TagFailure;
 768                         break;
 769                 }
 770                 if (!isPseudoTagLine (file->line.buffer))
 771                         break;
 772         }
 773         if (fsetpos (file->fp, &startOfLine) < 0)
 774         {
 775                 file->err = errno;
 776                 return TagFailure;
 777         }
 778         return TagSuccess;
 779 }
 780
 781 static tagFile *initialize (const char *const filePath, tagFileInfo *const info)
 782 {
 783         tagFile *result = (tagFile*) calloc ((size_t) 1, sizeof (tagFile));
 784
 785         if (result == NULL)
 786         {
 787                 info->status.opened = 0;
 788                 info->status.error_number = ENOMEM;
 789                 return NULL;
 790         }
 791
 792         if (growString (&result->line) != TagSuccess)
 793                 goto mem_error;
 794         if (growString (&result->name) != TagSuccess)
 795                 goto mem_error;
 796         result->fields.max = 20;
 797         result->fields.list = (tagExtensionField*) calloc (
 798                 result->fields.max, sizeof (tagExtensionField));
 799         if (result->fields.list == NULL)
 800                 goto mem_error;
 801         result->fp = fopen (filePath, "rb");
 802         if (result->fp == NULL)
 803         {
 804                 info->status.error_number = errno;
 805                 goto file_error;
 806         }
 807         else
 808         {
 809                 if (fseek (result->fp, 0, SEEK_END) == -1)
 810                 {
 811                         info->status.error_number = errno;
 812                         goto file_error;
 813                 }
 814                 result->size = ftell (result->fp);
 815                 if (result->size == -1)
 816                 {
 817                         info->status.error_number = errno;
 818                         goto file_error;
 819                 }
 820                 if (fseek(result->fp, 0L, SEEK_SET) == -1)
 821                 {
 822                         info->status.error_number = errno;
 823                         goto file_error;
 824                 }
 825
 826                 if (readPseudoTags (result, info) == TagFailure)
 827                         goto file_error;
 828
 829                 info->status.opened = 1;
 830                 result->initialized = 1;
 831         }
 832         return result;
 833  mem_error:
 834         info->status.error_number = ENOMEM;
 835  file_error:
 836         free (result->line.buffer);
 837         free (result->name.buffer);
 838         free (result->fields.list);
 839         if (result->fp)
 840                 fclose (result->fp);
 841         free (result);
 842         info->status.opened = 0;
 843         return NULL;
 844 }
 845
 846 static void terminate (tagFile *const file)
 847 {
 848         fclose (file->fp);
 849
 850         free (file->line.buffer);
 851         free (file->name.buffer);
 852         free (file->fields.list);
 853
 854         if (file->program.author != NULL)
 855                 free (file->program.author);
 856         if (file->program.name != NULL)
 857                 free (file->program.name);
 858         if (file->program.url != NULL)
 859                 free (file->program.url);
 860         if (file->program.version != NULL)
 861                 free (file->program.version);
 862         if (file->search.name != NULL)
 863                 free (file->search.name);
 864
 865         memset (file, 0, sizeof (tagFile));
 866
 867         free (file);
 868 }
 869
 870 static tagResult readNext (tagFile *const file, tagEntry *const entry)
 871 {
 872         tagResult result;
 873
 874         if (file == NULL)
 875                 return TagFailure;
 876
 877         if (! file->initialized)
 878         {
 879                 file->err = TagErrnoInvalidArgument;
 880                 return TagFailure;
 881         }
 882
 883         if (! readTagLine (file, &file->err))
 884                 return TagFailure;
 885
 886         result = (entry != NULL)
 887                 ? parseTagLine (file, entry, &file->err)
 888                 : TagSuccess;
 889
 890         return result;
 891 }
 892
 893 static const char *readFieldValue (
 894         const tagEntry *const entry, const char *const key)
 895 {
 896         const char *result = NULL;
 897         int i;
 898         if (strcmp (key, "kind") == 0)
 899                 result = entry->kind;
 900         else if (strcmp (key, "file") == 0)
 901                 result = EmptyString;
 902         else for (i = 0  ;  i < entry->fields.count  &&  result == NULL  ;  ++i)
 903                 if (strcmp (entry->fields.list [i].key, key) == 0)
 904                         result = entry->fields.list [i].value;
 905         return result;
 906 }
 907
 908 static int readTagLineSeek (tagFile *const file, const off_t pos)
 909 {
 910         if (fseek (file->fp, pos, SEEK_SET) < 0)
 911         {
 912                 file->err = errno;
 913                 return 0;
 914         }
 915
 916         /* read probable partial line */
 917         if (!readTagLine (file, &file->err))
 918                 return 0;
 919
 920         /* read complete line */
 921         if (pos > 0)
 922                 return readTagLine (file, &file->err);
 923
 924         return 1;
 925 }
 926
 927 static int nameComparison (tagFile *const file)
 928 {
 929         int result;
 930         if (file->search.ignorecase)
 931         {
 932                 if (file->search.partial)
 933                         result = tagnuppercmp (file->search.name, file->name.buffer,
 934                                         file->search.nameLength);
 935                 else
 936                         result = taguppercmp (file->search.name, file->name.buffer);
 937         }
 938         else
 939         {
 940                 if (file->search.partial)
 941                         result = tagncmp (file->search.name, file->name.buffer,
 942                                         file->search.nameLength);
 943                 else
 944                         result = tagcmp (file->search.name, file->name.buffer);
 945         }
 946         return result;
 947 }
 948
 949 static tagResult findFirstNonMatchBefore (tagFile *const file)
 950 {
 951 #define JUMP_BACK 512
 952         int more_lines;
 953         int comp;
 954         off_t start = file->pos;
 955         off_t pos = start;
 956         do
 957         {
 958                 if (pos < (off_t) JUMP_BACK)
 959                         pos = 0;
 960                 else
 961                         pos = pos - JUMP_BACK;
 962                 more_lines = readTagLineSeek (file, pos);
 963                 if (more_lines == 0 && file->err)
 964                         return TagFailure;
 965                 comp = nameComparison (file);
 966         } while (more_lines  &&  comp == 0  &&  pos > 0  &&  pos < start);
 967         return TagSuccess;
 968 }
 969
 970 static tagResult findFirstMatchBefore (tagFile *const file)
 971 {
 972         tagResult result = TagFailure;
 973         int more_lines;
 974         off_t start = file->pos;
 975         if (findFirstNonMatchBefore (file) != TagSuccess)
 976                 return TagFailure;
 977         do
 978         {
 979                 more_lines = readTagLine (file, &file->err);
 980                 if (more_lines == 0 && file->err)
 981                         return TagFailure;
 982                 if (nameComparison (file) == 0)
 983                         result = TagSuccess;
 984         } while (more_lines  &&  result != TagSuccess  &&  file->pos < start);
 985         return result;
 986 }
 987
 988 static tagResult findBinary (tagFile *const file)
 989 {
 990         tagResult result = TagFailure;
 991         off_t lower_limit = 0;
 992         off_t upper_limit = file->size;
 993         off_t last_pos = 0;
 994         off_t pos = upper_limit / 2;
 995         while (result != TagSuccess)
 996         {
 997                 if (! readTagLineSeek (file, pos))
 998                 {
 999                         if (file->err)
1000                                 break;
1001                         /* in case we fell off end of file */
1002                         result = findFirstMatchBefore (file);
1003                         break;
1004                 }
1005                 else if (pos == last_pos)
1006                 {
1007                         /* prevent infinite loop if we backed up to beginning of file */
1008                         break;
1009                 }
1010                 else
1011                 {
1012                         const int comp = nameComparison (file);
1013                         last_pos = pos;
1014                         if (comp < 0)
1015                         {
1016                                 upper_limit = pos;
1017                                 pos = lower_limit + ((upper_limit - lower_limit) / 2);
1018                         }
1019                         else if (comp > 0)
1020                         {
1021                                 lower_limit = pos;
1022                                 pos = lower_limit + ((upper_limit - lower_limit) / 2);
1023                         }
1024                         else if (pos == 0)
1025                                 result = TagSuccess;
1026                         else
1027                         {
1028                                 result = findFirstMatchBefore (file);
1029                                 if (result != TagSuccess && file->err)
1030                                         break;
1031                         }
1032                 }
1033         }
1034         return result;
1035 }
1036
1037 static tagResult findSequentialFull (tagFile *const file,
1038                                                                          int (* isAcceptable) (tagFile *const, void *),
1039                                                                          void *data)
1040 {
1041         if (file == NULL)
1042                 return TagFailure;
1043
1044         if (!file->initialized || file->err)
1045         {
1046                 file->err = TagErrnoInvalidArgument;
1047                 return TagFailure;
1048         }
1049
1050         tagResult result = TagFailure;
1051         while (result == TagFailure)
1052         {
1053                 if (! readTagLine (file, &file->err))
1054                         break;
1055                 if (isAcceptable (file, data))
1056                         result = TagSuccess;
1057         }
1058         return result;
1059 }
1060
1061 static int nameAcceptable (tagFile *const file, void *unused)
1062 {
1063         return (nameComparison (file) == 0);
1064 }
1065
1066 static tagResult findSequential (tagFile *const file)
1067 {
1068         return findSequentialFull (file, nameAcceptable, NULL);
1069 }
1070
1071 static tagResult find (tagFile *const file, tagEntry *const entry,
1072                                            const char *const name, const int options)
1073 {
1074         tagResult result;
1075         if (file->search.name != NULL)
1076                 free (file->search.name);
1077         file->search.name = duplicate (name);
1078         if (file->search.name == NULL)
1079         {
1080                 file->err = ENOMEM;
1081                 return TagFailure;
1082         }
1083         file->search.nameLength = strlen (name);
1084         file->search.partial = (options & TAG_PARTIALMATCH) != 0;
1085         file->search.ignorecase = (options & TAG_IGNORECASE) != 0;
1086         if (fseek (file->fp, 0, SEEK_END) < 0)
1087         {
1088                 file->err = errno;
1089                 return TagFailure;
1090         }
1091         file->size = ftell (file->fp);
1092         if (file->size == -1)
1093         {
1094                 file->err = errno;
1095                 return TagFailure;
1096         }
1097         if (fseek(file->fp, 0L, SEEK_SET) == -1)
1098         {
1099                 file->err = errno;
1100                 return TagFailure;
1101         }
1102         if ((file->sortMethod == TAG_SORTED      && !file->search.ignorecase) ||
1103                 (file->sortMethod == TAG_FOLDSORTED  &&  file->search.ignorecase))
1104         {
1105                 result = findBinary (file);
1106                 if (result == TagFailure && file->err)
1107                         return TagFailure;
1108         }
1109         else
1110         {
1111                 result = findSequential (file);
1112                 if (result == TagFailure && file->err)
1113                         return TagFailure;
1114         }
1115
1116         if (result != TagSuccess)
1117                 file->search.pos = file->size;
1118         else
1119         {
1120                 file->search.pos = file->pos;
1121                 result = (entry != NULL)
1122                         ? parseTagLine (file, entry, &file->err)
1123                         : TagSuccess;
1124         }
1125         return result;
1126 }
1127
1128 static tagResult findNextFull (tagFile *const file, tagEntry *const entry,
1129                                                            int sorted,
1130                                                            int (* isAcceptable) (tagFile *const, void *),
1131                                                            void *data)
1132 {
1133         tagResult result;
1134         if (sorted)
1135         {
1136                 result = tagsNext (file, entry);
1137                 if (result == TagSuccess  && !isAcceptable (file, data))
1138                         result = TagFailure;
1139         }
1140         else
1141         {
1142                 result = findSequentialFull (file, isAcceptable, data);
1143                 if (result == TagSuccess  &&  entry != NULL)
1144                         result = parseTagLine (file, entry, &file->err);
1145         }
1146         return result;
1147 }
1148
1149 static tagResult findNext (tagFile *const file, tagEntry *const entry)
1150 {
1151         return findNextFull (file, entry,
1152                                                  (file->sortMethod == TAG_SORTED      && !file->search.ignorecase) ||
1153                                                  (file->sortMethod == TAG_FOLDSORTED  &&  file->search.ignorecase),
1154                                                  nameAcceptable, NULL);
1155 }
1156
1157 static tagResult findPseudoTag (tagFile *const file, int rewindBeforeFinding, tagEntry *const entry)
1158 {
1159         if (file == NULL)
1160                 return TagFailure;
1161
1162         if (!file->initialized || file->err)
1163         {
1164                 file->err = TagErrnoInvalidArgument;
1165                 return TagFailure;
1166         }
1167
1168         if (rewindBeforeFinding)
1169         {
1170                 if (fseek(file->fp, 0L, SEEK_SET) == -1)
1171                 {
1172                         file->err = errno;
1173                         return TagFailure;
1174                 }
1175         }
1176         return findNextFull (file, entry,
1177                                                  (file->sortMethod == TAG_SORTED || file->sortMethod == TAG_FOLDSORTED),
1178                                                  doesFilePointPseudoTag,
1179                                                  NULL);
1180 }
1181
1182
1183 /*
1184 *  EXTERNAL INTERFACE
1185 */
1186
1187 extern tagFile *tagsOpen (const char *const filePath, tagFileInfo *const info)
1188 {
1189         tagFileInfo infoDummy;
1190         return initialize (filePath, info? info: &infoDummy);
1191 }
1192
1193 extern tagResult tagsSetSortType (tagFile *const file, const tagSortType type)
1194 {
1195         if (file == NULL)
1196                 return TagFailure;
1197
1198         if (!file->initialized || file->err)
1199         {
1200                 file->err = TagErrnoInvalidArgument;
1201                 return TagFailure;
1202         }
1203
1204         switch (type)
1205         {
1206         case TAG_UNSORTED:
1207         case TAG_SORTED:
1208         case TAG_FOLDSORTED:
1209                 file->sortMethod = type;
1210                 return TagSuccess;
1211         default:
1212                 file->err = TagErrnoUnexpectedSortedMethod;
1213                 return TagFailure;
1214         }
1215 }
1216
1217 extern tagResult tagsFirst (tagFile *const file, tagEntry *const entry)
1218 {
1219         if (file == NULL)
1220                 return TagFailure;
1221
1222         if (!file->initialized || file->err)
1223         {
1224                 file->err = TagErrnoInvalidArgument;
1225                 return TagFailure;
1226         }
1227
1228         if (gotoFirstLogicalTag (file) != TagSuccess)
1229                 return TagFailure;
1230         return readNext (file, entry);
1231 }
1232
1233 extern tagResult tagsNext (tagFile *const file, tagEntry *const entry)
1234 {
1235         if (file == NULL)
1236                 return TagFailure;
1237
1238         if (!file->initialized || file->err)
1239         {
1240                 file->err = TagErrnoInvalidArgument;
1241                 return TagFailure;
1242         }
1243
1244         return readNext (file, entry);
1245 }
1246
1247 extern const char *tagsField (const tagEntry *const entry, const char *const key)
1248 {
1249         const char *result = NULL;
1250         if (entry != NULL)
1251                 result = readFieldValue (entry, key);
1252         return result;
1253 }
1254
1255 extern tagResult tagsFind (tagFile *const file, tagEntry *const entry,
1256                                                    const char *const name, const int options)
1257 {
1258         if (file == NULL)
1259                 return TagFailure;
1260
1261         if (!file->initialized || file->err)
1262         {
1263                 file->err = TagErrnoInvalidArgument;
1264                 return TagFailure;
1265         }
1266
1267         return find (file, entry, name, options);
1268 }
1269
1270 extern tagResult tagsFindNext (tagFile *const file, tagEntry *const entry)
1271 {
1272         if (file == NULL)
1273                 return TagFailure;
1274
1275         if (!file->initialized || file->err)
1276         {
1277                 file->err = TagErrnoInvalidArgument;
1278                 return TagFailure;
1279         }
1280
1281         return findNext (file, entry);
1282 }
1283
1284 extern tagResult tagsFirstPseudoTag (tagFile *const file, tagEntry *const entry)
1285 {
1286         return findPseudoTag (file, 1, entry);
1287 }
1288
1289 extern tagResult tagsNextPseudoTag (tagFile *const file, tagEntry *const entry)
1290 {
1291         return findPseudoTag (file, 0, entry);
1292 }
1293
1294 extern tagResult tagsClose (tagFile *const file)
1295 {
1296         tagResult result = TagFailure;
1297         if (file != NULL  &&  file->initialized)
1298         {
1299                 terminate (file);
1300                 result = TagSuccess;
1301         }
1302         return result;
1303 }
1304
1305 extern int tagsGetErrno (tagFile *const file)
1306 {
1307         if (file == NULL)
1308                 return TagErrnoInvalidArgument;
1309         return file->err;
1310 }