Reviewed by Maciej
[WebKit-https.git] / WebCore / platform / StringImpl.cpp
1 /**
2  * This file is part of the DOM implementation for KDE.
3  *
4  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
5  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
6  *           (C) 2001 Dirk Mueller ( mueller@kde.org )
7  * Copyright (C) 2003, 2004, 2005, 2006 Apple Computer, Inc.
8  * Copyright (C) 2006 Andrew Wellington (proton@wiretapped.net)
9  *
10  * This library is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU Library General Public
12  * License as published by the Free Software Foundation; either
13  * version 2 of the License, or (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  * Library General Public License for more details.
19  *
20  * You should have received a copy of the GNU Library General Public License
21  * along with this library; see the file COPYING.LIB.  If not, write to
22  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
23  * Boston, MA 02111-1307, USA.
24  *
25  */
26
27 #include "config.h"
28 #include "StringImpl.h"
29
30 #include "AtomicString.h"
31 #include "Length.h"
32 #include <kxmlcore/Assertions.h>
33 #include <string.h>
34 #include <unicode/ubrk.h>
35
36 using namespace KXMLCore;
37
38 namespace WebCore {
39
40 static inline QChar* newQCharVector(unsigned n)
41 {
42     return static_cast<QChar*>(fastMalloc(sizeof(QChar) * n));
43 }
44
45 static inline void deleteQCharVector(QChar* p)
46 {
47     fastFree(p);
48 }
49
50 StringImpl* StringImpl::empty()
51 {
52     static WithOneRef w;
53     static StringImpl e(w);
54     return &e;
55 }
56
57 StringImpl::StringImpl(const QString& str)
58 {
59     initWithQChar(str.unicode(), str.length());
60 }
61
62 StringImpl::StringImpl(const QChar* str, unsigned len)
63 {
64     initWithQChar(str, len);
65 }
66
67 StringImpl::StringImpl(const char* str)
68 {
69     initWithChar(str, strlen(str));
70 }
71
72 StringImpl::StringImpl(const char* str, unsigned int len)
73 {
74     initWithChar(str, len);
75 }
76
77 void StringImpl::initWithChar(const char* str, unsigned int len)
78 {
79     _hash = 0;
80     _inTable = false;
81     l = len;
82     if (!l || !str) {
83         s = 0;
84         return;
85     }
86     
87     s = newQCharVector(l);
88     int i = l;
89     QChar* ptr = s;
90     while (i--)
91         *ptr++ = *str++;
92 }
93
94 void StringImpl::initWithQChar(const QChar* str, unsigned int len)
95 {
96     _hash = 0;
97     _inTable = false;
98     l = len;
99     if (!l || !str) {
100         s = 0;
101         return;
102     }
103     
104     s = newQCharVector(len);
105     memcpy(s, str, len * sizeof(QChar));
106 }
107
108 StringImpl::~StringImpl()
109 {
110     if (_inTable)
111         AtomicString::remove(this);
112     deleteQCharVector(s);
113 }
114
115 void StringImpl::append(const StringImpl* str)
116 {
117     assert(!_inTable);
118     if(str && str->l != 0)
119     {
120         int newlen = l+str->l;
121         QChar* c = newQCharVector(newlen);
122         memcpy(c, s, l*sizeof(QChar));
123         memcpy(c+l, str->s, str->l*sizeof(QChar));
124         deleteQCharVector(s);
125         s = c;
126         l = newlen;
127     }
128 }
129
130 void StringImpl::insert(const StringImpl* str, unsigned pos)
131 {
132     assert(!_inTable);
133     if (pos >= l) {
134         append(str);
135         return;
136     }
137     if (str && str->l != 0) {
138         int newlen = l + str->l;
139         QChar* c = newQCharVector(newlen);
140         memcpy(c, s, pos*sizeof(QChar));
141         memcpy(c+pos, str->s, str->l*sizeof(QChar));
142         memcpy(c+pos+str->l, s+pos, (l-pos)*sizeof(QChar));
143         deleteQCharVector(s);
144         s = c;
145         l = newlen;
146     }
147 }
148
149 void StringImpl::truncate(int len)
150 {
151     assert(!_inTable);
152     if (len > (int)l)
153         return;
154     int nl = len < 1 ? 1 : len;
155     QChar* c = newQCharVector(nl);
156     memcpy(c, s, nl*sizeof(QChar));
157     deleteQCharVector(s);
158     s = c;
159     l = len;
160 }
161
162 void StringImpl::remove(unsigned pos, int len)
163 {
164     assert(!_inTable);
165     if(len <= 0) return;
166     if(pos >= l ) return;
167     if((unsigned)len > l - pos)
168     len = l - pos;
169
170     unsigned newLen = l-len;
171     QChar* c = newQCharVector(newLen);
172     memcpy(c, s, pos*sizeof(QChar));
173     memcpy(c+pos, s+pos+len, (l-len-pos)*sizeof(QChar));
174     deleteQCharVector(s);
175     s = c;
176     l = newLen;
177 }
178
179 StringImpl* StringImpl::split(unsigned pos)
180 {
181     assert(!_inTable);
182     if( pos >=l ) return new StringImpl();
183
184     unsigned newLen = l-pos;
185     QChar* c = newQCharVector(newLen);
186     memcpy(c, s+pos, newLen*sizeof(QChar));
187
188     StringImpl* str = new StringImpl(s + pos, newLen);
189     truncate(pos);
190     return str;
191 }
192
193 bool StringImpl::containsOnlyWhitespace() const
194 {
195     return containsOnlyWhitespace(0, l);
196 }
197
198 bool StringImpl::containsOnlyWhitespace(unsigned int from, unsigned int len) const
199 {
200     if (!s)
201         return true;
202     
203     for (unsigned i = from; i < len; i++) {
204         QChar c = s[i];
205         if (c.unicode() <= 0x7F) {
206             if (!isspace(c.unicode()))
207                 return false;
208         } 
209         else
210             return false;
211     }
212     return true;
213 }
214     
215 StringImpl* StringImpl::substring(unsigned pos, unsigned len)
216 {
217     if (pos >= l) return
218         new StringImpl;
219     if (len > l - pos)
220         len = l - pos;
221     return new StringImpl(s + pos, len);
222 }
223
224 static Length parseLength(const QChar* s, unsigned int l)
225 {
226     if (l == 0)
227         return Length(1, Relative);
228
229     unsigned i = 0;
230     while (i < l && s[i].isSpace())
231         ++i;
232     if (i < l && (s[i] == '+' || s[i] == '-'))
233         ++i;
234     while (i < l && s[i].isDigit())
235         ++i;
236
237     bool ok;
238     int r = QConstString(s, i).string().toInt(&ok);
239
240     /* Skip over any remaining digits, we are not that accurate (5.5% => 5%) */
241     while (i < l && (s[i].isDigit() || s[i] == '.'))
242         ++i;
243
244     /* IE Quirk: Skip any whitespace (20 % => 20%) */
245     while (i < l && s[i].isSpace())
246         ++i;
247
248     if (ok) {
249         if (i == l) {
250             return Length(r, Fixed);
251         } else {
252             const QChar* next = s+i;
253
254             if (*next == '%')
255                 return Length(r, Percent);
256
257             if (*next == '*')
258                 return Length(r, Relative);
259         }
260         return Length(r, Fixed);
261     } else {
262         if (i < l) {
263             const QChar* next = s + i;
264
265             if (*next == '*')
266                 return Length(1, Relative);
267
268             if (*next == '%')
269                 return Length(1, Relative);
270         }
271     }
272     return Length(0, Relative);
273 }
274
275 Length StringImpl::toLength() const
276 {
277     return parseLength(s, l);
278 }
279
280 Length* StringImpl::toCoordsArray(int& len) const
281 {
282     QChar* spacified = newQCharVector(l);
283     QChar space(' ');
284     for(unsigned int i=0; i < l; i++) {
285         QChar cc = s[i];
286         if (cc > '9' || (cc < '0' && cc != '-' && cc != '*' && cc != '.'))
287             spacified[i] = space;
288         else
289             spacified[i] = cc;
290     }
291     QString str(spacified, l);
292     deleteQCharVector(spacified);
293
294     str = str.simplifyWhiteSpace();
295
296     len = str.contains(' ') + 1;
297     Length* r = new Length[len];
298
299     int i = 0;
300     int pos = 0;
301     int pos2;
302
303     while((pos2 = str.find(' ', pos)) != -1) {
304         r[i++] = parseLength(str.unicode() + pos, pos2-pos);
305         pos = pos2+1;
306     }
307     r[i] = parseLength(str.unicode() + pos, str.length()-pos);
308
309     return r;
310 }
311
312 Length* StringImpl::toLengthArray(int& len) const
313 {
314     QString str(s, l);
315     str = str.simplifyWhiteSpace();
316
317     len = str.contains(',') + 1;
318     Length* r = new Length[len];
319
320     int i = 0;
321     int pos = 0;
322     int pos2;
323
324     while((pos2 = str.find(',', pos)) != -1) {
325         r[i++] = parseLength(str.unicode() + pos, pos2 - pos);
326         pos = pos2+1;
327     }
328
329     /* IE Quirk: If the last comma is the last char skip it and reduce len by one */
330     if (str.length()-pos > 0)
331         r[i] = parseLength(str.unicode() + pos, str.length() - pos);
332     else
333         len--;
334
335     return r;
336 }
337
338 bool StringImpl::isLower() const
339 {
340     unsigned int i;
341     for (i = 0; i < l; i++)
342         if (s[i].lower() != s[i])
343             return false;
344     return true;
345 }
346
347 StringImpl* StringImpl::lower() const
348 {
349     StringImpl* c = new StringImpl;
350     if (!l)
351         return c;
352
353     c->s = newQCharVector(l);
354     c->l = l;
355
356     for (unsigned int i = 0; i < l; i++)
357         c->s[i] = s[i].lower();
358
359     return c;
360 }
361
362 StringImpl* StringImpl::upper() const
363 {
364     StringImpl* c = new StringImpl;
365     if (!l)
366         return c;
367
368     c->s = newQCharVector(l);
369     c->l = l;
370
371     for (unsigned int i = 0; i < l; i++)
372         c->s[i] = s[i].upper();
373
374     return c;
375 }
376
377 static UBreakIterator* getWordBreakIterator(const QChar* string, int length)
378 {
379     // The locale is currently ignored when determining character cluster breaks.
380     // This may change in the future, according to Deborah Goldsmith.
381     static bool createdIterator = false;
382     static UBreakIterator* iterator;
383     UErrorCode status;
384     if (!createdIterator) {
385         status = U_ZERO_ERROR;
386         iterator = ubrk_open(UBRK_WORD, "en_us", 0, 0, &status);
387         createdIterator = true;
388     }
389     if (!iterator)
390         return 0;
391
392     status = U_ZERO_ERROR;
393     ubrk_setText(iterator, reinterpret_cast<const UChar*>(string), length, &status);
394     if (status != U_ZERO_ERROR)
395         return 0;
396
397     return iterator;
398 }
399
400 StringImpl* StringImpl::capitalize(QChar previous) const
401 {
402     StringImpl* capitalizedString = new StringImpl;
403     if(!l) return capitalizedString;
404     
405     QChar* stringWithPrevious = newQCharVector(l + 1);
406     stringWithPrevious[0] = previous;
407     for (unsigned i = 1; i < l + 1; i++)
408         stringWithPrevious[i] = s[i - 1];
409     
410     UBreakIterator* boundary = getWordBreakIterator(stringWithPrevious, l + 1);
411     if (!boundary)
412         return capitalizedString;
413     
414     capitalizedString->s = newQCharVector(l);
415     capitalizedString->l = l;
416     
417     int32_t end;
418     int32_t start = ubrk_first(boundary);
419     for (end = ubrk_next(boundary); end != UBRK_DONE; start = end, end = ubrk_next(boundary)) {
420         if (start != 0)
421             capitalizedString->s[start - 1] = stringWithPrevious[start].upper();
422         for (int i = start; i < end; i++)
423             capitalizedString->s[i] = stringWithPrevious[i + 1];
424     }
425     
426     return capitalizedString;
427 }
428
429 int StringImpl::toInt(bool* ok) const
430 {
431     unsigned i = 0;
432
433     // Allow leading spaces.
434     for (; i != l; ++i) {
435         if (!s[i].isSpace()) {
436             break;
437         }
438     }
439     
440     // Allow sign.
441     if (i != l) {
442         if (s[i] == '+' || s[i] == '-') {
443             ++i;
444         }
445     }
446     
447     // Allow digits.
448     for (; i != l; ++i) {
449         if (!s[i].isDigit()) {
450             break;
451         }
452     }
453     
454     return QConstString(s, i).string().toInt(ok);
455 }
456
457 static bool equal(const QChar* a, const char* b, int l)
458 {
459     ASSERT(l >= 0);
460     while (l--) {
461         if (*a != *b)
462             return false;
463         a++; b++;
464     }
465     return true;
466 }
467
468 static bool equalCaseInsensitive(const QChar* a, const char* b, int l)
469 {
470     ASSERT(l >= 0);
471     while (l--) {
472         if (tolower(a->unicode()) != tolower(*b))
473             return false;
474         a++; b++;
475     }
476     return true;
477 }
478
479 static bool equalCaseInsensitive(const QChar* a, const QChar* b, int l)
480 {
481     ASSERT(l >= 0);
482     while (l--) {
483         if (tolower(a->unicode()) != tolower(b->unicode()))
484             return false;
485         a++; b++;
486     }
487     return true;
488 }
489
490 // This function should be as fast as possible, every little bit helps.
491 // Our usage patterns are typically small strings.  In time trials
492 // this simplistic algorithm is much faster than Boyer-Moore or hash
493 // based algorithms.
494 // NOTE: Those time trials were done when this function was part of KWQ's QString
495 // It was copied here and changed slightly since.
496 int StringImpl::find(const char* chs, int index, bool caseSensitive) const
497 {
498     if (!chs || index < 0)
499         return -1;
500
501     int chsLength = strlen(chs);
502     int n = l - index;
503     if (n < 0)
504         return -1;
505     n -= chsLength - 1;
506     if (n <= 0)
507         return -1;
508
509     const char* chsPlusOne = chs + 1;
510     int chsLengthMinusOne = chsLength - 1;
511     
512     const QChar* ptr = s + index - 1;
513     if (caseSensitive) {
514         QChar c = *chs;
515         do {
516             if (*++ptr == c && equal(ptr + 1, chsPlusOne, chsLengthMinusOne))
517                 return l - chsLength - n + 1;
518         } while (--n);
519     } else {
520         int lc = tolower((unsigned char)*chs);
521         do {
522             if (tolower((++ptr)->unicode()) == lc && equalCaseInsensitive(ptr + 1, chsPlusOne, chsLengthMinusOne))
523                 return l - chsLength - n + 1;
524         } while (--n);
525     }
526
527     return -1;
528 }
529
530 int StringImpl::find(const QChar c, int start) const
531 {
532     unsigned int index = start;
533     if (index >= l )
534         return -1;
535     while(index < l) {
536         if (s[index] == c)
537             return index;
538         index++;
539     }
540     return -1;
541 }
542
543 // This was copied from KWQ's QString and made to work here w/ small modifications.
544 // FIXME comments were from the QString version.
545 int StringImpl::find(const StringImpl* str, int index, bool caseSensitive) const
546 {
547     // FIXME, use the first character algorithm
548     /*
549       We use some weird hashing for efficiency's sake.  Instead of
550       comparing strings, we compare the sum of str with that of
551       a part of this QString.  Only if that matches, we call memcmp
552       or ucstrnicmp.
553
554       The hash value of a string is the sum of the cells of its
555       QChars.
556     */
557     ASSERT(str);
558     if (index < 0)
559         index += l;
560     int lstr = str->l;
561     int lthis = l - index;
562     if ((unsigned)lthis > l)
563         return -1;
564     int delta = lthis - lstr;
565     if (delta < 0)
566         return -1;
567
568     const QChar* uthis = s + index;
569     const QChar* ustr = str->s;
570     unsigned hthis = 0;
571     unsigned hstr = 0;
572     if (caseSensitive) {
573         for (int i = 0; i < lstr; i++) {
574             hthis += uthis[i].unicode();
575             hstr += ustr[i].unicode();
576         }
577         int i = 0;
578         while (1) {
579             if (hthis == hstr && memcmp(uthis + i, ustr, lstr * sizeof(QChar)) == 0)
580                 return index + i;
581             if (i == delta)
582                 return -1;
583             hthis += uthis[i + lstr].unicode();
584             hthis -= uthis[i].unicode();
585             i++;
586         }
587     } else {
588         for (int i = 0; i < lstr; i++ ) {
589             hthis += tolower(uthis[i].unicode());
590             hstr += tolower(ustr[i].unicode());
591         }
592         int i = 0;
593         while (1) {
594             if (hthis == hstr && equalCaseInsensitive(uthis + i, ustr, lstr))
595                 return index + i;
596             if (i == delta)
597                 return -1;
598             hthis += tolower(uthis[i + lstr].unicode());
599             hthis -= tolower(uthis[i].unicode());
600             i++;
601         }
602     }
603 }
604
605 bool StringImpl::endsWith(const StringImpl* s, bool caseSensitive) const
606 {
607     ASSERT(s);
608     int start = l - s->l;
609     if (start >= 0)
610         return (find(s, start, caseSensitive) == start);
611     return false;
612 }
613
614 StringImpl* StringImpl::replace(QChar oldC, QChar newC)
615 {
616     if (oldC == newC)
617         return this;
618     unsigned i;
619     for (i = 0; i != l; ++i)
620         if (s[i] == oldC)
621             break;
622     if (i == l)
623         return this;
624
625     StringImpl* c = new StringImpl;
626
627     c->s = newQCharVector(l);
628     c->l = l;
629
630     for (i = 0; i != l; ++i) {
631         QChar ch = s[i];
632         if (ch == oldC)
633             ch = newC;
634         c->s[i] = ch;
635     }
636
637     return c;
638 }
639
640 bool equal(const StringImpl* a, const StringImpl* b)
641 {
642     return StrHash<StringImpl*>::equal(a, b);
643 }
644
645 bool equal(const StringImpl* a, const char* b)
646 {
647     if (!a)
648         return !b;
649     if (!b)
650         return !a;
651
652     unsigned length = a->l;
653     const QChar* as = a->s;
654     for (unsigned i = 0; i != length; ++i) {
655         char c = b[i];
656         if (!c)
657             return false;
658         if (as[i] != c)
659             return false;
660     }
661
662     return !b[length];
663 }
664
665 bool equal(const char* a, const StringImpl* b)
666 {
667     if (!a)
668         return !b;
669     if (!b)
670         return !a;
671
672     unsigned length = b->l;
673     const QChar* bs = b->s;
674     for (unsigned i = 0; i != length; ++i) {
675         char c = a[i];
676         if (!c)
677             return false;
678         if (c != bs[i])
679             return false;
680     }
681
682     return !a[length];
683 }
684
685 bool equalIgnoringCase(const StringImpl* a, const StringImpl* b)
686 {
687     return CaseInsensitiveHash::equal(a, b);
688 }
689
690 bool equalIgnoringCase(const StringImpl* a, const char* b)
691 {
692     if (!a)
693         return !b;
694     if (!b)
695         return !a;
696
697     unsigned length = a->l;
698     const QChar* as = a->s;
699     for (unsigned i = 0; i != length; ++i) {
700         char c = b[i];
701         if (!c)
702             return false;
703         if (as[i].lower() != QChar(c).lower())
704             return false;
705     }
706
707     return !b[length];
708 }
709
710 bool equalIgnoringCase(const char* a, const StringImpl* b)
711 {
712     if (!a)
713         return !b;
714     if (!b)
715         return !a;
716
717     unsigned length = b->l;
718     const QChar* bs = b->s;
719     for (unsigned i = 0; i != length; ++i) {
720         char c = a[i];
721         if (!c)
722             return false;
723         if (QChar(c).lower() != bs[i].lower())
724             return false;
725     }
726
727     return !a[length];
728 }
729
730 // Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
731 // or anything like that.
732 const unsigned PHI = 0x9e3779b9U;
733
734 // Paul Hsieh's SuperFastHash
735 // http://www.azillionmonkeys.com/qed/hash.html
736 unsigned StringImpl::computeHash(const QChar* s, unsigned len)
737 {
738     unsigned l = len;
739     uint32_t hash = PHI;
740     uint32_t tmp;
741     
742     int rem = l & 1;
743     l >>= 1;
744     
745     // Main loop
746     for (; l > 0; l--) {
747         hash += s[0].unicode();
748         tmp = (s[1].unicode() << 11) ^ hash;
749         hash = (hash << 16) ^ tmp;
750         s += 2;
751         hash += hash >> 11;
752     }
753     
754     // Handle end case
755     if (rem) {
756         hash += s[0].unicode();
757         hash ^= hash << 11;
758         hash += hash >> 17;
759     }
760
761     // Force "avalanching" of final 127 bits
762     hash ^= hash << 3;
763     hash += hash >> 5;
764     hash ^= hash << 2;
765     hash += hash >> 15;
766     hash ^= hash << 10;
767
768     // this avoids ever returning a hash code of 0, since that is used to
769     // signal "hash not computed yet", using a value that is likely to be
770     // effectively the same as 0 when the low bits are masked
771     if (hash == 0)
772         hash = 0x80000000;
773     
774     return hash;
775 }
776
777 // Paul Hsieh's SuperFastHash
778 // http://www.azillionmonkeys.com/qed/hash.html
779 unsigned StringImpl::computeHash(const char* s)
780 {
781     // This hash is designed to work on 16-bit chunks at a time. But since the normal case
782     // (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
783     // were 16-bit chunks, which should give matching results
784
785     unsigned l = strlen(s);
786     uint32_t hash = PHI;
787     uint32_t tmp;
788     
789     int rem = l & 1;
790     l >>= 1;
791     
792     // Main loop
793     for (; l > 0; l--) {
794         hash += (unsigned char)s[0];
795         tmp = ((unsigned char)s[1] << 11) ^ hash;
796         hash = (hash << 16) ^ tmp;
797         s += 2;
798         hash += hash >> 11;
799     }
800     
801     // Handle end case
802     if (rem) {
803         hash += (unsigned char)s[0];
804         hash ^= hash << 11;
805         hash += hash >> 17;
806     }
807
808     // Force "avalanching" of final 127 bits
809     hash ^= hash << 3;
810     hash += hash >> 5;
811     hash ^= hash << 2;
812     hash += hash >> 15;
813     hash ^= hash << 10;
814
815     // this avoids ever returning a hash code of 0, since that is used to
816     // signal "hash not computed yet", using a value that is likely to be
817     // effectively the same as 0 when the low bits are masked
818     if (hash == 0)
819         hash = 0x80000000;
820     
821     return hash;
822 }
823
824 const char* StringImpl::ascii() const
825 {
826     char* buffer = new char[l + 1];
827     char* p = buffer;
828     for (unsigned i = 0; i != l; ++i) {
829         unsigned short c = s[i].unicode();
830         if (c >= 0x20 && c < 0x7F)
831             *p++ = c;
832         else
833             *p++ = '?';
834     }
835     *p++ = '\0';
836     return buffer;
837 }
838
839 } // namespace WebCore
840
841 namespace KXMLCore {
842
843 const RefPtr<WebCore::StringImpl> HashTraits<RefPtr<WebCore::StringImpl> >::_deleted = new WebCore::StringImpl(static_cast<char*>(0), 0);
844
845 }