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