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 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 static XdgGlobHashNode *
 185 _xdg_glob_hash_insert_ucs4 (XdgGlobHashNode *glob_hash_node,
 186                             xdg_unichar_t   *text,
 187                             const char      *mime_type,
 188                             int              weight,
 189                             int              case_sensitive)
 190 {
 191   XdgGlobHashNode *node;
 192   xdg_unichar_t character;
 193
 194   character = text[0];
 195
 196   if ((glob_hash_node == NULL) ||
 197       (character < glob_hash_node->character))
 198     {
 199       node = _xdg_glob_hash_node_new ();
 200       node->character = character;
 201       node->next = glob_hash_node;
 202       glob_hash_node = node;
 203     }
 204   else if (character == glob_hash_node->character)
 205     {
 206       node = glob_hash_node;
 207     }
 208   else
 209     {
 210       XdgGlobHashNode *prev_node;
 211       int found_node = FALSE;
 212
 213       /* Look for the first character of text in glob_hash_node, and insert it if we
 214        * have to.*/
 215       prev_node = glob_hash_node;
 216       node = prev_node->next;
 217
 218       while (node != NULL)
 219         {
 220           if (character < node->character)
 221             {
 222               node = _xdg_glob_hash_node_new ();
 223               node->character = character;
 224               node->next = prev_node->next;
 225               prev_node->next = node;
 226
 227               found_node = TRUE;
 228               break;
 229             }
 230           else if (character == node->character)
 231             {
 232               found_node = TRUE;
 233               break;
 234             }
 235           prev_node = node;
 236           node = node->next;
 237         }
 238
 239       if (! found_node)
 240         {
 241           node = _xdg_glob_hash_node_new ();
 242           node->character = character;
 243           node->next = prev_node->next;
 244           prev_node->next = node;
 245         }
 246     }
 247
 248   text++;
 249   if (*text == 0)
 250     {
 251       if (node->mime_type)
 252         {
 253           if (strcmp (node->mime_type, mime_type) != 0)
 254             {
 255               XdgGlobHashNode *child;
 256               int found_node = FALSE;
 257
 258               child = node->child;
 259               while (child && child->character == 0)
 260                 {
 261                   if (strcmp (child->mime_type, mime_type) == 0)
 262                     {
 263                       found_node = TRUE;
 264                       break;
 265                     }
 266                   child = child->next;
 267                 }
 268
 269               if (!found_node)
 270                 {
 271                   child = _xdg_glob_hash_node_new ();
 272                   child->character = 0;
 273                   child->mime_type = strdup (mime_type);
 274                   child->weight = weight;
 275                   child->case_sensitive = case_sensitive;
 276                   child->child = NULL;
 277                   child->next = node->child;
 278                   node->child = child;
 279                 }
 280             }
 281         }
 282       else
 283         {
 284           node->mime_type = strdup (mime_type);
 285           node->weight = weight;
 286           node->case_sensitive = case_sensitive;
 287         }
 288     }
 289   else
 290     {
 291       node->child = _xdg_glob_hash_insert_ucs4 (node->child, text, mime_type, weight, case_sensitive);
 292     }
 293   return glob_hash_node;
 294 }
 295
 296 /* glob must be valid UTF-8 */
 297 static XdgGlobHashNode *
 298 _xdg_glob_hash_insert_text (XdgGlobHashNode *glob_hash_node,
 299                             const char      *text,
 300                             const char      *mime_type,
 301                             int              weight,
 302                             int              case_sensitive)
 303 {
 304   XdgGlobHashNode *node;
 305   xdg_unichar_t *unitext;
 306   int len;
 307
 308   unitext = _xdg_convert_to_ucs4 (text, &len);
 309   _xdg_reverse_ucs4 (unitext, len);
 310   node = _xdg_glob_hash_insert_ucs4 (glob_hash_node, unitext, mime_type, weight, case_sensitive);
 311   free (unitext);
 312   return node;
 313 }
 314
 315 typedef struct {
 316   const char *mime;
 317   int weight;
 318 } MimeWeight;
 319
 320 static int
 321 _xdg_glob_hash_node_lookup_file_name (XdgGlobHashNode *glob_hash_node,
 322                                       const char      *file_name,
 323                                       int              len,
 324                                       int              case_sensitive_check,
 325                                       MimeWeight       mime_types[],
 326                                       int              n_mime_types)
 327 {
 328   int n;
 329   XdgGlobHashNode *node;
 330   xdg_unichar_t character;
 331
 332   if (glob_hash_node == NULL)
 333     return 0;
 334
 335   character = file_name[len - 1];
 336
 337   for (node = glob_hash_node; node && character >= node->character; node = node->next)
 338     {
 339       if (character == node->character)
 340         {
 341           len--;
 342           n = 0;
 343           if (len > 0)
 344             {
 345               n = _xdg_glob_hash_node_lookup_file_name (node->child,
 346                                                         file_name,
 347                                                         len,
 348                                                         case_sensitive_check,
 349                                                         mime_types,
 350                                                         n_mime_types);
 351             }
 352           if (n == 0)
 353             {
 354               if (node->mime_type &&
 355                   (case_sensitive_check ||
 356                    !node->case_sensitive))
 357                 {
 358                   mime_types[n].mime = node->mime_type;
 359                   mime_types[n].weight = node->weight;
 360                   n++;
 361                 }
 362               node = node->child;
 363               while (n < n_mime_types && node && node->character == 0)
 364                 {
 365                   if (node->mime_type &&
 366                       (case_sensitive_check ||
 367                        !node->case_sensitive))
 368                     {
 369                       mime_types[n].mime = node->mime_type;
 370                       mime_types[n].weight = node->weight;
 371                       n++;
 372                     }
 373                   node = node->next;
 374                 }
 375             }
 376           return n;
 377         }
 378     }
 379
 380   return 0;
 381 }
 382
 383 static int compare_mime_weight (const void *a, const void *b)
 384 {
 385   const MimeWeight *aa = (const MimeWeight *)a;
 386   const MimeWeight *bb = (const MimeWeight *)b;
 387
 388   return bb->weight - aa->weight;
 389 }
 390
 391 #define ISUPPER(c)              ((c) >= 'A' && (c) <= 'Z')
 392 static char *
 393 ascii_tolower (const char *str)
 394 {
 395   char *p, *lower;
 396
 397   lower = strdup (str);
 398   p = lower;
 399   while (*p != 0)
 400     {
 401       char c = *p;
 402       *p++ = ISUPPER (c) ? c - 'A' + 'a' : c;
 403     }
 404   return lower;
 405 }
 406
 407 static int
 408 filter_out_dupes (MimeWeight mimes[], int n_mimes)
 409 {
 410   int last;
 411   int i, j;
 412
 413   last = n_mimes;
 414
 415   for (i = 0; i < last; i++)
 416     {
 417       j = i + 1;
 418       while (j < last)
 419         {
 420           if (strcmp (mimes[i].mime, mimes[j].mime) == 0)
 421             {
 422               mimes[i].weight = MAX (mimes[i].weight, mimes[j].weight);
 423               last--;
 424               mimes[j].mime = mimes[last].mime;
 425               mimes[j].weight = mimes[last].weight;
 426             }
 427           else
 428             j++;
 429         }
 430     }
 431
 432   return last;
 433 }
 434
 435 int
 436 _xdg_glob_hash_lookup_file_name (XdgGlobHash *glob_hash,
 437                                  const char  *file_name,
 438                                  const char  *mime_types[],
 439                                  int          n_mime_types)
 440 {
 441   XdgGlobList *list;
 442   int i, n;
 443   MimeWeight mimes[10];
 444   int n_mimes = 10;
 445   int len;
 446   char *lower_case;
 447
 448   /* First, check the literals */
 449
 450   assert (file_name != NULL && n_mime_types > 0);
 451
 452   n = 0;
 453
 454   lower_case = ascii_tolower (file_name);
 455
 456   for (list = glob_hash->literal_list; list; list = list->next)
 457     {
 458       if (strcmp ((const char *)list->data, file_name) == 0)
 459         {
 460           mime_types[0] = list->mime_type;
 461           free (lower_case);
 462           return 1;
 463         }
 464     }
 465
 466   for (list = glob_hash->literal_list; list; list = list->next)
 467     {
 468       if (!list->case_sensitive &&
 469           strcmp ((const char *)list->data, lower_case) == 0)
 470         {
 471           mime_types[0] = list->mime_type;
 472           free (lower_case);
 473           return 1;
 474         }
 475     }
 476
 477
 478   len = strlen (file_name);
 479   n = _xdg_glob_hash_node_lookup_file_name (glob_hash->simple_node, lower_case, len, FALSE,
 480                                             mimes, n_mimes);
 481   if (n < 2)
 482     n += _xdg_glob_hash_node_lookup_file_name (glob_hash->simple_node, file_name, len, TRUE,
 483                                                mimes + n, n_mimes - n);
 484
 485   if (n < 2)
 486     {
 487       for (list = glob_hash->full_list; list && n < n_mime_types; list = list->next)
 488         {
 489           if (fnmatch ((const char *)list->data, file_name, 0) == 0)
 490             {
 491               mimes[n].mime = list->mime_type;
 492               mimes[n].weight = list->weight;
 493               n++;
 494             }
 495         }
 496     }
 497   free (lower_case);
 498
 499   n = filter_out_dupes (mimes, n);
 500
 501   qsort (mimes, n, sizeof (MimeWeight), compare_mime_weight);
 502
 503   if (n_mime_types < n)
 504     n = n_mime_types;
 505
 506   for (i = 0; i < n; i++)
 507     mime_types[i] = mimes[i].mime;
 508
 509   return n;
 510 }
 511
 512
 513
 514 /* XdgGlobHash
 515  */
 516
 517 XdgGlobHash *
 518 _xdg_glob_hash_new (void)
 519 {
 520   XdgGlobHash *glob_hash;
 521
 522   glob_hash = calloc (1, sizeof (XdgGlobHash));
 523
 524   return glob_hash;
 525 }
 526
 527
 528 static void
 529 _xdg_glob_hash_free_nodes (XdgGlobHashNode *node)
 530 {
 531   if (node)
 532     {
 533       if (node->child)
 534        _xdg_glob_hash_free_nodes (node->child);
 535       if (node->next)
 536        _xdg_glob_hash_free_nodes (node->next);
 537       if (node->mime_type)
 538         free ((void *) node->mime_type);
 539       free (node);
 540     }
 541 }
 542
 543 void
 544 _xdg_glob_hash_free (XdgGlobHash *glob_hash)
 545 {
 546   _xdg_glob_list_free (glob_hash->literal_list);
 547   _xdg_glob_list_free (glob_hash->full_list);
 548   _xdg_glob_hash_free_nodes (glob_hash->simple_node);
 549   free (glob_hash);
 550 }
 551
 552 XdgGlobType
 553 _xdg_glob_determine_type (const char *glob)
 554 {
 555   const char *ptr;
 556   int maybe_in_simple_glob = FALSE;
 557   int first_char = TRUE;
 558
 559   ptr = glob;
 560
 561   while (*ptr != '\0')
 562     {
 563       if (*ptr == '*' && first_char)
 564         maybe_in_simple_glob = TRUE;
 565       else if (*ptr == '\\' || *ptr == '[' || *ptr == '?' || *ptr == '*')
 566           return XDG_GLOB_FULL;
 567
 568       first_char = FALSE;
 569       ptr = _xdg_utf8_next_char (ptr);
 570     }
 571   if (maybe_in_simple_glob)
 572     return XDG_GLOB_SIMPLE;
 573   else
 574     return XDG_GLOB_LITERAL;
 575 }
 576
 577 /* glob must be valid UTF-8 */
 578 void
 579 _xdg_glob_hash_append_glob (XdgGlobHash *glob_hash,
 580                             const char  *glob,
 581                             const char  *mime_type,
 582                             int          weight,
 583                             int          case_sensitive)
 584 {
 585   XdgGlobType type;
 586
 587   assert (glob_hash != NULL);
 588   assert (glob != NULL);
 589
 590   type = _xdg_glob_determine_type (glob);
 591
 592   switch (type)
 593     {
 594     case XDG_GLOB_LITERAL:
 595       glob_hash->literal_list = _xdg_glob_list_append (glob_hash->literal_list, strdup (glob), strdup (mime_type), weight, case_sensitive);
 596       break;
 597     case XDG_GLOB_SIMPLE:
 598       glob_hash->simple_node = _xdg_glob_hash_insert_text (glob_hash->simple_node, glob + 1, mime_type, weight, case_sensitive);
 599       break;
 600     case XDG_GLOB_FULL:
 601       glob_hash->full_list = _xdg_glob_list_append (glob_hash->full_list, strdup (glob), strdup (mime_type), weight, case_sensitive);
 602       break;
 603     }
 604 }
 605
 606 void
 607 _xdg_glob_hash_dump (XdgGlobHash *glob_hash)
 608 {
 609   XdgGlobList *list;
 610   printf ("LITERAL STRINGS\n");
 611   if (!glob_hash || glob_hash->literal_list == NULL)
 612     {
 613       printf ("    None\n");
 614     }
 615   else
 616     {
 617       for (list = glob_hash->literal_list; list; list = list->next)
 618         printf ("    %s - %s %d\n", (char *)list->data, list->mime_type, list->weight);
 619     }
 620   printf ("\nSIMPLE GLOBS\n");
 621   if (!glob_hash || glob_hash->simple_node == NULL)
 622     {
 623       printf ("    None\n");
 624     }
 625   else
 626     {
 627       _xdg_glob_hash_node_dump (glob_hash->simple_node, 4);
 628     }
 629
 630   printf ("\nFULL GLOBS\n");
 631   if (!glob_hash || glob_hash->full_list == NULL)
 632     {
 633       printf ("    None\n");
 634     }
 635   else
 636     {
 637       for (list = glob_hash->full_list; list; list = list->next)
 638         printf ("    %s - %s %d\n", (char *)list->data, list->mime_type, list->weight);
 639     }
 640 }
 641
 642
 643 void
 644 _xdg_mime_glob_read_from_file (XdgGlobHash *glob_hash,
 645                                const char  *file_name,
 646                                int          version_two)
 647 {
 648   FILE *glob_file;
 649   char line[255];
 650   char *p;
 651
 652   glob_file = fopen (file_name, "r");
 653
 654   if (glob_file == NULL)
 655     return;
 656
 657   /* FIXME: Not UTF-8 safe.  Doesn't work if lines are greater than 255 chars.
 658    * Blah */
 659   while (fgets (line, 255, glob_file) != NULL)
 660     {
 661       char *colon;
 662       char *mimetype, *glob, *end;
 663       int weight;
 664       int case_sensitive;
 665
 666       if (line[0] == '#' || line[0] == 0)
 667         continue;
 668
 669       end = line + strlen(line) - 1;
 670       if (*end == '\n')
 671         *end = 0;
 672
 673       p = line;
 674       if (version_two)
 675         {
 676           colon = strchr (p, ':');
 677           if (colon == NULL)
 678             continue;
 679           *colon = 0;
 680           weight = atoi (p);
 681           p = colon + 1;
 682         }
 683       else
 684         weight = 50;
 685
 686       colon = strchr (p, ':');
 687       if (colon == NULL)
 688         continue;
 689       *colon = 0;
 690
 691       mimetype = p;
 692       p = colon + 1;
 693       glob = p;
 694       case_sensitive = FALSE;
 695
 696       colon = strchr (p, ':');
 697       if (version_two && colon != NULL)
 698         {
 699           char *flag;
 700
 701           /* We got flags */
 702           *colon = 0;
 703           p = colon + 1;
 704
 705           /* Flags end at next colon */
 706           colon = strchr (p, ':');
 707           if (colon != NULL)
 708             *colon = 0;
 709
 710           flag = strstr (p, "cs");
 711           if (flag != NULL &&
 712               /* Start or after comma */
 713               (flag == p ||
 714                flag[-1] == ',') &&
 715               /* ends with comma or end of string */
 716               (flag[2] == 0 ||
 717                flag[2] == ','))
 718             case_sensitive = TRUE;
 719         }
 720
 721       _xdg_glob_hash_append_glob (glob_hash, glob, mimetype, weight, case_sensitive);
 722     }
 723
 724   fclose (glob_file);
 725 }