gio/xdgmime/xdgmimeglob.c

   1 /* -*- mode: C; c-file-style: "gnu" -*- */
   2 /* xdgmimeglob.c: Private file.  Datastructure for storing the globs.
   3  *
   4  * More info can be found at http://www.freedesktop.org/standards/
   5  *
   6  * Copyright (C) 2003  Red Hat, Inc.
   7  * Copyright (C) 2003  Jonathan Blandford <jrb@alum.mit.edu>
   8  *
   9  * Licensed under the Academic Free License version 2.0
  10  * Or under the following terms:
  11  *
  12  * This library is free software; you can redistribute it and/or
  13  * modify it under the terms of the GNU Lesser General Public
  14  * License as published by the Free Software Foundation; either
  15  * version 2 of the License, or (at your option) any later version.
  16  *
  17  * This library is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20  * Lesser General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public
  23  * License along with this library; if not, write to the
  24  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  25  * Boston, MA 02111-1307, USA.
  26  */
  27
  28 #ifdef HAVE_CONFIG_H
  29 #include "config.h"
  30 #endif
  31
  32 #include "xdgmimeglob.h"
  33 #include "xdgmimeint.h"
  34 #include <stdlib.h>
  35 #include <stdio.h>
  36 #include <assert.h>
  37 #include <string.h>
  38 #include <fnmatch.h>
  39
  40 #ifndef MAX
  41 #define MAX(a,b) ((a) > (b) ? (a) : (b))
  42 #endif
  43
  44 #ifndef FALSE
  45 #define FALSE   (0)
  46 #endif
  47
  48 #ifndef TRUE
  49 #define TRUE    (!FALSE)
  50 #endif
  51
  52 typedef struct XdgGlobHashNode XdgGlobHashNode;
  53 typedef struct XdgGlobList XdgGlobList;
  54
  55 struct XdgGlobHashNode
  56 {
  57   xdg_unichar_t character;
  58   const char *mime_type;
  59   int weight;
  60   int case_sensitive;
  61   XdgGlobHashNode *next;
  62   XdgGlobHashNode *child;
  63 };
  64 struct XdgGlobList
  65 {
  66   const char *data;
  67   const char *mime_type;
  68   int weight;
  69   int case_sensitive;
  70   XdgGlobList *next;
  71 };
  72
  73 struct XdgGlobHash
  74 {
  75   XdgGlobList *literal_list;
  76   XdgGlobHashNode *simple_node;
  77   XdgGlobList *full_list;
  78 };
  79
  80
  81 /* XdgGlobList
  82  */
  83 static XdgGlobList *
  84 _xdg_glob_list_new (void)
  85 {
  86   XdgGlobList *new_element;
  87
  88   new_element = calloc (1, sizeof (XdgGlobList));
  89
  90   return new_element;
  91 }
  92
  93 /* Frees glob_list and all of it's children */
  94 static void
  95 _xdg_glob_list_free (XdgGlobList *glob_list)
  96 {
  97   XdgGlobList *ptr, *next;
  98
  99   ptr = glob_list;
 100
 101   while (ptr != NULL)
 102     {
 103       next = ptr->next;
 104
 105       if (ptr->data)
 106         free ((void *) ptr->data);
 107       if (ptr->mime_type)
 108         free ((void *) ptr->mime_type);
 109       free (ptr);
 110
 111       ptr = next;
 112     }
 113 }
 114
 115 static XdgGlobList *
 116 _xdg_glob_list_append (XdgGlobList *glob_list,
 117                        void        *data,
 118                        const char  *mime_type,
 119                        int          weight,
 120                        int          case_sensitive)
 121 {
 122   XdgGlobList *new_element;
 123   XdgGlobList *tmp_element;
 124
 125   tmp_element = glob_list;
 126   while (tmp_element != NULL)
 127     {
 128       if (strcmp (tmp_element->data, data) == 0 &&
 129           strcmp (tmp_element->mime_type, mime_type) == 0)
 130         return glob_list;
 131
 132       tmp_element = tmp_element->next;
 133     }
 134
 135   new_element = _xdg_glob_list_new ();
 136   new_element->data = data;
 137   new_element->mime_type = mime_type;
 138   new_element->weight = weight;
 139   new_element->case_sensitive = case_sensitive;
 140   if (glob_list == NULL)
 141     return new_element;
 142
 143   tmp_element = glob_list;
 144   while (tmp_element->next != NULL)
 145     tmp_element = tmp_element->next;
 146
 147   tmp_element->next = new_element;
 148
 149   return glob_list;
 150 }
 151
 152 /* XdgGlobHashNode
 153  */
 154
 155 static XdgGlobHashNode *
 156 _xdg_glob_hash_node_new (void)
 157 {
 158   XdgGlobHashNode *glob_hash_node;
 159
 160   glob_hash_node = calloc (1, sizeof (XdgGlobHashNode));
 161
 162   return glob_hash_node;
 163 }
 164
 165 #ifdef NOT_USED_IN_GIO
 166
 167 static void
 168 _xdg_glob_hash_node_dump (XdgGlobHashNode *glob_hash_node,
 169                           int depth)
 170 {
 171   int i;
 172   for (i = 0; i < depth; i++)
 173     printf (" ");
 174
 175   printf ("%c", (char)glob_hash_node->character);
 176   if (glob_hash_node->mime_type)
 177     printf (" - %s %d\n", glob_hash_node->mime_type, glob_hash_node->weight);
 178   else
 179     printf ("\n");
 180   if (glob_hash_node->child)
 181     _xdg_glob_hash_node_dump (glob_hash_node->child, depth + 1);
 182   if (glob_hash_node->next)
 183     _xdg_glob_hash_node_dump (glob_hash_node->next, depth);
 184 }
 185
 186 #endif
 187
 188 static XdgGlobHashNode *
 189 _xdg_glob_hash_insert_ucs4 (XdgGlobHashNode *glob_hash_node,
 190                             xdg_unichar_t   *text,
 191                             const char      *mime_type,
 192                             int              weight,
 193                             int              case_sensitive)
 194 {
 195   XdgGlobHashNode *node;
 196   xdg_unichar_t character;
 197
 198   character = text[0];
 199
 200   if ((glob_hash_node == NULL) ||
 201       (character < glob_hash_node->character))
 202     {
 203       node = _xdg_glob_hash_node_new ();
 204       node->character = character;
 205       node->next = glob_hash_node;
 206       glob_hash_node = node;
 207     }
 208   else if (character == glob_hash_node->character)
 209     {
 210       node = glob_hash_node;
 211     }
 212   else
 213     {
 214       XdgGlobHashNode *prev_node;
 215       int found_node = FALSE;
 216
 217       /* Look for the first character of text in glob_hash_node, and insert it if we
 218        * have to.*/
 219       prev_node = glob_hash_node;
 220       node = prev_node->next;
 221
 222       while (node != NULL)
 223         {
 224           if (character < node->character)
 225             {
 226               node = _xdg_glob_hash_node_new ();
 227               node->character = character;
 228               node->next = prev_node->next;
 229               prev_node->next = node;
 230
 231               found_node = TRUE;
 232               break;
 233             }
 234           else if (character == node->character)
 235             {
 236               found_node = TRUE;
 237               break;
 238             }
 239           prev_node = node;
 240           node = node->next;
 241         }
 242
 243       if (! found_node)
 244         {
 245           node = _xdg_glob_hash_node_new ();
 246           node->character = character;
 247           node->next = prev_node->next;
 248           prev_node->next = node;
 249         }
 250     }
 251
 252   text++;
 253   if (*text == 0)
 254     {
 255       if (node->mime_type)
 256         {
 257           if (strcmp (node->mime_type, mime_type) != 0)
 258             {
 259               XdgGlobHashNode *child;
 260               int found_node = FALSE;
 261
 262               child = node->child;
 263               while (child && child->character == 0)
 264                 {
 265                   if (strcmp (child->mime_type, mime_type) == 0)
 266                     {
 267                       found_node = TRUE;
 268                       break;
 269                     }
 270                   child = child->next;
 271                 }
 272
 273               if (!found_node)
 274                 {
 275                   child = _xdg_glob_hash_node_new ();
 276                   child->character = 0;
 277                   child->mime_type = strdup (mime_type);
 278                   child->weight = weight;
 279                   child->case_sensitive = case_sensitive;
 280                   child->child = NULL;
 281                   child->next = node->child;
 282                   node->child = child;
 283                 }
 284             }
 285         }
 286       else
 287         {
 288           node->mime_type = strdup (mime_type);
 289           node->weight = weight;
 290           node->case_sensitive = case_sensitive;
 291         }
 292     }
 293   else
 294     {
 295       node->child = _xdg_glob_hash_insert_ucs4 (node->child, text, mime_type, weight, case_sensitive);
 296     }
 297   return glob_hash_node;
 298 }
 299
 300 /* glob must be valid UTF-8 */
 301 static XdgGlobHashNode *
 302 _xdg_glob_hash_insert_text (XdgGlobHashNode *glob_hash_node,
 303                             const char      *text,
 304                             const char      *mime_type,
 305                             int              weight,
 306                             int              case_sensitive)
 307 {
 308   XdgGlobHashNode *node;
 309   xdg_unichar_t *unitext;
 310   int len;
 311
 312   unitext = _xdg_convert_to_ucs4 (text, &len);
 313   _xdg_reverse_ucs4 (unitext, len);
 314   node = _xdg_glob_hash_insert_ucs4 (glob_hash_node, unitext, mime_type, weight, case_sensitive);
 315   free (unitext);
 316   return node;
 317 }
 318
 319 typedef struct {
 320   const char *mime;
 321   int weight;
 322 } MimeWeight;
 323
 324 static int
 325 _xdg_glob_hash_node_lookup_file_name (XdgGlobHashNode *glob_hash_node,
 326                                       const char      *file_name,
 327                                       int              len,
 328                                       int              case_sensitive_check,
 329                                       MimeWeight       mime_types[],
 330                                       int              n_mime_types)
 331 {
 332   int n;
 333   XdgGlobHashNode *node;
 334   xdg_unichar_t character;
 335
 336   if (glob_hash_node == NULL)
 337     return 0;
 338
 339   character = file_name[len - 1];
 340
 341   for (node = glob_hash_node; node && character >= node->character; node = node->next)
 342     {
 343       if (character == node->character)
 344         {
 345           len--;
 346           n = 0;
 347           if (len > 0)
 348             {
 349               n = _xdg_glob_hash_node_lookup_file_name (node->child,
 350                                                         file_name,
 351                                                         len,
 352                                                         case_sensitive_check,
 353                                                         mime_types,
 354                                                         n_mime_types);
 355             }
 356           if (n == 0)
 357             {
 358               if (node->mime_type &&
 359                   (case_sensitive_check ||
 360                    !node->case_sensitive))
 361                 {
 362                   mime_types[n].mime = node->mime_type;
 363                   mime_types[n].weight = node->weight;
 364                   n++;
 365                 }
 366               node = node->child;
 367               while (n < n_mime_types && node && node->character == 0)
 368                 {
 369                   if (node->mime_type &&
 370                       (case_sensitive_check ||
 371                        !node->case_sensitive))
 372                     {
 373                       mime_types[n].mime = node->mime_type;
 374                       mime_types[n].weight = node->weight;
 375                       n++;
 376                     }
 377                   node = node->next;
 378                 }
 379             }
 380           return n;
 381         }
 382     }
 383
 384   return 0;
 385 }
 386
 387 static int compare_mime_weight (const void *a, const void *b)
 388 {
 389   const MimeWeight *aa = (const MimeWeight *)a;
 390   const MimeWeight *bb = (const MimeWeight *)b;
 391
 392   return bb->weight - aa->weight;
 393 }
 394
 395 #define ISUPPER(c)              ((c) >= 'A' && (c) <= 'Z')
 396 static char *
 397 ascii_tolower (const char *str)
 398 {
 399   char *p, *lower;
 400
 401   lower = strdup (str);
 402   p = lower;
 403   while (*p != 0)
 404     {
 405       char c = *p;
 406       *p++ = ISUPPER (c) ? c - 'A' + 'a' : c;
 407     }
 408   return lower;
 409 }
 410
 411 static int
 412 filter_out_dupes (MimeWeight mimes[], int n_mimes)
 413 {
 414   int last;
 415   int i, j;
 416
 417   last = n_mimes;
 418
 419   for (i = 0; i < last; i++)
 420     {
 421       j = i + 1;
 422       while (j < last)
 423         {
 424           if (strcmp (mimes[i].mime, mimes[j].mime) == 0)
 425             {
 426               mimes[i].weight = MAX (mimes[i].weight, mimes[j].weight);
 427               last--;
 428               mimes[j].mime = mimes[last].mime;
 429               mimes[j].weight = mimes[last].weight;
 430             }
 431           else
 432             j++;
 433         }
 434     }
 435
 436   return last;
 437 }
 438
 439 int
 440 _xdg_glob_hash_lookup_file_name (XdgGlobHash *glob_hash,
 441                                  const char  *file_name,
 442                                  const char  *mime_types[],
 443                                  int          n_mime_types)
 444 {
 445   XdgGlobList *list;
 446   int i, n;
 447   MimeWeight mimes[10];
 448   int n_mimes = 10;
 449   int len;
 450   char *lower_case;
 451
 452   /* First, check the literals */
 453
 454   assert (file_name != NULL && n_mime_types > 0);
 455
 456   n = 0;
 457
 458   lower_case = ascii_tolower (file_name);
 459
 460   for (list = glob_hash->literal_list; list; list = list->next)
 461     {
 462       if (strcmp ((const char *)list->data, file_name) == 0)
 463         {
 464           mime_types[0] = list->mime_type;
 465           free (lower_case);
 466           return 1;
 467         }
 468     }
 469
 470   for (list = glob_hash->literal_list; list; list = list->next)
 471     {
 472       if (!list->case_sensitive &&
 473           strcmp ((const char *)list->data, lower_case) == 0)
 474         {
 475           mime_types[0] = list->mime_type;
 476           free (lower_case);
 477           return 1;
 478         }
 479     }
 480
 481
 482   len = strlen (file_name);
 483   n = _xdg_glob_hash_node_lookup_file_name (glob_hash->simple_node, lower_case, len, FALSE,
 484                                             mimes, n_mimes);
 485   if (n < 2)
 486     n += _xdg_glob_hash_node_lookup_file_name (glob_hash->simple_node, file_name, len, TRUE,
 487                                                mimes + n, n_mimes - n);
 488
 489   if (n < 2)
 490     {
 491       for (list = glob_hash->full_list; list && n < n_mime_types; list = list->next)
 492         {
 493           if (fnmatch ((const char *)list->data, file_name, 0) == 0)
 494             {
 495               mimes[n].mime = list->mime_type;
 496               mimes[n].weight = list->weight;
 497               n++;
 498             }
 499         }
 500     }
 501   free (lower_case);
 502
 503   n = filter_out_dupes (mimes, n);
 504
 505   qsort (mimes, n, sizeof (MimeWeight), compare_mime_weight);
 506
 507   if (n_mime_types < n)
 508     n = n_mime_types;
 509
 510   for (i = 0; i < n; i++)
 511     mime_types[i] = mimes[i].mime;
 512
 513   return n;
 514 }
 515
 516
 517
 518 /* XdgGlobHash
 519  */
 520
 521 XdgGlobHash *
 522 _xdg_glob_hash_new (void)
 523 {
 524   XdgGlobHash *glob_hash;
 525
 526   glob_hash = calloc (1, sizeof (XdgGlobHash));
 527
 528   return glob_hash;
 529 }
 530
 531
 532 static void
 533 _xdg_glob_hash_free_nodes (XdgGlobHashNode *node)
 534 {
 535   if (node)
 536     {
 537       if (node->child)
 538        _xdg_glob_hash_free_nodes (node->child);
 539       if (node->next)
 540        _xdg_glob_hash_free_nodes (node->next);
 541       if (node->mime_type)
 542         free ((void *) node->mime_type);
 543       free (node);
 544     }
 545 }
 546
 547 void
 548 _xdg_glob_hash_free (XdgGlobHash *glob_hash)
 549 {
 550   _xdg_glob_list_free (glob_hash->literal_list);
 551   _xdg_glob_list_free (glob_hash->full_list);
 552   _xdg_glob_hash_free_nodes (glob_hash->simple_node);
 553   free (glob_hash);
 554 }
 555
 556 XdgGlobType
 557 _xdg_glob_determine_type (const char *glob)
 558 {
 559   const char *ptr;
 560   int maybe_in_simple_glob = FALSE;
 561   int first_char = TRUE;
 562
 563   ptr = glob;
 564
 565   while (*ptr != '\0')
 566     {
 567       if (*ptr == '*' && first_char)
 568         maybe_in_simple_glob = TRUE;
 569       else if (*ptr == '\\' || *ptr == '[' || *ptr == '?' || *ptr == '*')
 570           return XDG_GLOB_FULL;
 571
 572       first_char = FALSE;
 573       ptr = _xdg_utf8_next_char (ptr);
 574     }
 575   if (maybe_in_simple_glob)
 576     return XDG_GLOB_SIMPLE;
 577   else
 578     return XDG_GLOB_LITERAL;
 579 }
 580
 581 /* glob must be valid UTF-8 */
 582 void
 583 _xdg_glob_hash_append_glob (XdgGlobHash *glob_hash,
 584                             const char  *glob,
 585                             const char  *mime_type,
 586                             int          weight,
 587                             int          case_sensitive)
 588 {
 589   XdgGlobType type;
 590
 591   assert (glob_hash != NULL);
 592   assert (glob != NULL);
 593
 594   type = _xdg_glob_determine_type (glob);
 595
 596   switch (type)
 597     {
 598     case XDG_GLOB_LITERAL:
 599       glob_hash->literal_list = _xdg_glob_list_append (glob_hash->literal_list, strdup (glob), strdup (mime_type), weight, case_sensitive);
 600       break;
 601     case XDG_GLOB_SIMPLE:
 602       glob_hash->simple_node = _xdg_glob_hash_insert_text (glob_hash->simple_node, glob + 1, mime_type, weight, case_sensitive);
 603       break;
 604     case XDG_GLOB_FULL:
 605       glob_hash->full_list = _xdg_glob_list_append (glob_hash->full_list, strdup (glob), strdup (mime_type), weight, case_sensitive);
 606       break;
 607     }
 608 }
 609
 610 #ifdef NOT_USED_IN_GIO
 611
 612 void
 613 _xdg_glob_hash_dump (XdgGlobHash *glob_hash)
 614 {
 615   XdgGlobList *list;
 616   printf ("LITERAL STRINGS\n");
 617   if (!glob_hash || glob_hash->literal_list == NULL)
 618     {
 619       printf ("    None\n");
 620     }
 621   else
 622     {
 623       for (list = glob_hash->literal_list; list; list = list->next)
 624         printf ("    %s - %s %d\n", (char *)list->data, list->mime_type, list->weight);
 625     }
 626   printf ("\nSIMPLE GLOBS\n");
 627   if (!glob_hash || glob_hash->simple_node == NULL)
 628     {
 629       printf ("    None\n");
 630     }
 631   else
 632     {
 633       _xdg_glob_hash_node_dump (glob_hash->simple_node, 4);
 634     }
 635
 636   printf ("\nFULL GLOBS\n");
 637   if (!glob_hash || glob_hash->full_list == NULL)
 638     {
 639       printf ("    None\n");
 640     }
 641   else
 642     {
 643       for (list = glob_hash->full_list; list; list = list->next)
 644         printf ("    %s - %s %d\n", (char *)list->data, list->mime_type, list->weight);
 645     }
 646 }
 647
 648 #endif
 649
 650 void
 651 _xdg_mime_glob_read_from_file (XdgGlobHash *glob_hash,
 652                                const char  *file_name,
 653                                int          version_two)
 654 {
 655   FILE *glob_file;
 656   char line[255];
 657   char *p;
 658
 659   glob_file = fopen (file_name, "r");
 660
 661   if (glob_file == NULL)
 662     return;
 663
 664   /* FIXME: Not UTF-8 safe.  Doesn't work if lines are greater than 255 chars.
 665    * Blah */
 666   while (fgets (line, 255, glob_file) != NULL)
 667     {
 668       char *colon;
 669       char *mimetype, *glob, *end;
 670       int weight;
 671       int case_sensitive;
 672
 673       if (line[0] == '#' || line[0] == 0)
 674         continue;
 675
 676       end = line + strlen(line) - 1;
 677       if (*end == '\n')
 678         *end = 0;
 679
 680       p = line;
 681       if (version_two)
 682         {
 683           colon = strchr (p, ':');
 684           if (colon == NULL)
 685             continue;
 686           *colon = 0;
 687           weight = atoi (p);
 688           p = colon + 1;
 689         }
 690       else
 691         weight = 50;
 692
 693       colon = strchr (p, ':');
 694       if (colon == NULL)
 695         continue;
 696       *colon = 0;
 697
 698       mimetype = p;
 699       p = colon + 1;
 700       glob = p;
 701       case_sensitive = FALSE;
 702
 703       colon = strchr (p, ':');
 704       if (version_two && colon != NULL)
 705         {
 706           char *flag;
 707
 708           /* We got flags */
 709           *colon = 0;
 710           p = colon + 1;
 711
 712           /* Flags end at next colon */
 713           colon = strchr (p, ':');
 714           if (colon != NULL)
 715             *colon = 0;
 716
 717           flag = strstr (p, "cs");
 718           if (flag != NULL &&
 719               /* Start or after comma */
 720               (flag == p ||
 721                flag[-1] == ',') &&
 722               /* ends with comma or end of string */
 723               (flag[2] == 0 ||
 724                flag[2] == ','))
 725             case_sensitive = TRUE;
 726         }
 727
 728       _xdg_glob_hash_append_glob (glob_hash, glob, mimetype, weight, case_sensitive);
 729     }
 730
 731   fclose (glob_file);
 732 }