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 |