OLD | NEW |
1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 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 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
42 | 42 |
43 #ifdef ENABLE_DEBUGGER_SUPPORT | 43 #ifdef ENABLE_DEBUGGER_SUPPORT |
44 | 44 |
45 | 45 |
46 // A simple implementation of dynamic programming algorithm. It solves | 46 // A simple implementation of dynamic programming algorithm. It solves |
47 // the problem of finding the difference of 2 arrays. It uses a table of results | 47 // the problem of finding the difference of 2 arrays. It uses a table of results |
48 // of subproblems. Each cell contains a number together with 2-bit flag | 48 // of subproblems. Each cell contains a number together with 2-bit flag |
49 // that helps building the chunk list. | 49 // that helps building the chunk list. |
50 class Differencer { | 50 class Differencer { |
51 public: | 51 public: |
52 explicit Differencer(Compare::Input* input) | 52 explicit Differencer(Comparator::Input* input) |
53 : input_(input), len1_(input->getLength1()), len2_(input->getLength2()) { | 53 : input_(input), len1_(input->getLength1()), len2_(input->getLength2()) { |
54 buffer_ = NewArray<int>(len1_ * len2_); | 54 buffer_ = NewArray<int>(len1_ * len2_); |
55 } | 55 } |
56 ~Differencer() { | 56 ~Differencer() { |
57 DeleteArray(buffer_); | 57 DeleteArray(buffer_); |
58 } | 58 } |
59 | 59 |
60 void Initialize() { | 60 void Initialize() { |
61 int array_size = len1_ * len2_; | 61 int array_size = len1_ * len2_; |
62 for (int i = 0; i < array_size; i++) { | 62 for (int i = 0; i < array_size; i++) { |
63 buffer_[i] = kEmptyCellValue; | 63 buffer_[i] = kEmptyCellValue; |
64 } | 64 } |
65 } | 65 } |
66 | 66 |
67 // Makes sure that result for the full problem is calculated and stored | 67 // Makes sure that result for the full problem is calculated and stored |
68 // in the table together with flags showing a path through subproblems. | 68 // in the table together with flags showing a path through subproblems. |
69 void FillTable() { | 69 void FillTable() { |
70 CompareUpToTail(0, 0); | 70 CompareUpToTail(0, 0); |
71 } | 71 } |
72 | 72 |
73 void SaveResult(Compare::Output* chunk_writer) { | 73 void SaveResult(Comparator::Output* chunk_writer) { |
74 ResultWriter writer(chunk_writer); | 74 ResultWriter writer(chunk_writer); |
75 | 75 |
76 int pos1 = 0; | 76 int pos1 = 0; |
77 int pos2 = 0; | 77 int pos2 = 0; |
78 while (true) { | 78 while (true) { |
79 if (pos1 < len1_) { | 79 if (pos1 < len1_) { |
80 if (pos2 < len2_) { | 80 if (pos2 < len2_) { |
81 Direction dir = get_direction(pos1, pos2); | 81 Direction dir = get_direction(pos1, pos2); |
82 switch (dir) { | 82 switch (dir) { |
83 case EQ: | 83 case EQ: |
(...skipping 21 matching lines...) Expand all Loading... |
105 if (len2_ != pos2) { | 105 if (len2_ != pos2) { |
106 writer.skip2(len2_ - pos2); | 106 writer.skip2(len2_ - pos2); |
107 } | 107 } |
108 break; | 108 break; |
109 } | 109 } |
110 } | 110 } |
111 writer.close(); | 111 writer.close(); |
112 } | 112 } |
113 | 113 |
114 private: | 114 private: |
115 Compare::Input* input_; | 115 Comparator::Input* input_; |
116 int* buffer_; | 116 int* buffer_; |
117 int len1_; | 117 int len1_; |
118 int len2_; | 118 int len2_; |
119 | 119 |
120 enum Direction { | 120 enum Direction { |
121 EQ = 0, | 121 EQ = 0, |
122 SKIP1, | 122 SKIP1, |
123 SKIP2, | 123 SKIP2, |
124 SKIP_ANY, | 124 SKIP_ANY, |
125 | 125 |
(...skipping 62 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
188 static const int kEmptyCellValue = -1 << kDirectionSizeBits; | 188 static const int kEmptyCellValue = -1 << kDirectionSizeBits; |
189 | 189 |
190 // This method only holds static assert statement (unfortunately you cannot | 190 // This method only holds static assert statement (unfortunately you cannot |
191 // place one in class scope). | 191 // place one in class scope). |
192 void StaticAssertHolder() { | 192 void StaticAssertHolder() { |
193 STATIC_ASSERT(MAX_DIRECTION_FLAG_VALUE < (1 << kDirectionSizeBits)); | 193 STATIC_ASSERT(MAX_DIRECTION_FLAG_VALUE < (1 << kDirectionSizeBits)); |
194 } | 194 } |
195 | 195 |
196 class ResultWriter { | 196 class ResultWriter { |
197 public: | 197 public: |
198 explicit ResultWriter(Compare::Output* chunk_writer) | 198 explicit ResultWriter(Comparator::Output* chunk_writer) |
199 : chunk_writer_(chunk_writer), pos1_(0), pos2_(0), | 199 : chunk_writer_(chunk_writer), pos1_(0), pos2_(0), |
200 pos1_begin_(-1), pos2_begin_(-1), has_open_chunk_(false) { | 200 pos1_begin_(-1), pos2_begin_(-1), has_open_chunk_(false) { |
201 } | 201 } |
202 void eq() { | 202 void eq() { |
203 FlushChunk(); | 203 FlushChunk(); |
204 pos1_++; | 204 pos1_++; |
205 pos2_++; | 205 pos2_++; |
206 } | 206 } |
207 void skip1(int len1) { | 207 void skip1(int len1) { |
208 StartChunk(); | 208 StartChunk(); |
209 pos1_ += len1; | 209 pos1_ += len1; |
210 } | 210 } |
211 void skip2(int len2) { | 211 void skip2(int len2) { |
212 StartChunk(); | 212 StartChunk(); |
213 pos2_ += len2; | 213 pos2_ += len2; |
214 } | 214 } |
215 void close() { | 215 void close() { |
216 FlushChunk(); | 216 FlushChunk(); |
217 } | 217 } |
218 | 218 |
219 private: | 219 private: |
220 Compare::Output* chunk_writer_; | 220 Comparator::Output* chunk_writer_; |
221 int pos1_; | 221 int pos1_; |
222 int pos2_; | 222 int pos2_; |
223 int pos1_begin_; | 223 int pos1_begin_; |
224 int pos2_begin_; | 224 int pos2_begin_; |
225 bool has_open_chunk_; | 225 bool has_open_chunk_; |
226 | 226 |
227 void StartChunk() { | 227 void StartChunk() { |
228 if (!has_open_chunk_) { | 228 if (!has_open_chunk_) { |
229 pos1_begin_ = pos1_; | 229 pos1_begin_ = pos1_; |
230 pos2_begin_ = pos2_; | 230 pos2_begin_ = pos2_; |
231 has_open_chunk_ = true; | 231 has_open_chunk_ = true; |
232 } | 232 } |
233 } | 233 } |
234 | 234 |
235 void FlushChunk() { | 235 void FlushChunk() { |
236 if (has_open_chunk_) { | 236 if (has_open_chunk_) { |
237 chunk_writer_->AddChunk(pos1_begin_, pos2_begin_, | 237 chunk_writer_->AddChunk(pos1_begin_, pos2_begin_, |
238 pos1_ - pos1_begin_, pos2_ - pos2_begin_); | 238 pos1_ - pos1_begin_, pos2_ - pos2_begin_); |
239 has_open_chunk_ = false; | 239 has_open_chunk_ = false; |
240 } | 240 } |
241 } | 241 } |
242 }; | 242 }; |
243 }; | 243 }; |
244 | 244 |
245 | 245 |
246 void Compare::CalculateDifference(Compare::Input* input, | 246 void Comparator::CalculateDifference(Comparator::Input* input, |
247 Compare::Output* result_writer) { | 247 Comparator::Output* result_writer) { |
248 Differencer differencer(input); | 248 Differencer differencer(input); |
249 differencer.Initialize(); | 249 differencer.Initialize(); |
250 differencer.FillTable(); | 250 differencer.FillTable(); |
251 differencer.SaveResult(result_writer); | 251 differencer.SaveResult(result_writer); |
252 } | 252 } |
253 | 253 |
254 | 254 |
255 static bool CompareSubstrings(Handle<String> s1, int pos1, | 255 static bool CompareSubstrings(Handle<String> s1, int pos1, |
256 Handle<String> s2, int pos2, int len) { | 256 Handle<String> s2, int pos2, int len) { |
257 static StringInputBuffer buf1; | 257 static StringInputBuffer buf1; |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
305 Handle<FixedArray> ends_array_; | 305 Handle<FixedArray> ends_array_; |
306 int string_len_; | 306 int string_len_; |
307 | 307 |
308 int GetPosAfterNewLine(int index) { | 308 int GetPosAfterNewLine(int index) { |
309 return Smi::cast(ends_array_->get(index))->value() + 1; | 309 return Smi::cast(ends_array_->get(index))->value() + 1; |
310 } | 310 } |
311 }; | 311 }; |
312 | 312 |
313 | 313 |
314 // Represents 2 strings as 2 arrays of lines. | 314 // Represents 2 strings as 2 arrays of lines. |
315 class LineArrayCompareInput : public Compare::Input { | 315 class LineArrayCompareInput : public Comparator::Input { |
316 public: | 316 public: |
317 LineArrayCompareInput(Handle<String> s1, Handle<String> s2, | 317 LineArrayCompareInput(Handle<String> s1, Handle<String> s2, |
318 LineEndsWrapper line_ends1, LineEndsWrapper line_ends2) | 318 LineEndsWrapper line_ends1, LineEndsWrapper line_ends2) |
319 : s1_(s1), s2_(s2), line_ends1_(line_ends1), line_ends2_(line_ends2) { | 319 : s1_(s1), s2_(s2), line_ends1_(line_ends1), line_ends2_(line_ends2) { |
320 } | 320 } |
321 int getLength1() { | 321 int getLength1() { |
322 return line_ends1_.length(); | 322 return line_ends1_.length(); |
323 } | 323 } |
324 int getLength2() { | 324 int getLength2() { |
325 return line_ends2_.length(); | 325 return line_ends2_.length(); |
(...skipping 14 matching lines...) Expand all Loading... |
340 private: | 340 private: |
341 Handle<String> s1_; | 341 Handle<String> s1_; |
342 Handle<String> s2_; | 342 Handle<String> s2_; |
343 LineEndsWrapper line_ends1_; | 343 LineEndsWrapper line_ends1_; |
344 LineEndsWrapper line_ends2_; | 344 LineEndsWrapper line_ends2_; |
345 }; | 345 }; |
346 | 346 |
347 | 347 |
348 // Stores compare result in JSArray. Each chunk is stored as 3 array elements: | 348 // Stores compare result in JSArray. Each chunk is stored as 3 array elements: |
349 // (pos1_begin, pos1_end, pos2_end). | 349 // (pos1_begin, pos1_end, pos2_end). |
350 class LineArrayCompareOutput : public Compare::Output { | 350 class LineArrayCompareOutput : public Comparator::Output { |
351 public: | 351 public: |
352 LineArrayCompareOutput(LineEndsWrapper line_ends1, LineEndsWrapper line_ends2) | 352 LineArrayCompareOutput(LineEndsWrapper line_ends1, LineEndsWrapper line_ends2) |
353 : array_(Factory::NewJSArray(10)), current_size_(0), | 353 : array_(Factory::NewJSArray(10)), current_size_(0), |
354 line_ends1_(line_ends1), line_ends2_(line_ends2) { | 354 line_ends1_(line_ends1), line_ends2_(line_ends2) { |
355 } | 355 } |
356 | 356 |
357 void AddChunk(int line_pos1, int line_pos2, int line_len1, int line_len2) { | 357 void AddChunk(int line_pos1, int line_pos2, int line_len1, int line_len2) { |
358 int char_pos1 = line_ends1_.GetLineStart(line_pos1); | 358 int char_pos1 = line_ends1_.GetLineStart(line_pos1); |
359 int char_pos2 = line_ends2_.GetLineStart(line_pos2); | 359 int char_pos2 = line_ends2_.GetLineStart(line_pos2); |
360 int char_len1 = line_ends1_.GetLineStart(line_pos1 + line_len1) - char_pos1; | 360 int char_len1 = line_ends1_.GetLineStart(line_pos1 + line_len1) - char_pos1; |
(...skipping 20 matching lines...) Expand all Loading... |
381 | 381 |
382 | 382 |
383 Handle<JSArray> LiveEdit::CompareStringsLinewise(Handle<String> s1, | 383 Handle<JSArray> LiveEdit::CompareStringsLinewise(Handle<String> s1, |
384 Handle<String> s2) { | 384 Handle<String> s2) { |
385 LineEndsWrapper line_ends1(s1); | 385 LineEndsWrapper line_ends1(s1); |
386 LineEndsWrapper line_ends2(s2); | 386 LineEndsWrapper line_ends2(s2); |
387 | 387 |
388 LineArrayCompareInput input(s1, s2, line_ends1, line_ends2); | 388 LineArrayCompareInput input(s1, s2, line_ends1, line_ends2); |
389 LineArrayCompareOutput output(line_ends1, line_ends2); | 389 LineArrayCompareOutput output(line_ends1, line_ends2); |
390 | 390 |
391 Compare::CalculateDifference(&input, &output); | 391 Comparator::CalculateDifference(&input, &output); |
392 | 392 |
393 return output.GetResult(); | 393 return output.GetResult(); |
394 } | 394 } |
395 | 395 |
396 | 396 |
397 static void CompileScriptForTracker(Handle<Script> script) { | 397 static void CompileScriptForTracker(Handle<Script> script) { |
398 const bool is_eval = false; | 398 const bool is_eval = false; |
399 const bool is_global = true; | 399 const bool is_global = true; |
400 // TODO(635): support extensions. | 400 // TODO(635): support extensions. |
401 Extension* extension = NULL; | 401 Extension* extension = NULL; |
(...skipping 1001 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1403 | 1403 |
1404 bool LiveEditFunctionTracker::IsActive() { | 1404 bool LiveEditFunctionTracker::IsActive() { |
1405 return false; | 1405 return false; |
1406 } | 1406 } |
1407 | 1407 |
1408 #endif // ENABLE_DEBUGGER_SUPPORT | 1408 #endif // ENABLE_DEBUGGER_SUPPORT |
1409 | 1409 |
1410 | 1410 |
1411 | 1411 |
1412 } } // namespace v8::internal | 1412 } } // namespace v8::internal |
OLD | NEW |