sys/src/libhtml/utils.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <draw.h>
   4 #include <html.h>
   5 #include "impl.h"
   6
   7 Rune* whitespace = L" \t\n\r";
   8 Rune* notwhitespace = L"^ \t\n\r";
   9
  10 // All lists start out like List structure.
  11 // List itself can be used as list of int.
  12 int
  13 _listlen(List* l)
  14 {
  15         int n = 0;
  16
  17         while(l != nil) {
  18                 l = l->next;
  19                 n++;
  20         }
  21         return n;
  22 }
  23
  24 // Cons
  25 List*
  26 _newlist(int val, List* rest)
  27 {
  28         List* ans;
  29
  30         ans = (List*)emalloc(sizeof(List));
  31         ans->val = val;
  32         ans->next = rest;
  33         return ans;
  34 }
  35
  36 // Reverse a list in place
  37 List*
  38 _revlist(List* l)
  39 {
  40         List* newl;
  41         List* nextl;
  42
  43         newl = nil;
  44         while(l != nil) {
  45                 nextl = l->next;
  46                 l->next = newl;
  47                 newl = l;
  48                 l = nextl;
  49         }
  50         return newl;
  51 }
  52
  53 // The next few routines take a "character class" as argument.
  54 //    e.g., "a-zA-Z", or "^ \t\n"
  55 // (ranges indicated by - except in first position;
  56 //  ^ is first position means "not in" the following class)
  57
  58 // Splitl splits s[0:n] just before first character of class cl.
  59 // Answers go in (p1, n1) and (p2, n2).
  60 // If no split, the whole thing goes in the first component.
  61 // Note: answers contain pointers into original string.
  62 void
  63 _splitl(Rune* s, int n, Rune* cl, Rune** p1, int* n1, Rune** p2, int* n2)
  64 {
  65         Rune* p;
  66
  67         p = _Strnclass(s, cl, n);
  68         *p1 = s;
  69         if(p == nil) {
  70                 *n1 = n;
  71                 *p2 = nil;
  72                 *n2 = 0;
  73         }
  74         else {
  75                 *p2 = p;
  76                 *n1 = p-s;
  77                 *n2 = n-*n1;
  78         }
  79 }
  80
  81 // Splitr splits s[0:n] just after last character of class cl.
  82 // Answers go in (p1, n1) and (p2, n2).
  83 // If no split, the whole thing goes in the last component.
  84 // Note: answers contain pointers into original string.
  85 void
  86 _splitr(Rune* s, int n, Rune* cl, Rune** p1, int* n1, Rune** p2, int* n2)
  87 {
  88         Rune* p;
  89
  90         p = _Strnrclass(s, cl, n);
  91         if(p == nil) {
  92                 *p1 = nil;
  93                 *n1 = 0;
  94                 *p2 = s;
  95                 *n2 = n;
  96         }
  97         else {
  98                 *p1 = s;
  99                 *p2 = p+1;
 100                 *n1 = *p2-s;
 101                 *n2 = n-*n1;
 102         }
 103 }
 104
 105 // Splitall splits s[0:n] into parts that are separated by characters from class cl.
 106 // Each part will have nonzero length.
 107 // At most alen parts are found, and pointers to their starts go into
 108 // the strarr array, while their lengths go into the lenarr array.
 109 // The return value is the number of parts found.
 110 int
 111 _splitall(Rune* s, int n, Rune* cl, Rune** strarr, int* lenarr, int alen)
 112 {
 113         int i;
 114         Rune* p;
 115         Rune* q;
 116         Rune* slast;
 117
 118         if(s == nil || n == 0)
 119                 return 0;
 120         i = 0;
 121         p = s;
 122         slast = s+n;
 123         while(p < slast && i < alen) {
 124                 while(p < slast && _inclass(*p, cl))
 125                         p++;
 126                 if(p == slast)
 127                         break;
 128                 q = _Strnclass(p, cl, slast-p);
 129                 if(q == nil)
 130                         q = slast;
 131                 assert(q > p && q <= slast);
 132                 strarr[i] = p;
 133                 lenarr[i] = q-p;
 134                 i++;
 135                 p = q;
 136         }
 137         return i;
 138 }
 139
 140 // Find part of s that excludes leading and trailing whitespace,
 141 // and return that part in *pans (and its length in *panslen).
 142 void
 143 _trimwhite(Rune* s, int n, Rune** pans, int* panslen)
 144 {
 145         Rune* p;
 146         Rune* q;
 147
 148         p = nil;
 149         if(n > 0) {
 150                 p = _Strnclass(s, notwhitespace, n);
 151                 if(p != nil) {
 152                         q = _Strnrclass(s, notwhitespace, n);
 153                         assert(q != nil);
 154                         n = q+1-p;
 155                 }
 156         }
 157         *pans = p;
 158         *panslen = n;
 159 }
 160
 161 // _Strclass returns a pointer to the first element of s that is
 162 // a member of class cl, nil if none.
 163 Rune*
 164 _Strclass(Rune* s, Rune* cl)
 165 {
 166         Rune* p;
 167
 168         for(p = s; *p != 0; p++)
 169                 if(_inclass(*p, cl))
 170                         return p;
 171         return nil;
 172 }
 173
 174 // _Strnclass returns a pointer to the first element of s[0:n] that is
 175 // a member of class cl, nil if none.
 176 Rune*
 177 _Strnclass(Rune* s, Rune* cl, int n)
 178 {
 179         Rune* p;
 180
 181         for(p = s; n-- && *p != 0; p++)
 182                 if(_inclass(*p, cl))
 183                         return p;
 184         return nil;
 185 }
 186
 187 // _Strrclass returns a pointer to the last element of s that is
 188 // a member of class cl, nil if none
 189 Rune*
 190 _Strrclass(Rune* s, Rune* cl)
 191 {
 192         Rune* p;
 193
 194         if(s == nil || *s == 0)
 195                 return nil;
 196         p = s + runestrlen(s) - 1;
 197         while(p >= s) {
 198                 if(_inclass(*p, cl))
 199                         return p;
 200                 p--;
 201         };
 202         return nil;
 203 }
 204
 205 // _Strnrclass returns a pointer to the last element of s[0:n] that is
 206 // a member of class cl, nil if none
 207 Rune*
 208 _Strnrclass(Rune* s, Rune* cl, int n)
 209 {
 210         Rune* p;
 211
 212         if(s == nil || *s == 0 || n == 0)
 213                 return nil;
 214         p = s + n - 1;
 215         while(p >= s) {
 216                 if(_inclass(*p, cl))
 217                         return p;
 218                 p--;
 219         };
 220         return nil;
 221 }
 222
 223 // Is c in the class cl?
 224 int
 225 _inclass(Rune c, Rune* cl)
 226 {
 227         int     n;
 228         int     ans;
 229         int     negate;
 230         int     i;
 231
 232         n = _Strlen(cl);
 233         if(n == 0)
 234                 return 0;
 235         ans = 0;
 236         negate = 0;
 237         if(cl[0] == '^') {
 238                 negate = 1;
 239                 cl++;
 240                 n--;
 241         }
 242         for(i = 0; i < n; i++) {
 243                 if(cl[i] == '-' && i > 0 && i < n - 1) {
 244                         if(c >= cl[i - 1] && c <= cl[i + 1]) {
 245                                 ans = 1;
 246                                 break;
 247                         }
 248                         i++;
 249                 }
 250                 else if(c == cl[i]) {
 251                         ans = 1;
 252                         break;
 253                 }
 254         }
 255         if(negate)
 256                 ans = !ans;
 257         return ans;
 258 }
 259
 260 // Is pre a prefix of s?
 261 int
 262 _prefix(Rune* pre, Rune* s)
 263 {
 264         int     ns;
 265         int     n;
 266         int     k;
 267
 268         ns = _Strlen(s);
 269         n = _Strlen(pre);
 270         if(ns < n)
 271                 return 0;
 272         for(k = 0; k < n; k++) {
 273                 if(pre[k] != s[k])
 274                         return 0;
 275         }
 276         return 1;
 277 }
 278
 279 // Number of runes in (null-terminated) s
 280 int
 281 _Strlen(Rune* s)
 282 {
 283         if(s == nil)
 284                 return 0;
 285         return runestrlen(s);
 286 }
 287
 288 // -1, 0, 1 as s1 is lexicographically less, equal greater than s2
 289 int
 290 _Strcmp(Rune *s1, Rune *s2)
 291 {
 292         if(s1 == nil)
 293                 return (s2 == nil || *s2 == 0) ? 0 : -1;
 294         if(s2 == nil)
 295                 return (*s1 == 0) ? 0 : 1;
 296         return runestrcmp(s1, s2);
 297 }
 298
 299 // Like Strcmp, but use exactly n chars of s1 (assume s1 has at least n chars).
 300 // Also, do a case-insensitive match, assuming s2
 301 // has no chars in [A-Z], only their lowercase versions.
 302 // (This routine is used for in-place keyword lookup, where s2 is in a keyword
 303 // list and s1 is some substring, possibly mixed-case, in a buffer.)
 304 int
 305 _Strncmpci(Rune *s1, int n1, Rune *s2)
 306 {
 307         Rune c1, c2;
 308
 309         for(;;) {
 310                 if(n1-- == 0) {
 311                         if(*s2 == 0)
 312                                 return 0;
 313                         return -1;
 314                 }
 315                 c1 = *s1++;
 316                 c2 = *s2++;
 317                 if(c1 >= 'A' && c1 <= 'Z')
 318                         c1 = c1 - 'A' + 'a';
 319                 if(c1 != c2) {
 320                         if(c1 > c2)
 321                                 return 1;
 322                         return -1;
 323                 }
 324         }
 325 }
 326
 327 // emalloc and copy
 328 Rune*
 329 _Strdup(Rune* s)
 330 {
 331         Rune* ans;
 332         if(s == nil)
 333                 return nil;
 334         ans = _Strndup(s, runestrlen(s));
 335         setmalloctag(ans, getcallerpc(&s));
 336         return ans;
 337 }
 338
 339 // emalloc and copy n chars of s (assume s is at least that long),
 340 // and add 0 terminator.
 341 // Return nil if n==0.
 342 Rune*
 343 _Strndup(Rune* s, int n)
 344 {
 345         Rune* ans;
 346
 347         if(n <= 0)
 348                 return nil;
 349         ans = _newstr(n);
 350         memmove(ans, s, n*sizeof(Rune));
 351         ans[n] = 0;
 352         setmalloctag(ans, getcallerpc(&s));
 353         return ans;
 354 }
 355 // emalloc enough room for n Runes, plus 1 null terminator.
 356 // (Not initialized to anything.)
 357 Rune*
 358 _newstr(int n)
 359 {
 360         Rune* ans;
 361
 362         ans = (Rune*)emalloc((n+1)*sizeof(Rune));
 363         setmalloctag(ans, getcallerpc(&n));
 364         return ans;
 365 }
 366
 367 // emalloc and copy s+t
 368 Rune*
 369 _Strdup2(Rune* s, Rune* t)
 370 {
 371         int ns, nt;
 372         Rune* ans;
 373         Rune* p;
 374
 375         ns = _Strlen(s);
 376         nt = _Strlen(t);
 377         if(ns+nt == 0)
 378                 return nil;
 379         ans = _newstr(ns+nt);
 380         p = _Stradd(ans, s, ns);
 381         p = _Stradd(p, t, nt);
 382         *p = 0;
 383         setmalloctag(ans, getcallerpc(&s));
 384         return ans;
 385 }
 386
 387 // Return emalloc'd substring s[start:stop],
 388 Rune*
 389 _Strsubstr(Rune* s, int start, int stop)
 390 {
 391         Rune* t;
 392
 393         if(start == stop)
 394                 return nil;
 395         t = _Strndup(s+start, stop-start);
 396         setmalloctag(t, getcallerpc(&s));
 397         return t;
 398 }
 399
 400 // Copy n chars to s1 from s2, and return s1+n
 401 Rune*
 402 _Stradd(Rune* s1, Rune* s2, int n)
 403 {
 404         if(n == 0)
 405                 return s1;
 406         memmove(s1, s2, n*sizeof(Rune));
 407         return s1+n;
 408 }
 409
 410 // Like strtol, but converting from Rune* string
 411
 412 #define LONG_MAX        2147483647L
 413 #define LONG_MIN        -2147483648L
 414
 415 long
 416 _Strtol(Rune* nptr, Rune** endptr, int base)
 417 {
 418         Rune* p;
 419         long n, nn;
 420         int c, ovfl, v, neg, ndig;
 421
 422         p = nptr;
 423         neg = 0;
 424         n = 0;
 425         ndig = 0;
 426         ovfl = 0;
 427
 428         /*
 429          * White space
 430          */
 431         for(;;p++){
 432                 switch(*p){
 433                 case ' ':
 434                 case '\t':
 435                 case '\n':
 436                 case '\f':
 437                 case '\r':
 438                 case '\v':
 439                         continue;
 440                 }
 441                 break;
 442         }
 443
 444         /*
 445          * Sign
 446          */
 447         if(*p=='-' || *p=='+')
 448                 if(*p++ == '-')
 449                         neg = 1;
 450
 451         /*
 452          * Base
 453          */
 454         if(base==0){
 455                 if(*p != '0')
 456                         base = 10;
 457                 else{
 458                         base = 8;
 459                         if(p[1]=='x' || p[1]=='X'){
 460                                 p += 2;
 461                                 base = 16;
 462                         }
 463                 }
 464         }else if(base==16 && *p=='0'){
 465                 if(p[1]=='x' || p[1]=='X')
 466                         p += 2;
 467         }else if(base<0 || 36<base)
 468                 goto Return;
 469
 470         /*
 471          * Non-empty sequence of digits
 472          */
 473         for(;; p++,ndig++){
 474                 c = *p;
 475                 v = base;
 476                 if('0'<=c && c<='9')
 477                         v = c - '0';
 478                 else if('a'<=c && c<='z')
 479                         v = c - 'a' + 10;
 480                 else if('A'<=c && c<='Z')
 481                         v = c - 'A' + 10;
 482                 if(v >= base)
 483                         break;
 484                 nn = n*base + v;
 485                 if(nn < n)
 486                         ovfl = 1;
 487                 n = nn;
 488         }
 489
 490     Return:
 491         if(ndig == 0)
 492                 p = nptr;
 493         if(endptr)
 494                 *endptr = p;
 495         if(ovfl){
 496                 if(neg)
 497                         return LONG_MIN;
 498                 return LONG_MAX;
 499         }
 500         if(neg)
 501                 return -n;
 502         return n;
 503 }
 504
 505 // Convert buf[0:n], bytes whose character set is chset,
 506 // into a emalloc'd null-terminated Unicode string.
 507 Rune*
 508 toStr(uchar* buf, int n, int chset)
 509 {
 510         int i;
 511         int m;
 512         Rune ch;
 513         Rune* ans;
 514
 515         switch(chset) {
 516         case US_Ascii:
 517         case ISO_8859_1:
 518                 ans = (Rune*)emalloc((n+1)*sizeof(Rune));
 519                 for(i = 0; i < n; i++)
 520                         ans[i] = buf[i];
 521                 ans[n] = 0;
 522                 break;
 523
 524         case UTF_8:
 525                 m = 0;
 526                 for(i = 0; i < n; ) {
 527                         i += chartorune(&ch, (char*)(buf+i));
 528                         m++;
 529                 }
 530                 ans = (Rune*)emalloc((m+1)*sizeof(Rune));
 531                 m = 0;
 532                 for(i = 0; i < n; ) {
 533                         i += chartorune(&ch, (char*)(buf+i));
 534                         ans[m++] = ch;
 535                 }
 536                 ans[m] = 0;
 537                 break;
 538
 539         default:
 540                 ans = nil;
 541                 assert(0);
 542         }
 543         setmalloctag(ans, getcallerpc(&buf));
 544         return ans;
 545 }
 546
 547 // Convert buf[0:n], Unicode characters,
 548 // into an emalloc'd null-terminated string in character set chset.
 549 // Use Runeerror for unconvertable characters.
 550 uchar*
 551 fromStr(Rune* buf, int n, int chset)
 552 {
 553         uchar* ans;
 554         int i, lim, m;
 555         Rune ch;
 556         uchar* p;
 557         uchar s[UTFmax];
 558
 559         ans = nil;
 560         switch(chset) {
 561         case US_Ascii:
 562         case ISO_8859_1:
 563                 ans = (uchar*)emalloc(n+1);
 564                 lim = (chset==US_Ascii)? 127 : 255;
 565                 for(i = 0; i < n; i++) {
 566                         ch = buf[i];
 567                         if(ch > lim)
 568                                 ch = Runeerror;
 569                         ans[i] = ch;
 570                 }
 571                 ans[n] = 0;
 572                 break;
 573
 574         case UTF_8:
 575                 m = 0;
 576                 for(i = 0; i < n; i++) {
 577                         m += runetochar((char*)s, &buf[i]);
 578                 }
 579                 ans = (uchar*)emalloc(m+1);
 580                 p = ans;
 581                 for(i = 0; i < n; i++)
 582                         p += runetochar((char*)p, &buf[i]);
 583                 *p = 0;
 584                 break;
 585
 586         default:
 587                 assert(0);
 588         }
 589         setmalloctag(ans, getcallerpc(&buf));
 590         return ans;
 591 }