OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/runtime/runtime-utils.h" | 5 #include "src/runtime/runtime-utils.h" |
6 | 6 |
7 #include "src/arguments.h" | 7 #include "src/arguments.h" |
8 #include "src/regexp/jsregexp-inl.h" | 8 #include "src/regexp/jsregexp-inl.h" |
9 #include "src/string-builder.h" | 9 #include "src/string-builder.h" |
10 #include "src/string-search.h" | 10 #include "src/string-search.h" |
(...skipping 778 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
789 #ifdef DEBUG | 789 #ifdef DEBUG |
790 for (int i = 0; i < length; ++i) { | 790 for (int i = 0; i < length; ++i) { |
791 DCHECK(String::cast(elements->get(i))->length() == 1); | 791 DCHECK(String::cast(elements->get(i))->length() == 1); |
792 } | 792 } |
793 #endif | 793 #endif |
794 | 794 |
795 return *isolate->factory()->NewJSArrayWithElements(elements); | 795 return *isolate->factory()->NewJSArrayWithElements(elements); |
796 } | 796 } |
797 | 797 |
798 | 798 |
799 static inline bool ToUpperOverflows(uc32 character) { | |
800 // y with umlauts and the micro sign are the only characters that stop | |
801 // fitting into one-byte when converting to uppercase. | |
802 static const uc32 yuml_code = 0xff; | |
803 static const uc32 micro_code = 0xb5; | |
804 return (character == yuml_code || character == micro_code); | |
805 } | |
806 | |
807 | |
808 template <class Converter> | |
809 MUST_USE_RESULT static Object* ConvertCaseHelper( | |
810 Isolate* isolate, String* string, SeqString* result, int result_length, | |
811 unibrow::Mapping<Converter, 128>* mapping) { | |
812 DisallowHeapAllocation no_gc; | |
813 // We try this twice, once with the assumption that the result is no longer | |
814 // than the input and, if that assumption breaks, again with the exact | |
815 // length. This may not be pretty, but it is nicer than what was here before | |
816 // and I hereby claim my vaffel-is. | |
817 // | |
818 // NOTE: This assumes that the upper/lower case of an ASCII | |
819 // character is also ASCII. This is currently the case, but it | |
820 // might break in the future if we implement more context and locale | |
821 // dependent upper/lower conversions. | |
822 bool has_changed_character = false; | |
823 | |
824 // Convert all characters to upper case, assuming that they will fit | |
825 // in the buffer | |
826 StringCharacterStream stream(string); | |
827 unibrow::uchar chars[Converter::kMaxWidth]; | |
828 // We can assume that the string is not empty | |
829 uc32 current = stream.GetNext(); | |
830 bool ignore_overflow = Converter::kIsToLower || result->IsSeqTwoByteString(); | |
831 for (int i = 0; i < result_length;) { | |
832 bool has_next = stream.HasMore(); | |
833 uc32 next = has_next ? stream.GetNext() : 0; | |
834 int char_length = mapping->get(current, next, chars); | |
835 if (char_length == 0) { | |
836 // The case conversion of this character is the character itself. | |
837 result->Set(i, current); | |
838 i++; | |
839 } else if (char_length == 1 && | |
840 (ignore_overflow || !ToUpperOverflows(current))) { | |
841 // Common case: converting the letter resulted in one character. | |
842 DCHECK(static_cast<uc32>(chars[0]) != current); | |
843 result->Set(i, chars[0]); | |
844 has_changed_character = true; | |
845 i++; | |
846 } else if (result_length == string->length()) { | |
847 bool overflows = ToUpperOverflows(current); | |
848 // We've assumed that the result would be as long as the | |
849 // input but here is a character that converts to several | |
850 // characters. No matter, we calculate the exact length | |
851 // of the result and try the whole thing again. | |
852 // | |
853 // Note that this leaves room for optimization. We could just | |
854 // memcpy what we already have to the result string. Also, | |
855 // the result string is the last object allocated we could | |
856 // "realloc" it and probably, in the vast majority of cases, | |
857 // extend the existing string to be able to hold the full | |
858 // result. | |
859 int next_length = 0; | |
860 if (has_next) { | |
861 next_length = mapping->get(next, 0, chars); | |
862 if (next_length == 0) next_length = 1; | |
863 } | |
864 int current_length = i + char_length + next_length; | |
865 while (stream.HasMore()) { | |
866 current = stream.GetNext(); | |
867 overflows |= ToUpperOverflows(current); | |
868 // NOTE: we use 0 as the next character here because, while | |
869 // the next character may affect what a character converts to, | |
870 // it does not in any case affect the length of what it convert | |
871 // to. | |
872 int char_length = mapping->get(current, 0, chars); | |
873 if (char_length == 0) char_length = 1; | |
874 current_length += char_length; | |
875 if (current_length > String::kMaxLength) { | |
876 AllowHeapAllocation allocate_error_and_return; | |
877 THROW_NEW_ERROR_RETURN_FAILURE(isolate, | |
878 NewInvalidStringLengthError()); | |
879 } | |
880 } | |
881 // Try again with the real length. Return signed if we need | |
882 // to allocate a two-byte string for to uppercase. | |
883 return (overflows && !ignore_overflow) ? Smi::FromInt(-current_length) | |
884 : Smi::FromInt(current_length); | |
885 } else { | |
886 for (int j = 0; j < char_length; j++) { | |
887 result->Set(i, chars[j]); | |
888 i++; | |
889 } | |
890 has_changed_character = true; | |
891 } | |
892 current = next; | |
893 } | |
894 if (has_changed_character) { | |
895 return result; | |
896 } else { | |
897 // If we didn't actually change anything in doing the conversion | |
898 // we simple return the result and let the converted string | |
899 // become garbage; there is no reason to keep two identical strings | |
900 // alive. | |
901 return string; | |
902 } | |
903 } | |
904 | |
905 | |
906 static const uintptr_t kOneInEveryByte = kUintptrAllBitsSet / 0xFF; | |
907 static const uintptr_t kAsciiMask = kOneInEveryByte << 7; | |
908 | |
909 // Given a word and two range boundaries returns a word with high bit | |
910 // set in every byte iff the corresponding input byte was strictly in | |
911 // the range (m, n). All the other bits in the result are cleared. | |
912 // This function is only useful when it can be inlined and the | |
913 // boundaries are statically known. | |
914 // Requires: all bytes in the input word and the boundaries must be | |
915 // ASCII (less than 0x7F). | |
916 static inline uintptr_t AsciiRangeMask(uintptr_t w, char m, char n) { | |
917 // Use strict inequalities since in edge cases the function could be | |
918 // further simplified. | |
919 DCHECK(0 < m && m < n); | |
920 // Has high bit set in every w byte less than n. | |
921 uintptr_t tmp1 = kOneInEveryByte * (0x7F + n) - w; | |
922 // Has high bit set in every w byte greater than m. | |
923 uintptr_t tmp2 = w + kOneInEveryByte * (0x7F - m); | |
924 return (tmp1 & tmp2 & (kOneInEveryByte * 0x80)); | |
925 } | |
926 | |
927 | |
928 #ifdef DEBUG | |
929 static bool CheckFastAsciiConvert(char* dst, const char* src, int length, | |
930 bool changed, bool is_to_lower) { | |
931 bool expected_changed = false; | |
932 for (int i = 0; i < length; i++) { | |
933 if (dst[i] == src[i]) continue; | |
934 expected_changed = true; | |
935 if (is_to_lower) { | |
936 DCHECK('A' <= src[i] && src[i] <= 'Z'); | |
937 DCHECK(dst[i] == src[i] + ('a' - 'A')); | |
938 } else { | |
939 DCHECK('a' <= src[i] && src[i] <= 'z'); | |
940 DCHECK(dst[i] == src[i] - ('a' - 'A')); | |
941 } | |
942 } | |
943 return (expected_changed == changed); | |
944 } | |
945 #endif | |
946 | |
947 | |
948 template <class Converter> | |
949 static bool FastAsciiConvert(char* dst, const char* src, int length, | |
950 bool* changed_out) { | |
951 #ifdef DEBUG | |
952 char* saved_dst = dst; | |
953 const char* saved_src = src; | |
954 #endif | |
955 DisallowHeapAllocation no_gc; | |
956 // We rely on the distance between upper and lower case letters | |
957 // being a known power of 2. | |
958 DCHECK('a' - 'A' == (1 << 5)); | |
959 // Boundaries for the range of input characters than require conversion. | |
960 static const char lo = Converter::kIsToLower ? 'A' - 1 : 'a' - 1; | |
961 static const char hi = Converter::kIsToLower ? 'Z' + 1 : 'z' + 1; | |
962 bool changed = false; | |
963 uintptr_t or_acc = 0; | |
964 const char* const limit = src + length; | |
965 | |
966 // dst is newly allocated and always aligned. | |
967 DCHECK(IsAligned(reinterpret_cast<intptr_t>(dst), sizeof(uintptr_t))); | |
968 // Only attempt processing one word at a time if src is also aligned. | |
969 if (IsAligned(reinterpret_cast<intptr_t>(src), sizeof(uintptr_t))) { | |
970 // Process the prefix of the input that requires no conversion one aligned | |
971 // (machine) word at a time. | |
972 while (src <= limit - sizeof(uintptr_t)) { | |
973 const uintptr_t w = *reinterpret_cast<const uintptr_t*>(src); | |
974 or_acc |= w; | |
975 if (AsciiRangeMask(w, lo, hi) != 0) { | |
976 changed = true; | |
977 break; | |
978 } | |
979 *reinterpret_cast<uintptr_t*>(dst) = w; | |
980 src += sizeof(uintptr_t); | |
981 dst += sizeof(uintptr_t); | |
982 } | |
983 // Process the remainder of the input performing conversion when | |
984 // required one word at a time. | |
985 while (src <= limit - sizeof(uintptr_t)) { | |
986 const uintptr_t w = *reinterpret_cast<const uintptr_t*>(src); | |
987 or_acc |= w; | |
988 uintptr_t m = AsciiRangeMask(w, lo, hi); | |
989 // The mask has high (7th) bit set in every byte that needs | |
990 // conversion and we know that the distance between cases is | |
991 // 1 << 5. | |
992 *reinterpret_cast<uintptr_t*>(dst) = w ^ (m >> 2); | |
993 src += sizeof(uintptr_t); | |
994 dst += sizeof(uintptr_t); | |
995 } | |
996 } | |
997 // Process the last few bytes of the input (or the whole input if | |
998 // unaligned access is not supported). | |
999 while (src < limit) { | |
1000 char c = *src; | |
1001 or_acc |= c; | |
1002 if (lo < c && c < hi) { | |
1003 c ^= (1 << 5); | |
1004 changed = true; | |
1005 } | |
1006 *dst = c; | |
1007 ++src; | |
1008 ++dst; | |
1009 } | |
1010 | |
1011 if ((or_acc & kAsciiMask) != 0) return false; | |
1012 | |
1013 DCHECK(CheckFastAsciiConvert(saved_dst, saved_src, length, changed, | |
1014 Converter::kIsToLower)); | |
1015 | |
1016 *changed_out = changed; | |
1017 return true; | |
1018 } | |
1019 | |
1020 | |
1021 template <class Converter> | |
1022 MUST_USE_RESULT static Object* ConvertCase( | |
1023 Handle<String> s, Isolate* isolate, | |
1024 unibrow::Mapping<Converter, 128>* mapping) { | |
1025 s = String::Flatten(s); | |
1026 int length = s->length(); | |
1027 // Assume that the string is not empty; we need this assumption later | |
1028 if (length == 0) return *s; | |
1029 | |
1030 // Simpler handling of ASCII strings. | |
1031 // | |
1032 // NOTE: This assumes that the upper/lower case of an ASCII | |
1033 // character is also ASCII. This is currently the case, but it | |
1034 // might break in the future if we implement more context and locale | |
1035 // dependent upper/lower conversions. | |
1036 if (s->IsOneByteRepresentationUnderneath()) { | |
1037 // Same length as input. | |
1038 Handle<SeqOneByteString> result = | |
1039 isolate->factory()->NewRawOneByteString(length).ToHandleChecked(); | |
1040 DisallowHeapAllocation no_gc; | |
1041 String::FlatContent flat_content = s->GetFlatContent(); | |
1042 DCHECK(flat_content.IsFlat()); | |
1043 bool has_changed_character = false; | |
1044 bool is_ascii = FastAsciiConvert<Converter>( | |
1045 reinterpret_cast<char*>(result->GetChars()), | |
1046 reinterpret_cast<const char*>(flat_content.ToOneByteVector().start()), | |
1047 length, &has_changed_character); | |
1048 // If not ASCII, we discard the result and take the 2 byte path. | |
1049 if (is_ascii) return has_changed_character ? *result : *s; | |
1050 } | |
1051 | |
1052 Handle<SeqString> result; // Same length as input. | |
1053 if (s->IsOneByteRepresentation()) { | |
1054 result = isolate->factory()->NewRawOneByteString(length).ToHandleChecked(); | |
1055 } else { | |
1056 result = isolate->factory()->NewRawTwoByteString(length).ToHandleChecked(); | |
1057 } | |
1058 | |
1059 Object* answer = ConvertCaseHelper(isolate, *s, *result, length, mapping); | |
1060 if (answer->IsException() || answer->IsString()) return answer; | |
1061 | |
1062 DCHECK(answer->IsSmi()); | |
1063 length = Smi::cast(answer)->value(); | |
1064 if (s->IsOneByteRepresentation() && length > 0) { | |
1065 ASSIGN_RETURN_FAILURE_ON_EXCEPTION( | |
1066 isolate, result, isolate->factory()->NewRawOneByteString(length)); | |
1067 } else { | |
1068 if (length < 0) length = -length; | |
1069 ASSIGN_RETURN_FAILURE_ON_EXCEPTION( | |
1070 isolate, result, isolate->factory()->NewRawTwoByteString(length)); | |
1071 } | |
1072 return ConvertCaseHelper(isolate, *s, *result, length, mapping); | |
1073 } | |
1074 | |
1075 | |
1076 RUNTIME_FUNCTION(Runtime_StringToLowerCase) { | |
1077 HandleScope scope(isolate); | |
1078 DCHECK_EQ(args.length(), 1); | |
1079 CONVERT_ARG_HANDLE_CHECKED(String, s, 0); | |
1080 return ConvertCase(s, isolate, isolate->runtime_state()->to_lower_mapping()); | |
1081 } | |
1082 | |
1083 | |
1084 RUNTIME_FUNCTION(Runtime_StringToUpperCase) { | |
1085 HandleScope scope(isolate); | |
1086 DCHECK_EQ(args.length(), 1); | |
1087 CONVERT_ARG_HANDLE_CHECKED(String, s, 0); | |
1088 return ConvertCase(s, isolate, isolate->runtime_state()->to_upper_mapping()); | |
1089 } | |
1090 | |
1091 RUNTIME_FUNCTION(Runtime_StringLessThan) { | 799 RUNTIME_FUNCTION(Runtime_StringLessThan) { |
1092 HandleScope handle_scope(isolate); | 800 HandleScope handle_scope(isolate); |
1093 DCHECK_EQ(2, args.length()); | 801 DCHECK_EQ(2, args.length()); |
1094 CONVERT_ARG_HANDLE_CHECKED(String, x, 0); | 802 CONVERT_ARG_HANDLE_CHECKED(String, x, 0); |
1095 CONVERT_ARG_HANDLE_CHECKED(String, y, 1); | 803 CONVERT_ARG_HANDLE_CHECKED(String, y, 1); |
1096 switch (String::Compare(x, y)) { | 804 switch (String::Compare(x, y)) { |
1097 case ComparisonResult::kLessThan: | 805 case ComparisonResult::kLessThan: |
1098 return isolate->heap()->true_value(); | 806 return isolate->heap()->true_value(); |
1099 case ComparisonResult::kEqual: | 807 case ComparisonResult::kEqual: |
1100 case ComparisonResult::kGreaterThan: | 808 case ComparisonResult::kGreaterThan: |
(...skipping 106 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1207 SealHandleScope shs(isolate); | 915 SealHandleScope shs(isolate); |
1208 DCHECK(args.length() == 2); | 916 DCHECK(args.length() == 2); |
1209 if (!args[0]->IsString()) return isolate->heap()->undefined_value(); | 917 if (!args[0]->IsString()) return isolate->heap()->undefined_value(); |
1210 if (!args[1]->IsNumber()) return isolate->heap()->undefined_value(); | 918 if (!args[1]->IsNumber()) return isolate->heap()->undefined_value(); |
1211 if (std::isinf(args.number_at(1))) return isolate->heap()->nan_value(); | 919 if (std::isinf(args.number_at(1))) return isolate->heap()->nan_value(); |
1212 return __RT_impl_Runtime_StringCharCodeAtRT(args, isolate); | 920 return __RT_impl_Runtime_StringCharCodeAtRT(args, isolate); |
1213 } | 921 } |
1214 | 922 |
1215 } // namespace internal | 923 } // namespace internal |
1216 } // namespace v8 | 924 } // namespace v8 |
OLD | NEW |