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