source: webkit/trunk/JavaScriptCore/runtime/JSString.h@ 51975

Last change on this file since 51975 was 51975, checked in by [email protected], 15 years ago

​https://bugs.webkit.org/show_bug.cgi?id=32400
Switch remaining cases of string addition to use ropes.

Reviewed by Oliver Hunt.

~1% progression on Sunspidey.

  • jit/JITStubs.cpp:

(JSC::DEFINE_STUB_FUNCTION):

  • runtime/JSString.h:

(JSC::JSString::JSString):
(JSC::JSString::appendStringInConstruct):

  • runtime/Operations.cpp:

(JSC::jsAddSlowCase):

  • runtime/Operations.h:

(JSC::jsString):
(JSC::jsAdd):
  • Property svn:eol-style set to native
File size: 20.2 KB
Line 
1/*
2 * Copyright (C) 1999-2001 Harri Porten ([email protected])
3 * Copyright (C) 2001 Peter Kelly ([email protected])
4 * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Library General Public License for more details.
15 *
16 * You should have received a copy of the GNU Library General Public License
17 * along with this library; see the file COPYING.LIB. If not, write to
18 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 * Boston, MA 02110-1301, USA.
20 *
21 */
22
23#ifndef JSString_h
24#define JSString_h
25
26#include "CallFrame.h"
27#include "CommonIdentifiers.h"
28#include "Identifier.h"
29#include "JSNumberCell.h"
30#include "PropertyDescriptor.h"
31#include "PropertySlot.h"
32
33namespace JSC {
34
35 class JSString;
36
37 JSString* jsEmptyString(JSGlobalData*);
38 JSString* jsEmptyString(ExecState*);
39 JSString* jsString(JSGlobalData*, const UString&); // returns empty string if passed null string
40 JSString* jsString(ExecState*, const UString&); // returns empty string if passed null string
41
42 JSString* jsSingleCharacterString(JSGlobalData*, UChar);
43 JSString* jsSingleCharacterString(ExecState*, UChar);
44 JSString* jsSingleCharacterSubstring(JSGlobalData*, const UString&, unsigned offset);
45 JSString* jsSingleCharacterSubstring(ExecState*, const UString&, unsigned offset);
46 JSString* jsSubstring(JSGlobalData*, const UString&, unsigned offset, unsigned length);
47 JSString* jsSubstring(ExecState*, const UString&, unsigned offset, unsigned length);
48
49 // Non-trivial strings are two or more characters long.
50 // These functions are faster than just calling jsString.
51 JSString* jsNontrivialString(JSGlobalData*, const UString&);
52 JSString* jsNontrivialString(ExecState*, const UString&);
53 JSString* jsNontrivialString(JSGlobalData*, const char*);
54 JSString* jsNontrivialString(ExecState*, const char*);
55
56 // Should be used for strings that are owned by an object that will
57 // likely outlive the JSValue this makes, such as the parse tree or a
58 // DOM object that contains a UString
59 JSString* jsOwnedString(JSGlobalData*, const UString&);
60 JSString* jsOwnedString(ExecState*, const UString&);
61
62 class JSString : public JSCell {
63 public:
64 friend class JIT;
65 friend struct VPtrSet;
66
67 // A Rope is a string composed of a set of substrings.
68 class Rope : public RefCounted<Rope> {
69 public:
70 // A Rope is composed from a set of smaller strings called Fibers.
71 // Each Fiber in a rope is either UString::Rep or another Rope.
72 class Fiber {
73 public:
74 Fiber() {}
75 Fiber(UString::Rep* string) : m_value(reinterpret_cast<intptr_t>(string)) {}
76 Fiber(Rope* rope) : m_value(reinterpret_cast<intptr_t>(rope) | 1) {}
77
78 void deref()
79 {
80 if (isRope())
81 rope()->deref();
82 else
83 string()->deref();
84 }
85
86 Fiber& ref()
87 {
88 if (isString())
89 string()->ref();
90 else
91 rope()->ref();
92 return *this;
93 }
94
95 unsigned refAndGetLength()
96 {
97 if (isString()) {
98 UString::Rep* rep = string();
99 return rep->ref()->len;
100 } else {
101 Rope* r = rope();
102 r->ref();
103 return r->stringLength();
104 }
105 }
106
107 bool isRope() { return m_value & 1; }
108 Rope* rope() { return reinterpret_cast<Rope*>(m_value & ~1); }
109 bool isString() { return !isRope(); }
110 UString::Rep* string() { return reinterpret_cast<UString::Rep*>(m_value); }
111
112 private:
113 intptr_t m_value;
114 };
115
116 // Creates a Rope comprising of 'ropeLength' Fibers.
117 // The Rope is constructed in an uninitialized state - initialize must be called for each Fiber in the Rope.
118 static PassRefPtr<Rope> createOrNull(unsigned ropeLength)
119 {
120 void* allocation;
121 if (tryFastMalloc(sizeof(Rope) + (ropeLength - 1) * sizeof(Fiber)).getValue(allocation))
122 return adoptRef(new (allocation) Rope(ropeLength));
123 return 0;
124 }
125
126 ~Rope();
127 void destructNonRecursive();
128
129 void append(unsigned &index, Fiber& fiber)
130 {
131 m_fibers[index++] = fiber;
132 m_stringLength += fiber.refAndGetLength();
133 }
134 void append(unsigned &index, const UString& string)
135 {
136 UString::Rep* rep = string.rep();
137 m_fibers[index++] = Fiber(rep);
138 m_stringLength += rep->ref()->len;
139 }
140 void append(unsigned& index, JSString* jsString)
141 {
142 if (jsString->isRope()) {
143 for (unsigned i = 0; i < jsString->m_ropeLength; ++i)
144 append(index, jsString->m_fibers[i]);
145 } else
146 append(index, jsString->string());
147 }
148
149 unsigned ropeLength() { return m_ropeLength; }
150 unsigned stringLength() { return m_stringLength; }
151 Fiber& fibers(unsigned index) { return m_fibers[index]; }
152
153 private:
154 Rope(unsigned ropeLength) : m_ropeLength(ropeLength), m_stringLength(0) {}
155 void* operator new(size_t, void* inPlace) { return inPlace; }
156
157 unsigned m_ropeLength;
158 unsigned m_stringLength;
159 Fiber m_fibers[1];
160 };
161
162 JSString(JSGlobalData* globalData, const UString& value)
163 : JSCell(globalData->stringStructure.get())
164 , m_stringLength(value.size())
165 , m_value(value)
166 , m_ropeLength(0)
167 {
168 Heap::heap(this)->reportExtraMemoryCost(value.cost());
169 }
170
171 enum HasOtherOwnerType { HasOtherOwner };
172 JSString(JSGlobalData* globalData, const UString& value, HasOtherOwnerType)
173 : JSCell(globalData->stringStructure.get())
174 , m_stringLength(value.size())
175 , m_value(value)
176 , m_ropeLength(0)
177 {
178 }
179 JSString(JSGlobalData* globalData, PassRefPtr<UString::Rep> value, HasOtherOwnerType)
180 : JSCell(globalData->stringStructure.get())
181 , m_stringLength(value->size())
182 , m_value(value)
183 , m_ropeLength(0)
184 {
185 }
186 JSString(JSGlobalData* globalData, PassRefPtr<JSString::Rope> rope)
187 : JSCell(globalData->stringStructure.get())
188 , m_stringLength(rope->stringLength())
189 , m_ropeLength(1)
190 {
191 m_fibers[0] = rope.releaseRef();
192 }
193 // This constructor constructs a new string by concatenating s1 & s2.
194 // This should only be called with ropeLength <= 3.
195 JSString(JSGlobalData* globalData, unsigned ropeLength, JSString* s1, JSString* s2)
196 : JSCell(globalData->stringStructure.get())
197 , m_stringLength(s1->length() + s2->length())
198 , m_ropeLength(ropeLength)
199 {
200 ASSERT(ropeLength <= s_maxInternalRopeLength);
201 unsigned index = 0;
202 appendStringInConstruct(index, s1);
203 appendStringInConstruct(index, s2);
204 ASSERT(ropeLength == index);
205 }
206 // This constructor constructs a new string by concatenating s1 & s2.
207 // This should only be called with ropeLength <= 3.
208 JSString(JSGlobalData* globalData, unsigned ropeLength, JSString* s1, const UString& u2)
209 : JSCell(globalData->stringStructure.get())
210 , m_stringLength(s1->length() + u2.size())
211 , m_ropeLength(ropeLength)
212 {
213 ASSERT(ropeLength <= s_maxInternalRopeLength);
214 unsigned index = 0;
215 appendStringInConstruct(index, s1);
216 appendStringInConstruct(index, u2);
217 ASSERT(ropeLength == index);
218 }
219 // This constructor constructs a new string by concatenating s1 & s2.
220 // This should only be called with ropeLength <= 3.
221 JSString(JSGlobalData* globalData, unsigned ropeLength, const UString& u1, JSString* s2)
222 : JSCell(globalData->stringStructure.get())
223 , m_stringLength(u1.size() + s2->length())
224 , m_ropeLength(ropeLength)
225 {
226 ASSERT(ropeLength <= s_maxInternalRopeLength);
227 unsigned index = 0;
228 appendStringInConstruct(index, u1);
229 appendStringInConstruct(index, s2);
230 ASSERT(ropeLength == index);
231 }
232 // This constructor constructs a new string by concatenating v1, v2 & v3.
233 // This should only be called with ropeLength <= 3 ... which since every
234 // value must require a ropeLength of at least one implies that the length
235 // for each value must be exactly 1!
236 JSString(ExecState* exec, JSValue v1, JSValue v2, JSValue v3)
237 : JSCell(exec->globalData().stringStructure.get())
238 , m_stringLength(0)
239 , m_ropeLength(s_maxInternalRopeLength)
240 {
241 unsigned index = 0;
242 appendValueInConstructAndIncrementLength(exec, index, v1);
243 appendValueInConstructAndIncrementLength(exec, index, v2);
244 appendValueInConstructAndIncrementLength(exec, index, v3);
245 ASSERT(index == s_maxInternalRopeLength);
246 }
247
248 ~JSString()
249 {
250 for (unsigned i = 0; i < m_ropeLength; ++i)
251 m_fibers[i].deref();
252 }
253
254 const UString& value(ExecState* exec) const
255 {
256 if (isRope())
257 resolveRope(exec);
258 return m_value;
259 }
260 const UString tryGetValue() const
261 {
262 if (isRope())
263 UString();
264 return m_value;
265 }
266 unsigned length() { return m_stringLength; }
267
268 bool getStringPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&);
269 bool getStringPropertySlot(ExecState*, unsigned propertyName, PropertySlot&);
270 bool getStringPropertyDescriptor(ExecState*, const Identifier& propertyName, PropertyDescriptor&);
271
272 bool canGetIndex(unsigned i) { return i < m_stringLength; }
273 JSString* getIndex(ExecState*, unsigned);
274
275 static PassRefPtr<Structure> createStructure(JSValue proto) { return Structure::create(proto, TypeInfo(StringType, OverridesGetOwnPropertySlot | NeedsThisConversion)); }
276
277 private:
278 enum VPtrStealingHackType { VPtrStealingHack };
279 JSString(VPtrStealingHackType)
280 : JSCell(0)
281 , m_ropeLength(0)
282 {
283 }
284
285 void resolveRope(ExecState*) const;
286
287 void appendStringInConstruct(unsigned& index, const UString& string)
288 {
289 m_fibers[index++] = Rope::Fiber(string.rep()->ref());
290 }
291
292 void appendStringInConstruct(unsigned& index, JSString* jsString)
293 {
294 if (jsString->isRope()) {
295 for (unsigned i = 0; i < jsString->m_ropeLength; ++i)
296 m_fibers[index++] = jsString->m_fibers[i].ref();
297 } else
298 appendStringInConstruct(index, jsString->string());
299 }
300
301 void appendValueInConstructAndIncrementLength(ExecState* exec, unsigned& index, JSValue v)
302 {
303 if (v.isString()) {
304 ASSERT(asCell(v)->isString());
305 JSString* s = static_cast<JSString*>(asCell(v));
306 ASSERT(s->ropeLength() == 1);
307 appendStringInConstruct(index, s);
308 m_stringLength += s->length();
309 } else {
310 UString u(v.toString(exec));
311 m_fibers[index++] = Rope::Fiber(u.rep()->ref());
312 m_stringLength += u.size();
313 }
314 }
315
316 virtual JSValue toPrimitive(ExecState*, PreferredPrimitiveType) const;
317 virtual bool getPrimitiveNumber(ExecState*, double& number, JSValue& value);
318 virtual bool toBoolean(ExecState*) const;
319 virtual double toNumber(ExecState*) const;
320 virtual JSObject* toObject(ExecState*) const;
321 virtual UString toString(ExecState*) const;
322
323 virtual JSObject* toThisObject(ExecState*) const;
324 virtual UString toThisString(ExecState*) const;
325 virtual JSString* toThisJSString(ExecState*);
326
327 // Actually getPropertySlot, not getOwnPropertySlot (see JSCell).
328 virtual bool getOwnPropertySlot(ExecState*, const Identifier& propertyName, PropertySlot&);
329 virtual bool getOwnPropertySlot(ExecState*, unsigned propertyName, PropertySlot&);
330 virtual bool getOwnPropertyDescriptor(ExecState*, const Identifier&, PropertyDescriptor&);
331
332 static const unsigned s_maxInternalRopeLength = 3;
333
334 // A string is represented either by a UString or a Rope.
335 unsigned m_stringLength;
336 mutable UString m_value;
337 mutable unsigned m_ropeLength;
338 mutable Rope::Fiber m_fibers[s_maxInternalRopeLength];
339
340 bool isRope() const { return m_ropeLength; }
341 UString& string() { ASSERT(!isRope()); return m_value; }
342 unsigned ropeLength() { return m_ropeLength ? m_ropeLength : 1; }
343
344 friend JSValue jsString(ExecState* exec, JSString* s1, JSString* s2);
345 friend JSValue jsString(ExecState* exec, const UString& u1, JSString* s2);
346 friend JSValue jsString(ExecState* exec, JSString* s1, const UString& u2);
347 friend JSValue jsString(ExecState* exec, Register* strings, unsigned count);
348 };
349
350 JSString* asString(JSValue);
351
352 inline JSString* asString(JSValue value)
353 {
354 ASSERT(asCell(value)->isString());
355 return static_cast<JSString*>(asCell(value));
356 }
357
358 inline JSString* jsEmptyString(JSGlobalData* globalData)
359 {
360 return globalData->smallStrings.emptyString(globalData);
361 }
362
363 inline JSString* jsSingleCharacterString(JSGlobalData* globalData, UChar c)
364 {
365 if (c <= 0xFF)
366 return globalData->smallStrings.singleCharacterString(globalData, c);
367 return new (globalData) JSString(globalData, UString(&c, 1));
368 }
369
370 inline JSString* jsSingleCharacterSubstring(JSGlobalData* globalData, const UString& s, unsigned offset)
371 {
372 ASSERT(offset < static_cast<unsigned>(s.size()));
373 UChar c = s.data()[offset];
374 if (c <= 0xFF)
375 return globalData->smallStrings.singleCharacterString(globalData, c);
376 return new (globalData) JSString(globalData, UString(UString::Rep::create(s.rep(), offset, 1)));
377 }
378
379 inline JSString* jsNontrivialString(JSGlobalData* globalData, const char* s)
380 {
381 ASSERT(s);
382 ASSERT(s[0]);
383 ASSERT(s[1]);
384 return new (globalData) JSString(globalData, s);
385 }
386
387 inline JSString* jsNontrivialString(JSGlobalData* globalData, const UString& s)
388 {
389 ASSERT(s.size() > 1);
390 return new (globalData) JSString(globalData, s);
391 }
392
393 inline JSString* JSString::getIndex(ExecState* exec, unsigned i)
394 {
395 ASSERT(canGetIndex(i));
396 return jsSingleCharacterSubstring(&exec->globalData(), value(exec), i);
397 }
398
399 inline JSString* jsString(JSGlobalData* globalData, const UString& s)
400 {
401 int size = s.size();
402 if (!size)
403 return globalData->smallStrings.emptyString(globalData);
404 if (size == 1) {
405 UChar c = s.data()[0];
406 if (c <= 0xFF)
407 return globalData->smallStrings.singleCharacterString(globalData, c);
408 }
409 return new (globalData) JSString(globalData, s);
410 }
411
412 inline JSString* jsSubstring(JSGlobalData* globalData, const UString& s, unsigned offset, unsigned length)
413 {
414 ASSERT(offset <= static_cast<unsigned>(s.size()));
415 ASSERT(length <= static_cast<unsigned>(s.size()));
416 ASSERT(offset + length <= static_cast<unsigned>(s.size()));
417 if (!length)
418 return globalData->smallStrings.emptyString(globalData);
419 if (length == 1) {
420 UChar c = s.data()[offset];
421 if (c <= 0xFF)
422 return globalData->smallStrings.singleCharacterString(globalData, c);
423 }
424 return new (globalData) JSString(globalData, UString(UString::Rep::create(s.rep(), offset, length)));
425 }
426
427 inline JSString* jsOwnedString(JSGlobalData* globalData, const UString& s)
428 {
429 int size = s.size();
430 if (!size)
431 return globalData->smallStrings.emptyString(globalData);
432 if (size == 1) {
433 UChar c = s.data()[0];
434 if (c <= 0xFF)
435 return globalData->smallStrings.singleCharacterString(globalData, c);
436 }
437 return new (globalData) JSString(globalData, s, JSString::HasOtherOwner);
438 }
439
440 inline JSString* jsEmptyString(ExecState* exec) { return jsEmptyString(&exec->globalData()); }
441 inline JSString* jsString(ExecState* exec, const UString& s) { return jsString(&exec->globalData(), s); }
442 inline JSString* jsSingleCharacterString(ExecState* exec, UChar c) { return jsSingleCharacterString(&exec->globalData(), c); }
443 inline JSString* jsSingleCharacterSubstring(ExecState* exec, const UString& s, unsigned offset) { return jsSingleCharacterSubstring(&exec->globalData(), s, offset); }
444 inline JSString* jsSubstring(ExecState* exec, const UString& s, unsigned offset, unsigned length) { return jsSubstring(&exec->globalData(), s, offset, length); }
445 inline JSString* jsNontrivialString(ExecState* exec, const UString& s) { return jsNontrivialString(&exec->globalData(), s); }
446 inline JSString* jsNontrivialString(ExecState* exec, const char* s) { return jsNontrivialString(&exec->globalData(), s); }
447 inline JSString* jsOwnedString(ExecState* exec, const UString& s) { return jsOwnedString(&exec->globalData(), s); }
448
449 ALWAYS_INLINE bool JSString::getStringPropertySlot(ExecState* exec, const Identifier& propertyName, PropertySlot& slot)
450 {
451 if (propertyName == exec->propertyNames().length) {
452 slot.setValue(jsNumber(exec, m_stringLength));
453 return true;
454 }
455
456 bool isStrictUInt32;
457 unsigned i = propertyName.toStrictUInt32(&isStrictUInt32);
458 if (isStrictUInt32 && i < m_stringLength) {
459 slot.setValue(jsSingleCharacterSubstring(exec, value(exec), i));
460 return true;
461 }
462
463 return false;
464 }
465
466 ALWAYS_INLINE bool JSString::getStringPropertySlot(ExecState* exec, unsigned propertyName, PropertySlot& slot)
467 {
468 if (propertyName < m_stringLength) {
469 slot.setValue(jsSingleCharacterSubstring(exec, value(exec), propertyName));
470 return true;
471 }
472
473 return false;
474 }
475
476 inline bool isJSString(JSGlobalData* globalData, JSValue v) { return v.isCell() && v.asCell()->vptr() == globalData->jsStringVPtr; }
477
478 // --- JSValue inlines ----------------------------
479
480 inline JSString* JSValue::toThisJSString(ExecState* exec)
481 {
482 return isCell() ? asCell()->toThisJSString(exec) : jsString(exec, toString(exec));
483 }
484
485 inline UString JSValue::toString(ExecState* exec) const
486 {
487 if (isString())
488 return static_cast<JSString*>(asCell())->value(exec);
489 if (isInt32())
490 return exec->globalData().numericStrings.add(asInt32());
491 if (isDouble())
492 return exec->globalData().numericStrings.add(asDouble());
493 if (isTrue())
494 return "true";
495 if (isFalse())
496 return "false";
497 if (isNull())
498 return "null";
499 if (isUndefined())
500 return "undefined";
501 ASSERT(isCell());
502 return asCell()->toString(exec);
503 }
504
505} // namespace JSC
506
507#endif // JSString_h
Note: See TracBrowser for help on using the repository browser.