libiri/parse.c

   1 /*
   2  * libiri: An IRI/URI/URL parsing library
   3  * @(#) $Id$
   4  */
   5
   6 /*
   7  * Copyright (c) 2005, 2008 Mo McRoberts.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  * notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  * notice, this list of conditions and the following disclaimer in the
  16  * documentation and/or other materials provided with the distribution.
  17  * 3. The names of the author(s) of this software may not be used to endorse
  18  * or promote products derived from this software without specific prior
  19  * written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
  22  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
  23  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
  24  * AUTHORS OF THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  25  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  26  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  27  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  28  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  29  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  30  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  */
  32
  33 #ifdef HAVE_CONFIG_H
  34 # include "config.h"
  35 #endif
  36
  37 #include <stdio.h>
  38
  39 #include "p_libiri.h"
  40
  41 #undef ALIGNMENT
  42 #define ALIGNMENT 8
  43 #undef ALIGN
  44 #define _ALIGN(x) ((((x)+(ALIGNMENT-1))&~(ALIGNMENT-1)))
  45 #define ALIGN(x) (char *) _ALIGN((size_t) x)
  46
  47 static inline int
  48 iri__hexnibble(char c)
  49 {
  50         if(c >= '0' && c <= '9')
  51         {
  52                 return c - '0';
  53         }
  54         if(c >= 'A' && c <= 'F')
  55         {
  56                 return c - 'A' + 10;
  57         }
  58         if(c >= 'a' && c <= 'f')
  59         {
  60                 return c - 'a' + 10;
  61         }
  62         return 0;
  63 }
  64
  65 static inline const char *
  66 iri__copychar(char **dest, const char *src)
  67 {
  68         **dest = *src;
  69         (*dest)++;
  70         src++;
  71         return src;
  72 }
  73
  74 /* TODO: Punycode decoding for the host part */
  75 static inline const char *
  76 iri__copychar_decode(char **dest, const char *src, int convert_space)
  77 {
  78         unsigned char *p = (unsigned char *) (*dest);
  79
  80         if(1 == convert_space && '+' == *src)
  81         {
  82                 **dest = ' ';
  83         }
  84         else if('%' == *src)
  85         {
  86                 if(0 == isxdigit(src[1]) || 0 == isxdigit(src[2]))
  87                 {
  88                         /* TODO: Deal with %u<nnnn> non-standard encoding - be liberal in
  89                          * what you accept, etc.
  90                          */
  91                         **dest = '%';
  92                 }
  93                 else
  94                 {
  95                         *p = (iri__hexnibble(src[1]) << 4) | iri__hexnibble(src[2]);
  96                         src += 2;
  97                 }
  98         }
  99         else
 100         {
 101                 **dest = *src;
 102         }
 103         src++;
 104         (*dest)++;
 105         return src;
 106 }
 107
 108 static inline char *
 109 iri__allocbuf(const char *src, size_t *len)
 110 {
 111         size_t sc;
 112         const char *p, *c;
 113 /*
 114         Internal format of IRI structure is very hard to understand at first.
 115         The buffer is used to store character strings with every parsed part of
 116         IRI, like host, user, auth, path etc. Start of every character string is
 117         ALIGNED to ALIGNMENT value and finished with NULL byte.
 118         Above that, the buffer is used to keep variable size array of parsed
 119         scheme parts. It consist of the array of addresses pointing to starts
 120         of scheme parts which are kept as all other characters strings, so are
 121         aligned to ALIGMENT and ended with NULL byte.
 122         This function calculates approximation of buffer size to store all the
 123         data of parser IRI.
 124
 125         Fully filled buffer with scheme parts looks as follows:
 126         0. start of the buffer
 127         1. aligned start of the scheme part with added NULL byte
 128         2. aligned start of the user part with added NULL byte
 129         3. aligned start of the password part with added NULL byte
 130         4. aligned start of the array of size schemes_number+1 of pointers that point
 131            to consecutive scheme part character strings (last one is NULL)
 132            schemes_number is a number of scheme tokens delimited with + sign in
 133            scheme part
 134         5. schems_number of characters strings of scheme parts each of which
 135            aligned and finished with NULL byte.
 136         6. aligned start of the host part with added NULL byte
 137         7. aligned start of the path part with added NULL byte
 138         8. aligned start of the query part with added NULL byte
 139         9. aligned start of the anchor part with added NULL byte
 140
 141         There can be indentified 4 kinds of characters in IRI:
 142         - characters which are copied one to one (i.e. letters)
 143         - characters which are removed (special characters like comma in scheme)
 144         - characters which are replaced with other characers where buffer grows
 145           this only happens with scheme part
 146         - characters which are replaced with other characers where buffer decreases
 147
 148         Alighning a pointer in worst case will advance a buffer pointers
 149         ALIGNMENT-1 bytes
 150
 151         Knowing all that we can count an approximation of buffer size which can
 152         be trusted that whole parsed IRI content will fit in.
 153 */
 154
 155 /* first approximation - all characers will have to be stored in buffer */
 156         *len = strlen(src);
 157
 158 /* second approximation - IRI has all possible parts which have to be
 159  * aligned to ALIGNMENT and have NULL byte an the end. There are 7 different
 160  * parts like that */
 161         *len += 7 * (ALIGNMENT-1 + 1);
 162
 163 /* third approximation - we have to make a room for scheme parts array.
 164  * Because the array has an aligned array of n + 1 pointers and n
 165  * characters strings aligned and NULL byte terminated.
 166  */
 167         if(NULL != (c = strchr(src, ':')))
 168         {
 169                 sc = 1;
 170                 for(p = src; p < c; p++)
 171                 {
 172                 if(*p == '+')
 173                         {
 174                                 sc++;
 175                         }
 176                 }
 177                 /* fourth approximation - all characters of scheme part will be stored
 178                  * in scheme parts tokens */
 179                 *len += (c - src);
 180
 181                 /* fifth approximation - Ensure we can align each element on an
 182                  * ALIGNMENT byte boundary and append NULL byte */
 183                 *len += sc * (ALIGNMENT-1 + 1);
 184
 185                 /* sixth approximation - Ensure we have a room for aligned array
 186                  * indexes */
 187                 *len += ALIGNMENT-1 + (sc + 1) * (sizeof(char*)/sizeof(char));
 188     }
 189         return (char *) calloc(1, *len);
 190 }
 191
 192 iri_t *
 193 iri_parse(const char *src)
 194 {
 195         iri_t *p;
 196         char *bufstart, *endp, *bufp, **sl;
 197     const char *at, *colon, *slash, *t, *slash3rd;
 198         size_t buflen, sc, cp;
 199
 200         if(NULL == (p = (iri_t *) calloc(1, sizeof(iri_t))))
 201         {
 202                 return NULL;
 203         }
 204         if(NULL == (bufstart = iri__allocbuf(src, &buflen)))
 205         {
 206                 free(p);
 207                 return NULL;
 208         }
 209         p->base = bufp = bufstart;
 210         p->nbytes = buflen;
 211         at = strchr(src, '@');
 212         slash = strchr(src, '/');
 213         colon = strchr(src, ':');
 214         if(slash && colon && slash < colon)
 215         {
 216                 /* We can disregard the colon if a slash appears before it */
 217                 colon = NULL;
 218         }
 219     // "@" is valid character in hierarchical part of IRI
 220     if(slash && colon && (colon[1] != '/' || colon[2] != '/'))
 221     {
 222         //if scheme not suffixed with ://, there is not autority
 223         //therefore autority(and user within) is not set
 224         at = NULL;
 225     }
 226     else if(at && slash && slash[1] && slash[2])
 227     {
 228         slash3rd = strchr(slash + 2, '/');
 229         //here we know scheme suffix is "://" so autority can exist
 230         //3rd slash should match start of hierarchical part if exists
 231         //@ after that is valid character
 232         if(slash3rd && slash3rd < at)
 233         {
 234             at = NULL;
 235         }
 236     }
 237         if(colon && !at)
 238         {
 239                 /* Definitely a scheme */
 240                 bufp = ALIGN(bufp);
 241                 p->iri.scheme = bufp;
 242                 while(*src && *src != ':')
 243                 {
 244                         src = iri__copychar_decode(&bufp, src, 0);
 245                 }
 246                 *bufp = 0;
 247                 bufp++;
 248                 src++;
 249                 /* src[0-1] SHOULD == '/' */
 250                 if(src[0] == '/') src++;
 251                 if(src[0] == '/') src++;
 252         }
 253         else if(colon && at && colon < at)
 254         {
 255                 fprintf(stderr, "Colon occurs before at\n");
 256                 /* This could be scheme://user[;auth][:password]@host or [scheme:]user[;auth][:password]@host (urgh) */
 257                 if(colon[1] == '/' && colon[2] == '/' && colon[3] != '/')
 258                 {
 259                         bufp = ALIGN(bufp);
 260                         p->iri.scheme = bufp;
 261                         while(*src && *src != ':')
 262                         {
 263                                 src = iri__copychar_decode(&bufp, src, 0);
 264                         }
 265                         *bufp = 0;
 266                         bufp++;
 267                         src++;
 268                         /* src[0-1] SHOULD == '/' */
 269                         for(; *src == '/'; src++);
 270                         bufp = ALIGN(bufp);
 271                         p->iri.user = bufp;
 272                         fprintf(stderr, "Found user\n");
 273                 }
 274                 else
 275                 {
 276                         fprintf(stderr, "Matched scheme\n");
 277                         bufp = ALIGN(bufp);
 278                         p->iri.scheme = bufp;
 279                 }
 280                 while(*src && *src != ':' && *src != '@' && *src != ';')
 281                 {
 282                         src = iri__copychar_decode(&bufp, src, 0);
 283                 }
 284                 *bufp = 0;
 285                 bufp++;
 286                 if(*src == ';')
 287                 {
 288                         /* Following authentication parameters */
 289                         src++;
 290                         bufp = ALIGN(bufp);
 291                         p->iri.auth = bufp;
 292                         while(*src && *src != ':' && *src != '@')
 293                         {
 294                                 /* Don't decode, so it can be extracted properly */
 295                                 src = iri__copychar(&bufp, src);
 296                         }
 297                         *bufp = 0;
 298                         bufp++;
 299                 }
 300                 if(*src == ':')
 301                 {
 302                         /* Following password data */
 303                         src++;
 304                         bufp = ALIGN(bufp);
 305                         p->iri.password = bufp;
 306                         while(*src && *src != ':' && *src != '@')
 307                         {
 308                                 src = iri__copychar_decode(&bufp, src, 0);
 309                         }
 310                         *bufp = 0;
 311                         bufp++;
 312                         if(*src == ':')
 313                         {
 314                                 src++;
 315                                 /* It was actually scheme:user:auth@host */
 316                                 p->iri.user = p->iri.auth;
 317                                 bufp = ALIGN(bufp);
 318                                 p->iri.password = bufp;
 319                                 while(*src && *src != '@')
 320                                 {
 321                                         src = iri__copychar_decode(&bufp, src, 0);
 322                                 }
 323                                 *bufp = 0;
 324                                 bufp++;
 325                         }
 326                 }
 327                 if(!*src)
 328                 {
 329                         /* No host part */
 330                         return p;
 331                 }
 332                 if(*src == '@')
 333                 {
 334                         src++;
 335                 }
 336         }
 337         else if(at)
 338         {
 339                 /* user[;auth]@host[/path...] */
 340                 bufp = ALIGN(bufp);
 341                 p->iri.user = bufp;
 342                 while(*src != '@' && *src != ';')
 343                 {
 344                         src = iri__copychar_decode(&bufp, src, 0);
 345                 }
 346                 *bufp = 0;
 347                 bufp++;
 348                 if(*src == ';')
 349                 {
 350                         src++;
 351                         bufp = ALIGN(bufp);
 352                         p->iri.auth = bufp;
 353                         while(*src && *src != '@')
 354                         {
 355                                 /* Don't decode, so it can be extracted properly */
 356                                 src = iri__copychar(&bufp, src);
 357                         }
 358                         *bufp = 0;
 359                         bufp++;
 360                 }
 361                 else
 362                 {
 363                         src++;
 364                 }
 365         }
 366         if(NULL != p->iri.scheme)
 367         {
 368                 sc = 1;
 369                 for(t = p->iri.scheme; *t; t++)
 370                 {
 371                         if('+' == *t)
 372                         {
 373                                 sc++;
 374                         }
 375                 }
 376                 bufp = ALIGN(bufp);
 377                 sl = (char **) (void *) bufp;
 378                 bufp += (sc + 1) * sizeof(char *);
 379                 sc = 0;
 380                 cp = 0;
 381                 bufp = ALIGN(bufp);
 382                 sl[0] = bufp;
 383                 for(t = p->iri.scheme; *t; t++)
 384                 {
 385                         if('+' == *t)
 386                         {
 387                                 if(sl[sc][0])
 388                                 {
 389                                         sl[sc][cp] = 0;
 390                                         bufp++;
 391                                         sc++;
 392                                         bufp = ALIGN(bufp);
 393                                         sl[sc] = bufp;
 394                                         cp = 0;
 395                                 }
 396                         }
 397                         else
 398                         {
 399                                 sl[sc][cp] = *t;
 400                                 bufp++;
 401                                 cp++;
 402                         }
 403                 }
 404                 if(sl[sc][0])
 405                 {
 406                         sl[sc][cp] = 0;
 407                         sc++;
 408                         bufp++;
 409                 }
 410                 sl[sc] = NULL;
 411                 p->iri.schemelist = (const char **) sl;
 412                 p->iri.nschemes = sc;
 413                 bufp++;
 414         }
 415         bufp = ALIGN(bufp);
 416         p->iri.host = bufp;
 417         while(*src && *src != ':' && *src != '/' && *src != '?' && *src != '#')
 418         {
 419                 src = iri__copychar_decode(&bufp, src, 0);
 420         }
 421         *bufp = 0;
 422         bufp++;
 423         if(*src == ':')
 424         {
 425                 /* Port part */
 426                 src++;
 427                 endp = (char *) src;
 428                 p->iri.port = strtol(src, &endp, 10);
 429                 src = endp;
 430         }
 431         if(*src == '/')
 432         {
 433                 bufp = ALIGN(bufp);
 434                 p->iri.path = bufp;
 435                 while(*src && *src != '?' && *src != '#')
 436                 {
 437                         src = iri__copychar_decode(&bufp, src, 0);
 438                 }
 439                 *bufp = 0;
 440                 bufp++;
 441         }
 442         if(*src == '?')
 443         {
 444                 bufp = ALIGN(bufp);
 445                 p->iri.query = bufp;
 446                 src++;
 447                 while(*src && *src != '#')
 448                 {
 449                         /* Don't actually decode the query itself, otherwise it
 450                          * can't be reliably split */
 451                         src = iri__copychar(&bufp, src);
 452                 }
 453                 *bufp = 0;
 454                 bufp++;
 455         }
 456         if(*src == '#')
 457         {
 458                 bufp = ALIGN(bufp);
 459                 p->iri.anchor = bufp;
 460                 while(*src)
 461                 {
 462                         src = iri__copychar_decode(&bufp, src, 0);
 463                 }
 464                 *bufp = 0;
 465                 bufp++;
 466         }
 467         if(*src)
 468         {
 469                 /* Still stuff left? It must be a path... of sorts */
 470                 bufp = ALIGN(bufp);
 471                 p->iri.path = bufp;
 472                 while(*src && *src != '?' && *src != '#')
 473                 {
 474                         src = iri__copychar_decode(&bufp, src, 0);
 475                 }
 476                 *bufp = 0;
 477                 bufp++;
 478         }
 479         return p;
 480 }