1 /* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include "string-inl.h" 18 19 #include "arch/memcmp16.h" 20 #include "array.h" 21 #include "base/array_ref.h" 22 #include "base/stl_util.h" 23 #include "class-inl.h" 24 #include "dex/descriptors_names.h" 25 #include "dex/utf-inl.h" 26 #include "gc/accounting/card_table-inl.h" 27 #include "gc_root-inl.h" 28 #include "handle_scope-inl.h" 29 #include "intern_table.h" 30 #include "object-inl.h" 31 #include "runtime.h" 32 #include "string-inl.h" 33 #include "thread.h" 34 35 namespace art { 36 namespace mirror { 37 38 // TODO: get global references for these 39 GcRoot<Class> String::java_lang_String_; 40 41 int32_t String::FastIndexOf(int32_t ch, int32_t start) { 42 int32_t count = GetLength(); 43 if (start < 0) { 44 start = 0; 45 } else if (start > count) { 46 start = count; 47 } 48 if (IsCompressed()) { 49 return FastIndexOf<uint8_t>(GetValueCompressed(), ch, start); 50 } else { 51 return FastIndexOf<uint16_t>(GetValue(), ch, start); 52 } 53 } 54 55 void String::SetClass(ObjPtr<Class> java_lang_String) { 56 CHECK(java_lang_String_.IsNull()); 57 CHECK(java_lang_String != nullptr); 58 CHECK(java_lang_String->IsStringClass()); 59 java_lang_String_ = GcRoot<Class>(java_lang_String); 60 } 61 62 void String::ResetClass() { 63 CHECK(!java_lang_String_.IsNull()); 64 java_lang_String_ = GcRoot<Class>(nullptr); 65 } 66 67 int String::ComputeHashCode() { 68 int32_t hash_code = 0; 69 if (IsCompressed()) { 70 hash_code = ComputeUtf16Hash(GetValueCompressed(), GetLength()); 71 } else { 72 hash_code = ComputeUtf16Hash(GetValue(), GetLength()); 73 } 74 SetHashCode(hash_code); 75 return hash_code; 76 } 77 78 int32_t String::GetUtfLength() { 79 if (IsCompressed()) { 80 return GetLength(); 81 } else { 82 return CountUtf8Bytes(GetValue(), GetLength()); 83 } 84 } 85 86 inline bool String::AllASCIIExcept(const uint16_t* chars, int32_t length, uint16_t non_ascii) { 87 DCHECK(!IsASCII(non_ascii)); 88 for (int32_t i = 0; i < length; ++i) { 89 if (!IsASCII(chars[i]) && chars[i] != non_ascii) { 90 return false; 91 } 92 } 93 return true; 94 } 95 96 ObjPtr<String> String::DoReplace(Thread* self, Handle<String> src, uint16_t old_c, uint16_t new_c) { 97 int32_t length = src->GetLength(); 98 DCHECK(src->IsCompressed() 99 ? ContainsElement(ArrayRef<uint8_t>(src->value_compressed_, length), old_c) 100 : ContainsElement(ArrayRef<uint16_t>(src->value_, length), old_c)); 101 bool compressible = 102 kUseStringCompression && 103 IsASCII(new_c) && 104 (src->IsCompressed() || (!IsASCII(old_c) && AllASCIIExcept(src->value_, length, old_c))); 105 gc::AllocatorType allocator_type = Runtime::Current()->GetHeap()->GetCurrentAllocator(); 106 const int32_t length_with_flag = String::GetFlaggedCount(length, compressible); 107 SetStringCountVisitor visitor(length_with_flag); 108 ObjPtr<String> string = Alloc<true>(self, length_with_flag, allocator_type, visitor); 109 if (UNLIKELY(string == nullptr)) { 110 return nullptr; 111 } 112 if (compressible) { 113 auto replace = [old_c, new_c](uint16_t c) { 114 return dchecked_integral_cast<uint8_t>((old_c != c) ? c : new_c); 115 }; 116 uint8_t* out = string->value_compressed_; 117 if (LIKELY(src->IsCompressed())) { // LIKELY(compressible == src->IsCompressed()) 118 std::transform(src->value_compressed_, src->value_compressed_ + length, out, replace); 119 } else { 120 std::transform(src->value_, src->value_ + length, out, replace); 121 } 122 DCHECK(kUseStringCompression && AllASCII(out, length)); 123 } else { 124 auto replace = [old_c, new_c](uint16_t c) { 125 return (old_c != c) ? c : new_c; 126 }; 127 uint16_t* out = string->value_; 128 if (UNLIKELY(src->IsCompressed())) { // LIKELY(compressible == src->IsCompressed()) 129 std::transform(src->value_compressed_, src->value_compressed_ + length, out, replace); 130 } else { 131 std::transform(src->value_, src->value_ + length, out, replace); 132 } 133 DCHECK(!kUseStringCompression || !AllASCII(out, length)); 134 } 135 return string; 136 } 137 138 String* String::AllocFromStrings(Thread* self, Handle<String> string, Handle<String> string2) { 139 int32_t length = string->GetLength(); 140 int32_t length2 = string2->GetLength(); 141 gc::AllocatorType allocator_type = Runtime::Current()->GetHeap()->GetCurrentAllocator(); 142 const bool compressible = kUseStringCompression && 143 (string->IsCompressed() && string2->IsCompressed()); 144 const int32_t length_with_flag = String::GetFlaggedCount(length + length2, compressible); 145 146 SetStringCountVisitor visitor(length_with_flag); 147 ObjPtr<String> new_string = Alloc<true>(self, length_with_flag, allocator_type, visitor); 148 if (UNLIKELY(new_string == nullptr)) { 149 return nullptr; 150 } 151 if (compressible) { 152 uint8_t* new_value = new_string->GetValueCompressed(); 153 memcpy(new_value, string->GetValueCompressed(), length * sizeof(uint8_t)); 154 memcpy(new_value + length, string2->GetValueCompressed(), length2 * sizeof(uint8_t)); 155 } else { 156 uint16_t* new_value = new_string->GetValue(); 157 if (string->IsCompressed()) { 158 for (int i = 0; i < length; ++i) { 159 new_value[i] = string->CharAt(i); 160 } 161 } else { 162 memcpy(new_value, string->GetValue(), length * sizeof(uint16_t)); 163 } 164 if (string2->IsCompressed()) { 165 for (int i = 0; i < length2; ++i) { 166 new_value[i+length] = string2->CharAt(i); 167 } 168 } else { 169 memcpy(new_value + length, string2->GetValue(), length2 * sizeof(uint16_t)); 170 } 171 } 172 return new_string.Ptr(); 173 } 174 175 String* String::AllocFromUtf16(Thread* self, int32_t utf16_length, const uint16_t* utf16_data_in) { 176 CHECK(utf16_data_in != nullptr || utf16_length == 0); 177 gc::AllocatorType allocator_type = Runtime::Current()->GetHeap()->GetCurrentAllocator(); 178 const bool compressible = kUseStringCompression && 179 String::AllASCII<uint16_t>(utf16_data_in, utf16_length); 180 int32_t length_with_flag = String::GetFlaggedCount(utf16_length, compressible); 181 SetStringCountVisitor visitor(length_with_flag); 182 ObjPtr<String> string = Alloc<true>(self, length_with_flag, allocator_type, visitor); 183 if (UNLIKELY(string == nullptr)) { 184 return nullptr; 185 } 186 if (compressible) { 187 for (int i = 0; i < utf16_length; ++i) { 188 string->GetValueCompressed()[i] = static_cast<uint8_t>(utf16_data_in[i]); 189 } 190 } else { 191 uint16_t* array = string->GetValue(); 192 memcpy(array, utf16_data_in, utf16_length * sizeof(uint16_t)); 193 } 194 return string.Ptr(); 195 } 196 197 String* String::AllocFromModifiedUtf8(Thread* self, const char* utf) { 198 DCHECK(utf != nullptr); 199 size_t byte_count = strlen(utf); 200 size_t char_count = CountModifiedUtf8Chars(utf, byte_count); 201 return AllocFromModifiedUtf8(self, char_count, utf, byte_count); 202 } 203 204 String* String::AllocFromModifiedUtf8(Thread* self, 205 int32_t utf16_length, 206 const char* utf8_data_in) { 207 return AllocFromModifiedUtf8(self, utf16_length, utf8_data_in, strlen(utf8_data_in)); 208 } 209 210 String* String::AllocFromModifiedUtf8(Thread* self, 211 int32_t utf16_length, 212 const char* utf8_data_in, 213 int32_t utf8_length) { 214 gc::AllocatorType allocator_type = Runtime::Current()->GetHeap()->GetCurrentAllocator(); 215 const bool compressible = kUseStringCompression && (utf16_length == utf8_length); 216 const int32_t utf16_length_with_flag = String::GetFlaggedCount(utf16_length, compressible); 217 SetStringCountVisitor visitor(utf16_length_with_flag); 218 ObjPtr<String> string = Alloc<true>(self, utf16_length_with_flag, allocator_type, visitor); 219 if (UNLIKELY(string == nullptr)) { 220 return nullptr; 221 } 222 if (compressible) { 223 memcpy(string->GetValueCompressed(), utf8_data_in, utf16_length * sizeof(uint8_t)); 224 } else { 225 uint16_t* utf16_data_out = string->GetValue(); 226 ConvertModifiedUtf8ToUtf16(utf16_data_out, utf16_length, utf8_data_in, utf8_length); 227 } 228 return string.Ptr(); 229 } 230 231 bool String::Equals(ObjPtr<String> that) { 232 if (this == that) { 233 // Quick reference equality test 234 return true; 235 } else if (that == nullptr) { 236 // Null isn't an instanceof anything 237 return false; 238 } else if (this->GetLength() != that->GetLength()) { 239 // Quick length inequality test 240 return false; 241 } else { 242 // Note: don't short circuit on hash code as we're presumably here as the 243 // hash code was already equal 244 for (int32_t i = 0; i < that->GetLength(); ++i) { 245 if (this->CharAt(i) != that->CharAt(i)) { 246 return false; 247 } 248 } 249 return true; 250 } 251 } 252 253 bool String::Equals(const uint16_t* that_chars, int32_t that_offset, int32_t that_length) { 254 if (this->GetLength() != that_length) { 255 return false; 256 } else { 257 for (int32_t i = 0; i < that_length; ++i) { 258 if (this->CharAt(i) != that_chars[that_offset + i]) { 259 return false; 260 } 261 } 262 return true; 263 } 264 } 265 266 bool String::Equals(const char* modified_utf8) { 267 const int32_t length = GetLength(); 268 int32_t i = 0; 269 while (i < length) { 270 const uint32_t ch = GetUtf16FromUtf8(&modified_utf8); 271 if (ch == '\0') { 272 return false; 273 } 274 275 if (GetLeadingUtf16Char(ch) != CharAt(i++)) { 276 return false; 277 } 278 279 const uint16_t trailing = GetTrailingUtf16Char(ch); 280 if (trailing != 0) { 281 if (i == length) { 282 return false; 283 } 284 285 if (CharAt(i++) != trailing) { 286 return false; 287 } 288 } 289 } 290 return *modified_utf8 == '\0'; 291 } 292 293 bool String::Equals(const StringPiece& modified_utf8) { 294 const int32_t length = GetLength(); 295 const char* p = modified_utf8.data(); 296 for (int32_t i = 0; i < length; ++i) { 297 uint32_t ch = GetUtf16FromUtf8(&p); 298 299 if (GetLeadingUtf16Char(ch) != CharAt(i)) { 300 return false; 301 } 302 303 const uint16_t trailing = GetTrailingUtf16Char(ch); 304 if (trailing != 0) { 305 if (i == (length - 1)) { 306 return false; 307 } 308 309 if (CharAt(++i) != trailing) { 310 return false; 311 } 312 } 313 } 314 return true; 315 } 316 317 // Create a modified UTF-8 encoded std::string from a java/lang/String object. 318 std::string String::ToModifiedUtf8() { 319 size_t byte_count = GetUtfLength(); 320 std::string result(byte_count, static_cast<char>(0)); 321 if (IsCompressed()) { 322 for (size_t i = 0; i < byte_count; ++i) { 323 result[i] = static_cast<char>(CharAt(i)); 324 } 325 } else { 326 const uint16_t* chars = GetValue(); 327 ConvertUtf16ToModifiedUtf8(&result[0], byte_count, chars, GetLength()); 328 } 329 return result; 330 } 331 332 int32_t String::CompareTo(ObjPtr<String> rhs) { 333 // Quick test for comparison of a string with itself. 334 ObjPtr<String> lhs = this; 335 if (lhs == rhs) { 336 return 0; 337 } 338 int32_t lhs_count = lhs->GetLength(); 339 int32_t rhs_count = rhs->GetLength(); 340 int32_t count_diff = lhs_count - rhs_count; 341 int32_t min_count = (count_diff < 0) ? lhs_count : rhs_count; 342 if (lhs->IsCompressed() && rhs->IsCompressed()) { 343 const uint8_t* lhs_chars = lhs->GetValueCompressed(); 344 const uint8_t* rhs_chars = rhs->GetValueCompressed(); 345 for (int32_t i = 0; i < min_count; ++i) { 346 int32_t char_diff = static_cast<int32_t>(lhs_chars[i]) - static_cast<int32_t>(rhs_chars[i]); 347 if (char_diff != 0) { 348 return char_diff; 349 } 350 } 351 } else if (lhs->IsCompressed() || rhs->IsCompressed()) { 352 const uint8_t* compressed_chars = 353 lhs->IsCompressed() ? lhs->GetValueCompressed() : rhs->GetValueCompressed(); 354 const uint16_t* uncompressed_chars = lhs->IsCompressed() ? rhs->GetValue() : lhs->GetValue(); 355 for (int32_t i = 0; i < min_count; ++i) { 356 int32_t char_diff = 357 static_cast<int32_t>(compressed_chars[i]) - static_cast<int32_t>(uncompressed_chars[i]); 358 if (char_diff != 0) { 359 return lhs->IsCompressed() ? char_diff : -char_diff; 360 } 361 } 362 } else { 363 const uint16_t* lhs_chars = lhs->GetValue(); 364 const uint16_t* rhs_chars = rhs->GetValue(); 365 // FIXME: The MemCmp16() name is misleading. It returns the char difference on mismatch 366 // where memcmp() only guarantees that the returned value has the same sign. 367 int32_t char_diff = MemCmp16(lhs_chars, rhs_chars, min_count); 368 if (char_diff != 0) { 369 return char_diff; 370 } 371 } 372 return count_diff; 373 } 374 375 void String::VisitRoots(RootVisitor* visitor) { 376 java_lang_String_.VisitRootIfNonNull(visitor, RootInfo(kRootStickyClass)); 377 } 378 379 CharArray* String::ToCharArray(Thread* self) { 380 StackHandleScope<1> hs(self); 381 Handle<String> string(hs.NewHandle(this)); 382 ObjPtr<CharArray> result = CharArray::Alloc(self, GetLength()); 383 if (result != nullptr) { 384 if (string->IsCompressed()) { 385 int32_t length = string->GetLength(); 386 for (int i = 0; i < length; ++i) { 387 result->GetData()[i] = string->CharAt(i); 388 } 389 } else { 390 memcpy(result->GetData(), string->GetValue(), string->GetLength() * sizeof(uint16_t)); 391 } 392 } else { 393 self->AssertPendingOOMException(); 394 } 395 return result.Ptr(); 396 } 397 398 void String::GetChars(int32_t start, int32_t end, Handle<CharArray> array, int32_t index) { 399 uint16_t* data = array->GetData() + index; 400 if (IsCompressed()) { 401 for (int i = start; i < end; ++i) { 402 data[i-start] = CharAt(i); 403 } 404 } else { 405 uint16_t* value = GetValue() + start; 406 memcpy(data, value, (end - start) * sizeof(uint16_t)); 407 } 408 } 409 410 bool String::IsValueNull() { 411 return (IsCompressed()) ? (GetValueCompressed() == nullptr) : (GetValue() == nullptr); 412 } 413 414 std::string String::PrettyStringDescriptor(ObjPtr<mirror::String> java_descriptor) { 415 if (java_descriptor == nullptr) { 416 return "null"; 417 } 418 return java_descriptor->PrettyStringDescriptor(); 419 } 420 421 std::string String::PrettyStringDescriptor() { 422 return PrettyDescriptor(ToModifiedUtf8().c_str()); 423 } 424 425 ObjPtr<String> String::Intern() { 426 return Runtime::Current()->GetInternTable()->InternWeak(this); 427 } 428 429 } // namespace mirror 430 } // namespace art 431