Revision: 6274
Author: [email protected]
Date: Tue Jan 11 06:55:47 2011
Log: Add fine-grained diff implementation to LiveEdit engine.
BUG=1013
TEST=
Review URL: http://codereview.chromium.org/6017008
http://code.google.com/p/v8/source/detail?r=6274
Modified:
/branches/bleeding_edge/src/liveedit-debugger.js
/branches/bleeding_edge/src/liveedit.cc
/branches/bleeding_edge/src/liveedit.h
/branches/bleeding_edge/src/runtime.cc
/branches/bleeding_edge/src/runtime.h
/branches/bleeding_edge/test/mjsunit/debug-liveedit-diff.js
/branches/bleeding_edge/test/mjsunit/debug-liveedit-newsource.js
=======================================
--- /branches/bleeding_edge/src/liveedit-debugger.js Thu Dec 23 18:44:35
2010
+++ /branches/bleeding_edge/src/liveedit-debugger.js Tue Jan 11 06:55:47
2011
@@ -980,15 +980,15 @@
// LiveEdit main entry point: changes a script text to a new string.
function SetScriptSource(script, new_source, preview_only, change_log) {
var old_source = script.source;
- var diff = CompareStringsLinewise(old_source, new_source);
+ var diff = CompareStrings(old_source, new_source);
return ApplyPatchMultiChunk(script, diff, new_source, preview_only,
change_log);
}
// Function is public.
this.SetScriptSource = SetScriptSource;
- function CompareStringsLinewise(s1, s2) {
- return %LiveEditCompareStringsLinewise(s1, s2);
+ function CompareStrings(s1, s2) {
+ return %LiveEditCompareStrings(s1, s2);
}
// Applies the change to the script.
@@ -1076,7 +1076,7 @@
// Functions are public for tests.
this.TestApi = {
PosTranslator: PosTranslator,
- CompareStringsLinewise: CompareStringsLinewise,
+ CompareStrings: CompareStrings,
ApplySingleChunkPatch: ApplySingleChunkPatch
}
}
=======================================
--- /branches/bleeding_edge/src/liveedit.cc Tue Dec 7 03:31:57 2010
+++ /branches/bleeding_edge/src/liveedit.cc Tue Jan 11 06:55:47 2011
@@ -273,6 +273,82 @@
}
return true;
}
+
+
+// A helper class that writes chunk numbers into JSArray.
+// Each chunk is stored as 3 array elements: (pos1_begin, pos1_end,
pos2_end).
+class CompareOutputArrayWriter {
+ public:
+ CompareOutputArrayWriter()
+ : array_(Factory::NewJSArray(10)), current_size_(0) {}
+
+ Handle<JSArray> GetResult() {
+ return array_;
+ }
+
+ void WriteChunk(int char_pos1, int char_pos2, int char_len1, int
char_len2) {
+ SetElement(array_, current_size_,
Handle<Object>(Smi::FromInt(char_pos1)));
+ SetElement(array_, current_size_ + 1,
+ Handle<Object>(Smi::FromInt(char_pos1 + char_len1)));
+ SetElement(array_, current_size_ + 2,
+ Handle<Object>(Smi::FromInt(char_pos2 + char_len2)));
+ current_size_ += 3;
+ }
+
+ private:
+ Handle<JSArray> array_;
+ int current_size_;
+};
+
+
+// Represents 2 strings as 2 arrays of tokens.
+// TODO(LiveEdit): Currently it's actually an array of charactres.
+// Make array of tokens instead.
+class TokensCompareInput : public Comparator::Input {
+ public:
+ TokensCompareInput(Handle<String> s1, int offset1, int len1,
+ Handle<String> s2, int offset2, int len2)
+ : s1_(s1), offset1_(offset1), len1_(len1),
+ s2_(s2), offset2_(offset2), len2_(len2) {
+ }
+ virtual int getLength1() {
+ return len1_;
+ }
+ virtual int getLength2() {
+ return len2_;
+ }
+ bool equals(int index1, int index2) {
+ return s1_->Get(offset1_ + index1) == s2_->Get(offset2_ + index2);
+ }
+
+ private:
+ Handle<String> s1_;
+ int offset1_;
+ int len1_;
+ Handle<String> s2_;
+ int offset2_;
+ int len2_;
+};
+
+
+// Stores compare result in JSArray. Converts substring positions
+// to absolute positions.
+class TokensCompareOutput : public Comparator::Output {
+ public:
+ TokensCompareOutput(CompareOutputArrayWriter* array_writer,
+ int offset1, int offset2)
+ : array_writer_(array_writer), offset1_(offset1),
offset2_(offset2) {
+ }
+
+ void AddChunk(int pos1, int pos2, int len1, int len2) {
+ array_writer_->WriteChunk(pos1 + offset1_, pos2 + offset2_, len1,
len2);
+ }
+
+ private:
+ CompareOutputArrayWriter* array_writer_;
+ int offset1_;
+ int offset2_;
+};
// Wraps raw n-elements line_ends array as a list of n+1 lines. The last
line
@@ -350,13 +426,14 @@
};
-// Stores compare result in JSArray. Each chunk is stored as 3 array
elements:
-// (pos1_begin, pos1_end, pos2_end).
-class LineArrayCompareOutput : public Comparator::Output {
+// Stores compare result in JSArray. For each chunk tries to conduct
+// a fine-grained nested diff token-wise.
+class TokenizingLineArrayCompareOutput : public Comparator::Output {
public:
- LineArrayCompareOutput(LineEndsWrapper line_ends1, LineEndsWrapper
line_ends2)
- : array_(Factory::NewJSArray(10)), current_size_(0),
- line_ends1_(line_ends1), line_ends2_(line_ends2) {
+ TokenizingLineArrayCompareOutput(LineEndsWrapper line_ends1,
+ LineEndsWrapper line_ends2,
+ Handle<String> s1, Handle<String> s2)
+ : line_ends1_(line_ends1), line_ends2_(line_ends2), s1_(s1), s2_(s2)
{
}
void AddChunk(int line_pos1, int line_pos2, int line_len1, int
line_len2) {
@@ -365,33 +442,43 @@
int char_len1 = line_ends1_.GetLineStart(line_pos1 + line_len1) -
char_pos1;
int char_len2 = line_ends2_.GetLineStart(line_pos2 + line_len2) -
char_pos2;
- SetElement(array_, current_size_,
Handle<Object>(Smi::FromInt(char_pos1)));
- SetElement(array_, current_size_ + 1,
- Handle<Object>(Smi::FromInt(char_pos1 + char_len1)));
- SetElement(array_, current_size_ + 2,
- Handle<Object>(Smi::FromInt(char_pos2 + char_len2)));
- current_size_ += 3;
+ if (char_len1 < CHUNK_LEN_LIMIT && char_len2 < CHUNK_LEN_LIMIT) {
+ // Chunk is small enough to conduct a nested token-level diff.
+ HandleScope subTaskScope;
+
+ TokensCompareInput tokens_input(s1_, char_pos1, char_len1,
+ s2_, char_pos2, char_len2);
+ TokensCompareOutput tokens_output(&array_writer_, char_pos1,
+ char_pos2);
+
+ Comparator::CalculateDifference(&tokens_input, &tokens_output);
+ } else {
+ array_writer_.WriteChunk(char_pos1, char_pos2, char_len1, char_len2);
+ }
}
Handle<JSArray> GetResult() {
- return array_;
+ return array_writer_.GetResult();
}
private:
- Handle<JSArray> array_;
- int current_size_;
+ static const int CHUNK_LEN_LIMIT = 800;
+
+ CompareOutputArrayWriter array_writer_;
LineEndsWrapper line_ends1_;
LineEndsWrapper line_ends2_;
+ Handle<String> s1_;
+ Handle<String> s2_;
};
-Handle<JSArray> LiveEdit::CompareStringsLinewise(Handle<String> s1,
- Handle<String> s2) {
+Handle<JSArray> LiveEdit::CompareStrings(Handle<String> s1,
+ Handle<String> s2) {
LineEndsWrapper line_ends1(s1);
LineEndsWrapper line_ends2(s2);
LineArrayCompareInput input(s1, s2, line_ends1, line_ends2);
- LineArrayCompareOutput output(line_ends1, line_ends2);
+ TokenizingLineArrayCompareOutput output(line_ends1, line_ends2, s1, s2);
Comparator::CalculateDifference(&input, &output);
=======================================
--- /branches/bleeding_edge/src/liveedit.h Tue Dec 7 03:31:57 2010
+++ /branches/bleeding_edge/src/liveedit.h Tue Jan 11 06:55:47 2011
@@ -126,10 +126,11 @@
FUNCTION_REPLACED_ON_ACTIVE_STACK = 5
};
- // Compares 2 strings line-by-line and returns diff in form of array of
- // triplets (pos1, pos1_end, pos2_end) describing list of diff chunks.
- static Handle<JSArray> CompareStringsLinewise(Handle<String> s1,
- Handle<String> s2);
+ // Compares 2 strings line-by-line, then token-wise and returns diff in
form
+ // of array of triplets (pos1, pos1_end, pos2_end) describing list
+ // of diff chunks.
+ static Handle<JSArray> CompareStrings(Handle<String> s1,
+ Handle<String> s2);
};
=======================================
--- /branches/bleeding_edge/src/runtime.cc Sun Jan 9 23:20:54 2011
+++ /branches/bleeding_edge/src/runtime.cc Tue Jan 11 06:55:47 2011
@@ -10334,15 +10334,16 @@
return *LiveEdit::CheckAndDropActivations(shared_array, do_drop);
}
-// Compares 2 strings line-by-line and returns diff in form of JSArray of
-// triplets (pos1, pos1_end, pos2_end) describing list of diff chunks.
-static MaybeObject* Runtime_LiveEditCompareStringsLinewise(Arguments args)
{
+// Compares 2 strings line-by-line, then token-wise and returns diff in
form
+// of JSArray of triplets (pos1, pos1_end, pos2_end) describing list
+// of diff chunks.
+static MaybeObject* Runtime_LiveEditCompareStrings(Arguments args) {
ASSERT(args.length() == 2);
HandleScope scope;
CONVERT_ARG_CHECKED(String, s1, 0);
CONVERT_ARG_CHECKED(String, s2, 1);
- return *LiveEdit::CompareStringsLinewise(s1, s2);
+ return *LiveEdit::CompareStrings(s1, s2);
}
=======================================
--- /branches/bleeding_edge/src/runtime.h Thu Jan 6 05:14:32 2011
+++ /branches/bleeding_edge/src/runtime.h Tue Jan 11 06:55:47 2011
@@ -361,7 +361,7 @@
F(LiveEditReplaceRefToNestedFunction, 3, 1) \
F(LiveEditPatchFunctionPositions, 2, 1) \
F(LiveEditCheckAndDropActivations, 2, 1) \
- F(LiveEditCompareStringsLinewise, 2, 1) \
+ F(LiveEditCompareStrings, 2, 1) \
F(GetFunctionCodePositionFromSource, 2, 1) \
F(ExecuteInDebugContext, 2, 1) \
\
=======================================
--- /branches/bleeding_edge/test/mjsunit/debug-liveedit-diff.js Tue Dec 7
03:01:02 2010
+++ /branches/bleeding_edge/test/mjsunit/debug-liveedit-diff.js Tue Jan 11
06:55:47 2011
@@ -31,11 +31,15 @@
Debug = debug.Debug
function CheckCompareOneWay(s1, s2) {
- var diff_array = Debug.LiveEdit.TestApi.CompareStringsLinewise(s1, s2);
+ var diff_array = Debug.LiveEdit.TestApi.CompareStrings(s1, s2);
var pos1 = 0;
var pos2 = 0;
print("Compare:");
+ print("s1='" + s1 + "'");
+ print("s2='" + s2 + "'");
+ print("Diff:");
+ print("" + diff_array);
for (var i = 0; i < diff_array.length; i += 3) {
var similar_length = diff_array[i] - pos1;
assertEquals(s1.substring(pos1, pos1 + similar_length),
@@ -45,12 +49,12 @@
pos1 += similar_length;
pos2 += similar_length;
print("<<< " + pos1 + " " + diff_array[i + 1]);
- print(s1.substring(pos1, pos1 + diff_array[i + 1]));
+ print(s1.substring(pos1, diff_array[i + 1]));
print("===");
- print(s2.substring(pos2, pos2 + diff_array[i + 2]));
+ print(s2.substring(pos2, diff_array[i + 2]));
print(">>> " + pos2 + " " + diff_array[i + 2]);
- pos1 += diff_array[i + 1];
- pos2 += diff_array[i + 2];
+ pos1 = diff_array[i + 1];
+ pos2 = diff_array[i + 2];
}
{
// After last change
@@ -64,9 +68,18 @@
print("");
}
-function CheckCompare(s1, s2) {
+function CheckCompareOneWayPlayWithLF(s1, s2) {
+ var s1Oneliner = s1.replace(/\n/g, ' ');
+ var s2Oneliner = s2.replace(/\n/g, ' ');
CheckCompareOneWay(s1, s2);
- CheckCompareOneWay(s2, s1);
+ CheckCompareOneWay(s1Oneliner, s2);
+ CheckCompareOneWay(s1, s2Oneliner);
+ CheckCompareOneWay(s1Oneliner, s2Oneliner);
+}
+
+function CheckCompare(s1, s2) {
+ CheckCompareOneWayPlayWithLF(s1, s2);
+ CheckCompareOneWayPlayWithLF(s2, s1);
}
CheckCompare("", "");
=======================================
--- /branches/bleeding_edge/test/mjsunit/debug-liveedit-newsource.js Tue
Dec 7 03:01:02 2010
+++ /branches/bleeding_edge/test/mjsunit/debug-liveedit-newsource.js Tue
Jan 11 06:55:47 2011
@@ -64,6 +64,6 @@
assertEquals("Capybara", ChooseAnimal());
// Global variable do not get changed (without restarting script).
assertEquals(25, something1);
-// Function is oneliner, so currently it is treated as damaged and not
patched.
-assertEquals(17, ChooseNumber());
+// We should support changes in oneliners.
+assertEquals(18, ChooseNumber());
assertEquals("Hello Peter", ChooseAnimal.Factory()("Peter"));
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
