| OLD | NEW |
| 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. |
| 2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
| 3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
| 4 // met: | 4 // met: |
| 5 // | 5 // |
| 6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
| 7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
| 8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
| 9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
| 10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
| (...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 94 | 94 |
| 95 static Object* Runtime_CloneObjectLiteralBoilerplate(Arguments args) { | 95 static Object* Runtime_CloneObjectLiteralBoilerplate(Arguments args) { |
| 96 CONVERT_CHECKED(JSObject, boilerplate, args[0]); | 96 CONVERT_CHECKED(JSObject, boilerplate, args[0]); |
| 97 return Heap::CopyJSObject(boilerplate); | 97 return Heap::CopyJSObject(boilerplate); |
| 98 } | 98 } |
| 99 | 99 |
| 100 | 100 |
| 101 static Handle<Map> ComputeObjectLiteralMap( | 101 static Handle<Map> ComputeObjectLiteralMap( |
| 102 Handle<Context> context, | 102 Handle<Context> context, |
| 103 Handle<FixedArray> constant_properties, | 103 Handle<FixedArray> constant_properties, |
| 104 bool &is_result_from_cache) { | 104 bool* is_result_from_cache) { |
| 105 if (FLAG_canonicalize_object_literal_maps) { | 105 if (FLAG_canonicalize_object_literal_maps) { |
| 106 // First find prefix of consecutive symbol keys. | 106 // First find prefix of consecutive symbol keys. |
| 107 int number_of_properties = constant_properties->length()/2; | 107 int number_of_properties = constant_properties->length()/2; |
| 108 int number_of_symbol_keys = 0; | 108 int number_of_symbol_keys = 0; |
| 109 while ((number_of_symbol_keys < number_of_properties) && | 109 while ((number_of_symbol_keys < number_of_properties) && |
| 110 (constant_properties->get(number_of_symbol_keys*2)->IsSymbol())) { | 110 (constant_properties->get(number_of_symbol_keys*2)->IsSymbol())) { |
| 111 number_of_symbol_keys++; | 111 number_of_symbol_keys++; |
| 112 } | 112 } |
| 113 // Based on the number of prefix symbols key we decide whether | 113 // Based on the number of prefix symbols key we decide whether |
| 114 // to use the map cache in the global context. | 114 // to use the map cache in the global context. |
| 115 const int kMaxKeys = 10; | 115 const int kMaxKeys = 10; |
| 116 if ((number_of_symbol_keys == number_of_properties) | 116 if ((number_of_symbol_keys == number_of_properties) |
| 117 && (number_of_symbol_keys < kMaxKeys)) { | 117 && (number_of_symbol_keys < kMaxKeys)) { |
| 118 // Create the fixed array with the key. | 118 // Create the fixed array with the key. |
| 119 Handle<FixedArray> keys = Factory::NewFixedArray(number_of_symbol_keys); | 119 Handle<FixedArray> keys = Factory::NewFixedArray(number_of_symbol_keys); |
| 120 for (int i = 0; i < number_of_symbol_keys; i++) { | 120 for (int i = 0; i < number_of_symbol_keys; i++) { |
| 121 keys->set(i, constant_properties->get(i*2)); | 121 keys->set(i, constant_properties->get(i*2)); |
| 122 } | 122 } |
| 123 is_result_from_cache = true; | 123 *is_result_from_cache = true; |
| 124 return Factory::ObjectLiteralMapFromCache(context, keys); | 124 return Factory::ObjectLiteralMapFromCache(context, keys); |
| 125 } | 125 } |
| 126 } | 126 } |
| 127 is_result_from_cache = false; | 127 *is_result_from_cache = false; |
| 128 return Handle<Map>(context->object_function()->initial_map()); | 128 return Handle<Map>(context->object_function()->initial_map()); |
| 129 } | 129 } |
| 130 | 130 |
| 131 | 131 |
| 132 static Object* Runtime_CreateObjectLiteralBoilerplate(Arguments args) { | 132 static Object* Runtime_CreateObjectLiteralBoilerplate(Arguments args) { |
| 133 HandleScope scope; | 133 HandleScope scope; |
| 134 ASSERT(args.length() == 3); | 134 ASSERT(args.length() == 3); |
| 135 // Copy the arguments. | 135 // Copy the arguments. |
| 136 Handle<FixedArray> literals = args.at<FixedArray>(0); | 136 Handle<FixedArray> literals = args.at<FixedArray>(0); |
| 137 int literals_index = Smi::cast(args[1])->value(); | 137 int literals_index = Smi::cast(args[1])->value(); |
| 138 Handle<FixedArray> constant_properties = args.at<FixedArray>(2); | 138 Handle<FixedArray> constant_properties = args.at<FixedArray>(2); |
| 139 | 139 |
| 140 // Get the global context from the literals array. This is the | 140 // Get the global context from the literals array. This is the |
| 141 // context in which the function was created and we use the object | 141 // context in which the function was created and we use the object |
| 142 // function from this context to create the object literal. We do | 142 // function from this context to create the object literal. We do |
| 143 // not use the object function from the current global context | 143 // not use the object function from the current global context |
| 144 // because this might be the object function from another context | 144 // because this might be the object function from another context |
| 145 // which we should not have access to. | 145 // which we should not have access to. |
| 146 Handle<Context> context = | 146 Handle<Context> context = |
| 147 Handle<Context>(JSFunction::GlobalContextFromLiterals(*literals)); | 147 Handle<Context>(JSFunction::GlobalContextFromLiterals(*literals)); |
| 148 | 148 |
| 149 bool is_result_from_cache; | 149 bool is_result_from_cache; |
| 150 Handle<Map> map = ComputeObjectLiteralMap(context, | 150 Handle<Map> map = ComputeObjectLiteralMap(context, |
| 151 constant_properties, | 151 constant_properties, |
| 152 is_result_from_cache); | 152 &is_result_from_cache); |
| 153 | 153 |
| 154 Handle<JSObject> boilerplate = Factory::NewJSObjectFromMap(map); | 154 Handle<JSObject> boilerplate = Factory::NewJSObjectFromMap(map); |
| 155 { // Add the constant propeties to the boilerplate. | 155 { // Add the constant propeties to the boilerplate. |
| 156 int length = constant_properties->length(); | 156 int length = constant_properties->length(); |
| 157 OptimizedObjectForAddingMultipleProperties opt(boilerplate, | 157 OptimizedObjectForAddingMultipleProperties opt(boilerplate, |
| 158 !is_result_from_cache); | 158 !is_result_from_cache); |
| 159 for (int index = 0; index < length; index +=2) { | 159 for (int index = 0; index < length; index +=2) { |
| 160 Handle<Object> key(constant_properties->get(index+0)); | 160 Handle<Object> key(constant_properties->get(index+0)); |
| 161 Handle<Object> value(constant_properties->get(index+1)); | 161 Handle<Object> value(constant_properties->get(index+1)); |
| 162 uint32_t element_index = 0; | 162 uint32_t element_index = 0; |
| (...skipping 844 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1007 ASSERT(biased_suffixes_ + index >= suffixes_); | 1007 ASSERT(biased_suffixes_ + index >= suffixes_); |
| 1008 return biased_suffixes_[index]; | 1008 return biased_suffixes_[index]; |
| 1009 } | 1009 } |
| 1010 inline int& shift(int index) { | 1010 inline int& shift(int index) { |
| 1011 ASSERT(biased_good_suffix_shift_ + index >= good_suffix_shift_); | 1011 ASSERT(biased_good_suffix_shift_ + index >= good_suffix_shift_); |
| 1012 return biased_good_suffix_shift_[index]; | 1012 return biased_good_suffix_shift_[index]; |
| 1013 } | 1013 } |
| 1014 private: | 1014 private: |
| 1015 int suffixes_[kBMMaxShift + 1]; | 1015 int suffixes_[kBMMaxShift + 1]; |
| 1016 int good_suffix_shift_[kBMMaxShift + 1]; | 1016 int good_suffix_shift_[kBMMaxShift + 1]; |
| 1017 int *biased_suffixes_; | 1017 int* biased_suffixes_; |
| 1018 int *biased_good_suffix_shift_; | 1018 int* biased_good_suffix_shift_; |
| 1019 DISALLOW_COPY_AND_ASSIGN(BMGoodSuffixBuffers); | 1019 DISALLOW_COPY_AND_ASSIGN(BMGoodSuffixBuffers); |
| 1020 }; | 1020 }; |
| 1021 | 1021 |
| 1022 // buffers reused by BoyerMoore | 1022 // buffers reused by BoyerMoore |
| 1023 static int bad_char_occurence[kBMAlphabetSize]; | 1023 static int bad_char_occurence[kBMAlphabetSize]; |
| 1024 static BMGoodSuffixBuffers bmgs_buffers; | 1024 static BMGoodSuffixBuffers bmgs_buffers; |
| 1025 | 1025 |
| 1026 // Compute the bad-char table for Boyer-Moore in the static buffer. | 1026 // Compute the bad-char table for Boyer-Moore in the static buffer. |
| 1027 template <typename pchar> | 1027 template <typename pchar> |
| 1028 static void BoyerMoorePopulateBadCharTable(Vector<const pchar> pattern, | 1028 static void BoyerMoorePopulateBadCharTable(Vector<const pchar> pattern, |
| (...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1111 } | 1111 } |
| 1112 | 1112 |
| 1113 // Restricted simplified Boyer-Moore string matching. Restricts tables to a | 1113 // Restricted simplified Boyer-Moore string matching. Restricts tables to a |
| 1114 // suffix of long pattern strings and handles only equivalence classes | 1114 // suffix of long pattern strings and handles only equivalence classes |
| 1115 // of the full alphabet. This allows us to ensure that tables take only | 1115 // of the full alphabet. This allows us to ensure that tables take only |
| 1116 // a fixed amount of space. | 1116 // a fixed amount of space. |
| 1117 template <typename schar, typename pchar> | 1117 template <typename schar, typename pchar> |
| 1118 static int BoyerMooreSimplified(Vector<const schar> subject, | 1118 static int BoyerMooreSimplified(Vector<const schar> subject, |
| 1119 Vector<const pchar> pattern, | 1119 Vector<const pchar> pattern, |
| 1120 int start_index, | 1120 int start_index, |
| 1121 bool& complete) { | 1121 bool* complete) { |
| 1122 int n = subject.length(); | 1122 int n = subject.length(); |
| 1123 int m = pattern.length(); | 1123 int m = pattern.length(); |
| 1124 // Only preprocess at most kBMMaxShift last characters of pattern. | 1124 // Only preprocess at most kBMMaxShift last characters of pattern. |
| 1125 int start = m < kBMMaxShift ? 0 : m - kBMMaxShift; | 1125 int start = m < kBMMaxShift ? 0 : m - kBMMaxShift; |
| 1126 | 1126 |
| 1127 BoyerMoorePopulateBadCharTable(pattern, start); | 1127 BoyerMoorePopulateBadCharTable(pattern, start); |
| 1128 | 1128 |
| 1129 int badness = -m; // How bad we are doing without a good-suffix table. | 1129 int badness = -m; // How bad we are doing without a good-suffix table. |
| 1130 int idx; // No matches found prior to this index. | 1130 int idx; // No matches found prior to this index. |
| 1131 pchar last_char = pattern[m - 1]; | 1131 pchar last_char = pattern[m - 1]; |
| 1132 // Perform search | 1132 // Perform search |
| 1133 for (idx = start_index; idx <= n - m;) { | 1133 for (idx = start_index; idx <= n - m;) { |
| 1134 int j = m - 1; | 1134 int j = m - 1; |
| 1135 int c; | 1135 int c; |
| 1136 while (last_char != (c = subject[idx + j])) { | 1136 while (last_char != (c = subject[idx + j])) { |
| 1137 int bc_occ = CharOccurence<schar, pchar>(c); | 1137 int bc_occ = CharOccurence<schar, pchar>(c); |
| 1138 int shift = j - bc_occ; | 1138 int shift = j - bc_occ; |
| 1139 idx += shift; | 1139 idx += shift; |
| 1140 badness += 1 - shift; // at most zero, so badness cannot increase. | 1140 badness += 1 - shift; // at most zero, so badness cannot increase. |
| 1141 if (idx > n - m) { | 1141 if (idx > n - m) { |
| 1142 complete = true; | 1142 *complete = true; |
| 1143 return -1; | 1143 return -1; |
| 1144 } | 1144 } |
| 1145 } | 1145 } |
| 1146 j--; | 1146 j--; |
| 1147 while (j >= 0 && pattern[j] == (c = subject[idx + j])) j--; | 1147 while (j >= 0 && pattern[j] == (c = subject[idx + j])) j--; |
| 1148 if (j < 0) { | 1148 if (j < 0) { |
| 1149 complete = true; | 1149 *complete = true; |
| 1150 return idx; | 1150 return idx; |
| 1151 } else { | 1151 } else { |
| 1152 int bc_occ = CharOccurence<schar, pchar>(c); | 1152 int bc_occ = CharOccurence<schar, pchar>(c); |
| 1153 int shift = bc_occ < j ? j - bc_occ : 1; | 1153 int shift = bc_occ < j ? j - bc_occ : 1; |
| 1154 idx += shift; | 1154 idx += shift; |
| 1155 // Badness increases by the number of characters we have | 1155 // Badness increases by the number of characters we have |
| 1156 // checked, and decreases by the number of characters we | 1156 // checked, and decreases by the number of characters we |
| 1157 // can skip by shifting. It's a measure of how we are doing | 1157 // can skip by shifting. It's a measure of how we are doing |
| 1158 // compared to reading each character exactly once. | 1158 // compared to reading each character exactly once. |
| 1159 badness += (m - j) - shift; | 1159 badness += (m - j) - shift; |
| 1160 if (badness > 0) { | 1160 if (badness > 0) { |
| 1161 complete = false; | 1161 *complete = false; |
| 1162 return idx; | 1162 return idx; |
| 1163 } | 1163 } |
| 1164 } | 1164 } |
| 1165 } | 1165 } |
| 1166 complete = true; | 1166 *complete = true; |
| 1167 return -1; | 1167 return -1; |
| 1168 } | 1168 } |
| 1169 | 1169 |
| 1170 | 1170 |
| 1171 template <typename schar, typename pchar> | 1171 template <typename schar, typename pchar> |
| 1172 static int BoyerMooreIndexOf(Vector<const schar> subject, | 1172 static int BoyerMooreIndexOf(Vector<const schar> subject, |
| 1173 Vector<const pchar> pattern, | 1173 Vector<const pchar> pattern, |
| 1174 int idx) { | 1174 int idx) { |
| 1175 int n = subject.length(); | 1175 int n = subject.length(); |
| 1176 int m = pattern.length(); | 1176 int m = pattern.length(); |
| (...skipping 51 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1228 // Trivial string search for shorter strings. | 1228 // Trivial string search for shorter strings. |
| 1229 // On return, if "complete" is set to true, the return value is the | 1229 // On return, if "complete" is set to true, the return value is the |
| 1230 // final result of searching for the patter in the subject. | 1230 // final result of searching for the patter in the subject. |
| 1231 // If "complete" is set to false, the return value is the index where | 1231 // If "complete" is set to false, the return value is the index where |
| 1232 // further checking should start, i.e., it's guaranteed that the pattern | 1232 // further checking should start, i.e., it's guaranteed that the pattern |
| 1233 // does not occur at a position prior to the returned index. | 1233 // does not occur at a position prior to the returned index. |
| 1234 template <typename pchar, typename schar> | 1234 template <typename pchar, typename schar> |
| 1235 static int SimpleIndexOf(Vector<const schar> subject, | 1235 static int SimpleIndexOf(Vector<const schar> subject, |
| 1236 Vector<const pchar> pattern, | 1236 Vector<const pchar> pattern, |
| 1237 int idx, | 1237 int idx, |
| 1238 bool &complete) { | 1238 bool* complete) { |
| 1239 // Badness is a count of how much work we have done. When we have | 1239 // Badness is a count of how much work we have done. When we have |
| 1240 // done enough work we decide it's probably worth switching to a better | 1240 // done enough work we decide it's probably worth switching to a better |
| 1241 // algorithm. | 1241 // algorithm. |
| 1242 int badness = -10 - (pattern.length() << 2); | 1242 int badness = -10 - (pattern.length() << 2); |
| 1243 // We know our pattern is at least 2 characters, we cache the first so | 1243 // We know our pattern is at least 2 characters, we cache the first so |
| 1244 // the common case of the first character not matching is faster. | 1244 // the common case of the first character not matching is faster. |
| 1245 pchar pattern_first_char = pattern[0]; | 1245 pchar pattern_first_char = pattern[0]; |
| 1246 | 1246 |
| 1247 for (int i = idx, n = subject.length() - pattern.length(); i <= n; i++) { | 1247 for (int i = idx, n = subject.length() - pattern.length(); i <= n; i++) { |
| 1248 badness++; | 1248 badness++; |
| 1249 if (badness > 0) { | 1249 if (badness > 0) { |
| 1250 complete = false; | 1250 *complete = false; |
| 1251 return (i); | 1251 return (i); |
| 1252 } | 1252 } |
| 1253 if (subject[i] != pattern_first_char) continue; | 1253 if (subject[i] != pattern_first_char) continue; |
| 1254 int j = 1; | 1254 int j = 1; |
| 1255 do { | 1255 do { |
| 1256 if (pattern[j] != subject[i+j]) { | 1256 if (pattern[j] != subject[i+j]) { |
| 1257 break; | 1257 break; |
| 1258 } | 1258 } |
| 1259 j++; | 1259 j++; |
| 1260 } while (j < pattern.length()); | 1260 } while (j < pattern.length()); |
| 1261 if (j == pattern.length()) { | 1261 if (j == pattern.length()) { |
| 1262 complete = true; | 1262 *complete = true; |
| 1263 return i; | 1263 return i; |
| 1264 } | 1264 } |
| 1265 badness += j; | 1265 badness += j; |
| 1266 } | 1266 } |
| 1267 complete = true; | 1267 *complete = true; |
| 1268 return -1; | 1268 return -1; |
| 1269 } | 1269 } |
| 1270 | 1270 |
| 1271 // Simple indexOf that never bails out. For short patterns only. | 1271 // Simple indexOf that never bails out. For short patterns only. |
| 1272 template <typename pchar, typename schar> | 1272 template <typename pchar, typename schar> |
| 1273 static int SimpleIndexOf(Vector<const schar> subject, | 1273 static int SimpleIndexOf(Vector<const schar> subject, |
| 1274 Vector<const pchar> pattern, | 1274 Vector<const pchar> pattern, |
| 1275 int idx) { | 1275 int idx) { |
| 1276 pchar pattern_first_char = pattern[0]; | 1276 pchar pattern_first_char = pattern[0]; |
| 1277 for (int i = idx, n = subject.length() - pattern.length(); i <= n; i++) { | 1277 for (int i = idx, n = subject.length() - pattern.length(); i <= n; i++) { |
| (...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1310 } | 1310 } |
| 1311 } | 1311 } |
| 1312 if (pat.length() < kBMMinPatternLength) { | 1312 if (pat.length() < kBMMinPatternLength) { |
| 1313 // We don't believe fancy searching can ever be more efficient. | 1313 // We don't believe fancy searching can ever be more efficient. |
| 1314 // The max shift of Boyer-Moore on a pattern of this length does | 1314 // The max shift of Boyer-Moore on a pattern of this length does |
| 1315 // not compensate for the overhead. | 1315 // not compensate for the overhead. |
| 1316 return SimpleIndexOf(sub, pat, start_index); | 1316 return SimpleIndexOf(sub, pat, start_index); |
| 1317 } | 1317 } |
| 1318 // Try algorithms in order of increasing setup cost and expected performance. | 1318 // Try algorithms in order of increasing setup cost and expected performance. |
| 1319 bool complete; | 1319 bool complete; |
| 1320 int idx = SimpleIndexOf(sub, pat, start_index, complete); | 1320 int idx = SimpleIndexOf(sub, pat, start_index, &complete); |
| 1321 if (complete) return idx; | 1321 if (complete) return idx; |
| 1322 idx = BoyerMooreSimplified(sub, pat, idx, complete); | 1322 idx = BoyerMooreSimplified(sub, pat, idx, &complete); |
| 1323 if (complete) return idx; | 1323 if (complete) return idx; |
| 1324 return BoyerMooreIndexOf(sub, pat, idx); | 1324 return BoyerMooreIndexOf(sub, pat, idx); |
| 1325 } | 1325 } |
| 1326 | 1326 |
| 1327 // Perform string match of pattern on subject, starting at start index. | 1327 // Perform string match of pattern on subject, starting at start index. |
| 1328 // Caller must ensure that 0 <= start_index <= sub->length(), | 1328 // Caller must ensure that 0 <= start_index <= sub->length(), |
| 1329 // and should check that pat->length() + start_index <= sub->length() | 1329 // and should check that pat->length() + start_index <= sub->length() |
| 1330 int Runtime::StringMatch(Handle<String> sub, | 1330 int Runtime::StringMatch(Handle<String> sub, |
| 1331 Handle<String> pat, | 1331 Handle<String> pat, |
| 1332 int start_index) { | 1332 int start_index) { |
| (...skipping 4141 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 5474 | 5474 |
| 5475 void Runtime::PerformGC(Object* result) { | 5475 void Runtime::PerformGC(Object* result) { |
| 5476 Failure* failure = Failure::cast(result); | 5476 Failure* failure = Failure::cast(result); |
| 5477 // Try to do a garbage collection; ignore it if it fails. The C | 5477 // Try to do a garbage collection; ignore it if it fails. The C |
| 5478 // entry stub will throw an out-of-memory exception in that case. | 5478 // entry stub will throw an out-of-memory exception in that case. |
| 5479 Heap::CollectGarbage(failure->requested(), failure->allocation_space()); | 5479 Heap::CollectGarbage(failure->requested(), failure->allocation_space()); |
| 5480 } | 5480 } |
| 5481 | 5481 |
| 5482 | 5482 |
| 5483 } } // namespace v8::internal | 5483 } } // namespace v8::internal |
| OLD | NEW |