util/url-scanner.c

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
   2 /*  GMime
   3  *  Copyright (C) 2000-2012 Jeffrey Stedfast
   4  *
   5  *  This library is free software; you can redistribute it and/or
   6  *  modify it under the terms of the GNU Lesser General Public License
   7  *  as published by the Free Software Foundation; either version 2.1
   8  *  of the License, or (at your option) any later version.
   9  *
  10  *  This library is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  *  Lesser General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU Lesser General Public
  16  *  License along with this library; if not, write to the Free
  17  *  Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  18  *  02110-1301, USA.
  19  */
  20
  21
  22 #ifdef HAVE_CONFIG_H
  23 #include <config.h>
  24 #endif
  25
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29
  30 #include "gtrie.h"
  31 #include "url-scanner.h"
  32
  33
  34 struct _UrlScanner {
  35         GPtrArray *patterns;
  36         GTrie *trie;
  37 };
  38
  39
  40 UrlScanner *
  41 url_scanner_new (void)
  42 {
  43         UrlScanner *scanner;
  44
  45         scanner = g_new (UrlScanner, 1);
  46         scanner->patterns = g_ptr_array_new ();
  47         scanner->trie = g_trie_new (TRUE);
  48
  49         return scanner;
  50 }
  51
  52
  53 void
  54 url_scanner_free (UrlScanner *scanner)
  55 {
  56         g_return_if_fail (scanner != NULL);
  57
  58         g_ptr_array_free (scanner->patterns, TRUE);
  59         g_trie_free (scanner->trie);
  60         g_free (scanner);
  61 }
  62
  63
  64 void
  65 url_scanner_add (UrlScanner *scanner, urlpattern_t *pattern)
  66 {
  67         g_return_if_fail (scanner != NULL);
  68
  69         g_trie_add (scanner->trie, pattern->pattern, scanner->patterns->len);
  70         g_ptr_array_add (scanner->patterns, pattern);
  71 }
  72
  73
  74 gboolean
  75 url_scanner_scan (UrlScanner *scanner, const char *in, size_t inlen, urlmatch_t *match)
  76 {
  77         const char *pos, *inend;
  78         urlpattern_t *pat;
  79         int pattern_id;
  80
  81         g_return_val_if_fail (scanner != NULL, FALSE);
  82         g_return_val_if_fail (in != NULL, FALSE);
  83
  84         if (!(pos = g_trie_search (scanner->trie, in, inlen, &pattern_id)))
  85                 return FALSE;
  86
  87         pat = g_ptr_array_index (scanner->patterns, pattern_id);
  88
  89         match->pattern = pat->pattern;
  90         match->prefix = pat->prefix;
  91
  92         inend = in + inlen;
  93         if (!pat->start (in, pos, inend, match))
  94                 return FALSE;
  95
  96         if (!pat->end (in, pos, inend, match))
  97                 return FALSE;
  98
  99         return TRUE;
 100 }
 101
 102
 103 static unsigned char url_scanner_table[256] = {
 104           1,  1,  1,  1,  1,  1,  1,  1,  1,  9,  9,  1,  1,  9,  1,  1,
 105           1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
 106          24,128,160,128,128,128,128,128,160,160,128,128,160,192,160,160,
 107          68, 68, 68, 68, 68, 68, 68, 68, 68, 68,160,160, 32,128, 32,128,
 108         160, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66,
 109          66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66,160,160,160,128,128,
 110         128, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66,
 111          66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66,128,128,128,128,  1,
 112           1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
 113           1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
 114           1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
 115           1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
 116           1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
 117           1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
 118           1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
 119           1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1
 120 };
 121
 122 enum {
 123         IS_CTRL         = (1 << 0),
 124         IS_ALPHA        = (1 << 1),
 125         IS_DIGIT        = (1 << 2),
 126         IS_LWSP         = (1 << 3),
 127         IS_SPACE        = (1 << 4),
 128         IS_SPECIAL      = (1 << 5),
 129         IS_DOMAIN       = (1 << 6),
 130         IS_URLSAFE      = (1 << 7),
 131 };
 132
 133 #define is_ctrl(x) ((url_scanner_table[(unsigned char)(x)] & IS_CTRL) != 0)
 134 #define is_lwsp(x) ((url_scanner_table[(unsigned char)(x)] & IS_LWSP) != 0)
 135 #define is_atom(x) ((url_scanner_table[(unsigned char)(x)] & (IS_SPECIAL|IS_SPACE|IS_CTRL)) == 0)
 136 #define is_alpha(x) ((url_scanner_table[(unsigned char)(x)] & IS_ALPHA) != 0)
 137 #define is_digit(x) ((url_scanner_table[(unsigned char)(x)] & IS_DIGIT) != 0)
 138 #define is_domain(x) ((url_scanner_table[(unsigned char)(x)] & IS_DOMAIN) != 0)
 139 #define is_urlsafe(x) ((url_scanner_table[(unsigned char)(x)] & (IS_ALPHA|IS_DIGIT|IS_URLSAFE)) != 0)
 140
 141 static struct {
 142         char open;
 143         char close;
 144 } url_braces[] = {
 145         { '(', ')' },
 146         { '{', '}' },
 147         { '[', ']' },
 148         { '<', '>' },
 149         { '|', '|' },
 150 };
 151
 152 static gboolean
 153 is_open_brace (char c)
 154 {
 155         int i;
 156
 157         for (i = 0; i < G_N_ELEMENTS (url_braces); i++) {
 158                 if (c == url_braces[i].open)
 159                         return TRUE;
 160         }
 161
 162         return FALSE;
 163 }
 164
 165 static char
 166 url_stop_at_brace (const char *in, size_t so)
 167 {
 168         int i;
 169
 170         if (so > 0) {
 171                 for (i = 0; i < 4; i++) {
 172                         if (in[so - 1] == url_braces[i].open)
 173                                 return url_braces[i].close;
 174                 }
 175         }
 176
 177         return '\0';
 178 }
 179
 180
 181 gboolean
 182 url_addrspec_start (const char *in, const char *pos, const char *inend, urlmatch_t *match)
 183 {
 184         register const char *inptr = pos;
 185
 186         g_assert (*inptr == '@');
 187
 188         if (inptr == in)
 189                 return FALSE;
 190
 191         inptr--;
 192
 193         while (inptr > in) {
 194                 if (is_atom (*inptr))
 195                         inptr--;
 196                 else
 197                         break;
 198
 199                 while (inptr > in && is_atom (*inptr))
 200                         inptr--;
 201
 202                 if (inptr > in && *inptr == '.')
 203                         inptr--;
 204         }
 205
 206         if (!is_atom (*inptr) || is_open_brace (*inptr))
 207                 inptr++;
 208
 209         if (inptr == pos)
 210                 return FALSE;
 211
 212         match->um_so = (inptr - in);
 213
 214         return TRUE;
 215 }
 216
 217 gboolean
 218 url_addrspec_end (const char *in, const char *pos, const char *inend, urlmatch_t *match)
 219 {
 220         const char *inptr = pos;
 221         int parts = 0, digits;
 222         gboolean got_dot = FALSE;
 223
 224         g_assert (*inptr == '@');
 225
 226         inptr++;
 227
 228         if (*inptr == '[') {
 229                 /* domain literal */
 230                 do {
 231                         inptr++;
 232
 233                         digits = 0;
 234                         while (inptr < inend && is_digit (*inptr) && digits < 3) {
 235                                 inptr++;
 236                                 digits++;
 237                         }
 238
 239                         parts++;
 240
 241                         if (*inptr != '.' && parts != 4)
 242                                 return FALSE;
 243                 } while (parts < 4);
 244
 245                 if (inptr < inend && *inptr == ']')
 246                         inptr++;
 247                 else
 248                         return FALSE;
 249
 250                 got_dot = TRUE;
 251         } else {
 252                 while (inptr < inend) {
 253                         if (is_domain (*inptr))
 254                                 inptr++;
 255                         else
 256                                 break;
 257
 258                         while (inptr < inend && is_domain (*inptr))
 259                                 inptr++;
 260
 261                         if (inptr < inend && *inptr == '.' && is_domain (inptr[1])) {
 262                                 if (*inptr == '.')
 263                                         got_dot = TRUE;
 264                                 inptr++;
 265                         }
 266                 }
 267         }
 268
 269         if (inptr == pos + 1 || !got_dot)
 270                 return FALSE;
 271
 272         match->um_eo = (inptr - in);
 273
 274         return TRUE;
 275 }
 276
 277
 278 gboolean
 279 url_file_start (const char *in, const char *pos, const char *inend, urlmatch_t *match)
 280 {
 281         match->um_so = (pos - in);
 282
 283         return TRUE;
 284 }
 285
 286 gboolean
 287 url_file_end (const char *in, const char *pos, const char *inend, urlmatch_t *match)
 288 {
 289         register const char *inptr = pos;
 290         char close_brace;
 291
 292         inptr += strlen (match->pattern);
 293
 294         if (*inptr == '/')
 295                 inptr++;
 296
 297         close_brace = url_stop_at_brace (in, match->um_so);
 298
 299         while (inptr < inend && is_urlsafe (*inptr) && *inptr != close_brace)
 300                 inptr++;
 301
 302         if (inptr == pos)
 303                 return FALSE;
 304
 305         match->um_eo = (inptr - in);
 306
 307         return TRUE;
 308 }
 309
 310 gboolean
 311 url_web_start (const char *in, const char *pos, const char *inend, urlmatch_t *match)
 312 {
 313         match->um_so = (pos - in);
 314
 315         return TRUE;
 316 }
 317
 318 gboolean
 319 url_web_end (const char *in, const char *pos, const char *inend, urlmatch_t *match)
 320 {
 321         register const char *inptr = pos;
 322         gboolean openbracket = FALSE;
 323         gboolean passwd = FALSE;
 324         const char *save;
 325         char close_brace;
 326         int port, val, n;
 327         char *end;
 328
 329         inptr += strlen (match->pattern);
 330
 331         close_brace = url_stop_at_brace (in, match->um_so);
 332
 333         /* find the end of the domain */
 334         if (is_digit (*inptr)) {
 335                 goto ip_literal2;
 336         } else if (is_atom (*inptr)) {
 337                 /* might be a domain or user@domain */
 338                 save = inptr;
 339                 while (inptr < inend) {
 340                         if (!is_atom (*inptr))
 341                                 break;
 342
 343                         inptr++;
 344
 345                         while (inptr < inend && is_atom (*inptr))
 346                                 inptr++;
 347
 348                         if ((inptr + 1) < inend && *inptr == '.' && is_atom (inptr[1]))
 349                                 inptr++;
 350                 }
 351
 352                 if (*inptr != '@')
 353                         inptr = save;
 354                 else
 355                         inptr++;
 356
 357                 if (*inptr == '[') {
 358                         /* IPv6 (or possibly IPv4) address literal */
 359                         goto ip_literal;
 360                 }
 361
 362                 if (is_domain (*inptr)) {
 363                         /* domain name or IPv4 address */
 364                         goto domain;
 365                 }
 366         } else if (*inptr == '[') {
 367         ip_literal:
 368                 openbracket = TRUE;
 369                 inptr++;
 370
 371                 if (is_digit (*inptr)) {
 372                 ip_literal2:
 373                         /* could be IPv4 or IPv6 */
 374                         if ((val = strtol (inptr, &end, 10)) < 0)
 375                                 return FALSE;
 376                 } else if ((*inptr >= 'A' && *inptr <= 'F') || (*inptr >= 'a' && *inptr <= 'f')) {
 377                         /* IPv6 address literals are in hex */
 378                         if ((val = strtol (inptr, &end, 16)) < 0 || *end != ':')
 379                                 return FALSE;
 380                 } else if (*inptr == ':') {
 381                         /* IPv6 can start with a ':' */
 382                         end = (char *) inptr;
 383                         val = 256; /* invalid value */
 384                 } else {
 385                         return FALSE;
 386                 }
 387
 388                 switch (*end) {
 389                 case '.': /* IPv4 address literal */
 390                         n = 1;
 391                         do {
 392                                 if (val > 255 || *end != '.')
 393                                         return FALSE;
 394
 395                                 inptr = end + 1;
 396                                 if ((val = strtol (inptr, &end, 10)) < 0)
 397                                         return FALSE;
 398
 399                                 n++;
 400                         } while (n < 4);
 401
 402                         if (val > 255 || n < 4 || (openbracket && *end != ']'))
 403                                 return FALSE;
 404
 405                         inptr = end + 1;
 406                         break;
 407                 case ':': /* IPv6 address literal */
 408                         if (!openbracket)
 409                                 return FALSE;
 410
 411                         do {
 412                                 if (end[1] != ':') {
 413                                         inptr = end + 1;
 414                                         if ((val = strtol (inptr, &end, 16)) < 0)
 415                                                 return FALSE;
 416                                 } else {
 417                                         inptr = end;
 418                                         end++;
 419                                 }
 420                         } while (end > inptr && *end == ':');
 421
 422                         if (*end != ']')
 423                                 return FALSE;
 424
 425                         inptr = end + 1;
 426                         break;
 427                 default:
 428                         return FALSE;
 429                 }
 430         } else if (is_domain (*inptr)) {
 431         domain:
 432                 while (inptr < inend) {
 433                         if (!is_domain (*inptr))
 434                                 break;
 435
 436                         inptr++;
 437
 438                         while (inptr < inend && is_domain (*inptr))
 439                                 inptr++;
 440
 441                         if ((inptr + 1) < inend && *inptr == '.' && (is_domain (inptr[1]) || inptr[1] == '/'))
 442                                 inptr++;
 443                 }
 444         } else {
 445                 return FALSE;
 446         }
 447
 448         if (inptr < inend) {
 449                 switch (*inptr) {
 450                 case ':': /* we either have a port or a password */
 451                         inptr++;
 452
 453                         if (is_digit (*inptr) || passwd) {
 454                                 port = (*inptr++ - '0');
 455
 456                                 while (inptr < inend && is_digit (*inptr) && port < 65536)
 457                                         port = (port * 10) + (*inptr++ - '0');
 458
 459                                 if (!passwd && (port >= 65536 || *inptr == '@')) {
 460                                         if (inptr < inend) {
 461                                                 /* this must be a password? */
 462                                                 goto passwd;
 463                                         }
 464
 465                                         inptr--;
 466                                 }
 467                         } else {
 468                         passwd:
 469                                 passwd = TRUE;
 470                                 save = inptr;
 471
 472                                 while (inptr < inend && is_atom (*inptr))
 473                                         inptr++;
 474
 475                                 if ((inptr + 2) < inend) {
 476                                         if (*inptr == '@') {
 477                                                 inptr++;
 478                                                 if (is_domain (*inptr))
 479                                                         goto domain;
 480                                         }
 481
 482                                         return FALSE;
 483                                 }
 484                         }
 485
 486                         if (inptr >= inend || *inptr != '/')
 487                                 break;
 488
 489                         /* we have a '/' so there could be a path - fall through */
 490                 case '/': /* we've detected a path component to our url */
 491                         inptr++;
 492
 493                         while (inptr < inend && is_urlsafe (*inptr) && *inptr != close_brace)
 494                                 inptr++;
 495
 496                         break;
 497                 default:
 498                         break;
 499                 }
 500         }
 501
 502         /* urls are extremely unlikely to end with any
 503          * punctuation, so strip any trailing
 504          * punctuation off. Also strip off any closing
 505          * braces or quotes. */
 506         while (inptr > pos && strchr (",.:;?!-|)}]'\"", inptr[-1]))
 507                 inptr--;
 508
 509         match->um_eo = (inptr - in);
 510
 511         return TRUE;
 512 }
 513
 514
 515 #ifdef BUILD_TABLE
 516
 517 #include <stdio.h>
 518
 519 /* got these from rfc1738 */
 520 #define CHARS_LWSP " \t\n\r"               /* linear whitespace chars */
 521 #define CHARS_SPECIAL "()<>@,;:\\\".[]"
 522
 523 /* got these from rfc1738 */
 524 #define CHARS_URLSAFE "$-_.+!*'(),{}|\\^~[]`#%\";/?:@&="
 525
 526
 527 static void
 528 table_init_bits (unsigned int mask, const unsigned char *vals)
 529 {
 530         int i;
 531
 532         for (i = 0; vals[i] != '\0'; i++)
 533                 url_scanner_table[vals[i]] |= mask;
 534 }
 535
 536 static void
 537 url_scanner_table_init (void)
 538 {
 539         int i;
 540
 541         for (i = 0; i < 256; i++) {
 542                 url_scanner_table[i] = 0;
 543                 if (i < 32)
 544                         url_scanner_table[i] |= IS_CTRL;
 545                 if ((i >= '0' && i <= '9'))
 546                         url_scanner_table[i] |= IS_DIGIT | IS_DOMAIN;
 547                 if ((i >= 'a' && i <= 'z') || (i >= 'A' && i <= 'Z'))
 548                         url_scanner_table[i] |= IS_ALPHA | IS_DOMAIN;
 549                 if (i >= 127)
 550                         url_scanner_table[i] |= IS_CTRL;
 551         }
 552
 553         url_scanner_table[' '] |= IS_SPACE;
 554         url_scanner_table['-'] |= IS_DOMAIN;
 555
 556         /* not defined to be special in rfc0822, but when scanning
 557            backwards to find the beginning of the email address we do
 558            not want to include this char if we come accross it - so
 559            this is kind of a hack, but it's ok */
 560         url_scanner_table['/'] |= IS_SPECIAL;
 561
 562         table_init_bits (IS_LWSP, CHARS_LWSP);
 563         table_init_bits (IS_SPECIAL, CHARS_SPECIAL);
 564         table_init_bits (IS_URLSAFE, CHARS_URLSAFE);
 565 }
 566
 567 int main (int argc, char **argv)
 568 {
 569         int i;
 570
 571         url_scanner_table_init ();
 572
 573         printf ("static unsigned char url_scanner_table[256] = {");
 574         for (i = 0; i < 256; i++) {
 575                 printf ("%s%3d%s", (i % 16) ? "" : "\n\t",
 576                         url_scanner_table[i], i != 255 ? "," : "\n");
 577         }
 578         printf ("};\n\n");
 579
 580         return 0;
 581 }
 582
 583 #endif /* BUILD_TABLE */