| 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 |