diff options
Diffstat (limited to 'deps/v8/src/liveedit-debugger.js')
| -rw-r--r-- | deps/v8/src/liveedit-debugger.js | 587 |
1 files changed, 440 insertions, 147 deletions
diff --git a/deps/v8/src/liveedit-debugger.js b/deps/v8/src/liveedit-debugger.js index d2aee87949..8fbff41b4c 100644 --- a/deps/v8/src/liveedit-debugger.js +++ b/deps/v8/src/liveedit-debugger.js @@ -28,26 +28,52 @@ // LiveEdit feature implementation. The script should be executed after // debug-debugger.js. -// A LiveEdit namespace is declared inside a single function constructor. +// A LiveEdit namespace. It contains functions that modifies JavaScript code +// according to changes of script source (if possible). +// +// When new script source is put in, the difference is calculated textually, +// in form of list of delete/add/change chunks. The functions that include +// change chunk(s) get recompiled, or their enclosing functions are +// recompiled instead. +// If the function may not be recompiled (e.g. it was completely erased in new +// version of the script) it remains unchanged, but the code that could +// create a new instance of this function goes away. An old version of script +// is created to back up this obsolete function. +// All unchanged functions have their positions updated accordingly. +// +// LiveEdit namespace is declared inside a single function constructor. Debug.LiveEdit = new function() { - // Changes script text and recompiles all relevant functions if possible. + // Applies the change to the script. // The change is always a substring (change_pos, change_pos + change_len) // being replaced with a completely different string new_str. - // - // Only one function will have its Code changed in result of this function. - // All nested functions (should they have any instances at the moment) are - // left unchanged and re-linked to a newly created script instance - // representing old version of the source. (Generally speaking, - // during the change all nested functions are erased and completely different - // set of nested functions are introduced.) All other functions just have - // their positions updated. + // This API is a legacy and is obsolete. // // @param {Script} script that is being changed // @param {Array} change_log a list that collects engineer-readable // description of what happened. function ApplyPatch(script, change_pos, change_len, new_str, change_log) { + var old_source = script.source; + + // Prepare new source string. + var new_source = old_source.substring(0, change_pos) + + new_str + old_source.substring(change_pos + change_len); + + return ApplyPatchMultiChunk(script, + [ change_pos, change_pos + change_len, change_pos + new_str.length], + new_source, change_log); + } + // Function is public. + this.ApplyPatch = ApplyPatch; + + // Forward declaration for minifier. + var FunctionStatus; + + // Applies the change to the script. + // The change is in form of list of chunks encoded in a single array as + // a series of triplets (pos1_start, pos1_end, pos2_end) + function ApplyPatchMultiChunk(script, diff_array, new_source, change_log) { // Fully compiles source string as a script. Returns Array of // FunctionCompileInfo -- a descriptions of all functions of the script. @@ -117,27 +143,6 @@ Debug.LiveEdit = new function() { return compile_info; } - // Given a positions, finds a function that fully includes the entire - // change. - function FindChangedFunction(compile_info, offset, len) { - // First condition: function should start before the change region. - // Function #0 (whole-script function) always does, but we want - // one, that is later in this list. - var index = 0; - while (index + 1 < compile_info.length && - compile_info[index + 1].start_position <= offset) { - index++; - } - // Now we are at the last function that begins before the change - // region. The function that covers entire change region is either - // this function or the enclosing one. - for (; compile_info[index].end_position < offset + len; - index = compile_info[index].outer_index) { - Assert(index != -1); - } - return index; - } - // Variable forward declarations. Preprocessor "Minifier" needs them. var old_compile_info; var shared_infos; @@ -156,34 +161,27 @@ Debug.LiveEdit = new function() { // Replaces function's Code. function PatchCode(new_info, shared_info) { - %LiveEditReplaceFunctionCode(new_info.raw_array, shared_info.raw_array); - - change_log.push( {function_patched: new_info.function_name} ); - } - - var change_len_old; - var change_len_new; - // Translate position in old version of script into position in new - // version of script. - function PosTranslator(old_pos) { - if (old_pos <= change_pos) { - return old_pos; - } - if (old_pos >= change_pos + change_len_old) { - return old_pos + change_len_new - change_len_old; + if (shared_info) { + %LiveEditReplaceFunctionCode(new_info.raw_array, shared_info.raw_array); + change_log.push( {function_patched: new_info.function_name} ); + } else { + change_log.push( {function_patched: new_info.function_name, + function_info_not_found: true} ); } - return -1; + } - var position_change_array; + var position_patch_report; - function PatchPositions(new_info, shared_info) { + function PatchPositions(old_info, shared_info) { if (!shared_info) { - // TODO(LiveEdit): explain what is happening. + // TODO(LiveEdit): function is not compiled yet or is already collected. + position_patch_report.push( + { name: old_info.function_name, info_not_found: true } ); return; } var breakpoint_position_update = %LiveEditPatchFunctionPositions( - shared_info.raw_array, position_change_array); + shared_info.raw_array, diff_array); for (var i = 0; i < breakpoint_position_update.length; i += 2) { var new_pos = breakpoint_position_update[i]; var break_point_object = breakpoint_position_update[i + 1]; @@ -191,7 +189,7 @@ Debug.LiveEdit = new function() { { from: break_point_object.source_position(), to: new_pos } } ); break_point_object.updateSourcePosition(new_pos, script); } - position_patch_report.push( { name: new_info.function_name } ); + position_patch_report.push( { name: old_info.function_name } ); } var link_to_old_script_report; @@ -199,22 +197,19 @@ Debug.LiveEdit = new function() { // Makes a function associated with another instance of a script (the // one representing its old version). This way the function still // may access its own text. - function LinkToOldScript(shared_info) { - %LiveEditRelinkFunctionToScript(shared_info.raw_array, old_script); - - link_to_old_script_report.push( { name: shared_info.function_name } ); + function LinkToOldScript(shared_info, old_info_node) { + if (shared_info) { + %LiveEditRelinkFunctionToScript(shared_info.raw_array, old_script); + link_to_old_script_report.push( { name: shared_info.function_name } ); + } else { + link_to_old_script_report.push( + { name: old_info_node.info.function_name, not_found: true } ); + } } - - + var old_source = script.source; - var change_len_old = change_len; - var change_len_new = new_str.length; - - // Prepare new source string. - var new_source = old_source.substring(0, change_pos) + - new_str + old_source.substring(change_pos + change_len); - + // Find all SharedFunctionInfo's that are compiled from this script. var shared_raw_list = %LiveEditFindSharedFunctionInfosForScript(script); @@ -234,94 +229,103 @@ Debug.LiveEdit = new function() { } catch (e) { throw new Failure("Failed to compile new version of script: " + e); } - - // An index of a single function, that is going to have its code replaced. - var function_being_patched = - FindChangedFunction(old_compile_info, change_pos, change_len_old); - - // In old and new script versions function with a change should have the - // same indexes. - var function_being_patched2 = - FindChangedFunction(new_compile_info, change_pos, change_len_new); - Assert(function_being_patched == function_being_patched2, - "inconsistent old/new compile info"); - - // Check that function being patched has the same expectations in a new - // version. Otherwise we cannot safely patch its behavior and should - // choose the outer function instead. - while (!CompareFunctionExpectations( - old_compile_info[function_being_patched], - new_compile_info[function_being_patched])) { - - Assert(old_compile_info[function_being_patched].outer_index == - new_compile_info[function_being_patched].outer_index); - function_being_patched = - old_compile_info[function_being_patched].outer_index; - Assert(function_being_patched != -1); + + var pos_translator = new PosTranslator(diff_array); + + // Build tree structures for old and new versions of the script. + var root_old_node = BuildCodeInfoTree(old_compile_info); + var root_new_node = BuildCodeInfoTree(new_compile_info); + + // Analyze changes. + MarkChangedFunctions(root_old_node, pos_translator.GetChunks()); + FindCorrespondingFunctions(root_old_node, root_new_node); + + // Prepare to-do lists. + var replace_code_list = new Array(); + var link_to_old_script_list = new Array(); + var update_positions_list = new Array(); + + function HarvestTodo(old_node) { + function CollectDamaged(node) { + link_to_old_script_list.push(node); + for (var i = 0; i < node.children.length; i++) { + CollectDamaged(node.children[i]); + } + } + + if (old_node.status == FunctionStatus.DAMAGED) { + CollectDamaged(old_node); + return; + } + if (old_node.status == FunctionStatus.UNCHANGED) { + update_positions_list.push(old_node); + } else if (old_node.status == FunctionStatus.SOURCE_CHANGED) { + update_positions_list.push(old_node); + } else if (old_node.status == FunctionStatus.CHANGED) { + replace_code_list.push(old_node); + } + for (var i = 0; i < old_node.children.length; i++) { + HarvestTodo(old_node.children[i]); + } } - + + HarvestTodo(root_old_node); + + // Collect shared infos for functions whose code need to be patched. + var replaced_function_infos = new Array(); + for (var i = 0; i < replace_code_list.length; i++) { + var info = FindFunctionInfo(replace_code_list[i].array_index); + if (info) { + replaced_function_infos.push(info); + } + } + // Check that function being patched is not currently on stack. - CheckStackActivations( - [ FindFunctionInfo(function_being_patched) ], change_log ); + CheckStackActivations(replaced_function_infos, change_log); + // We haven't changed anything before this line yet. // Committing all changes. - var old_script_name = CreateNameForOldScript(script); - - // Update the script text and create a new script representing an old - // version of the script. - var old_script = %LiveEditReplaceScript(script, new_source, - old_script_name); - - PatchCode(new_compile_info[function_being_patched], - FindFunctionInfo(function_being_patched)); - - var position_patch_report = new Array(); - change_log.push( {position_patched: position_patch_report} ); - - var position_change_array = [ change_pos, - change_pos + change_len_old, - change_pos + change_len_new ]; - - // Update positions of all outer functions (i.e. all functions, that - // are partially below the function being patched). - for (var i = new_compile_info[function_being_patched].outer_index; - i != -1; - i = new_compile_info[i].outer_index) { - PatchPositions(new_compile_info[i], FindFunctionInfo(i)); - } - - // Update positions of all functions that are fully below the function - // being patched. - var old_next_sibling = - old_compile_info[function_being_patched].next_sibling_index; - var new_next_sibling = - new_compile_info[function_being_patched].next_sibling_index; - - // We simply go over the tail of both old and new lists. Their tails should - // have an identical structure. - if (old_next_sibling == -1) { - Assert(new_next_sibling == -1); - } else { - Assert(old_compile_info.length - old_next_sibling == - new_compile_info.length - new_next_sibling); - - for (var i = old_next_sibling, j = new_next_sibling; - i < old_compile_info.length; i++, j++) { - PatchPositions(new_compile_info[j], FindFunctionInfo(i)); + + // Create old script if there are function linked to old version. + if (link_to_old_script_list.length > 0) { + var old_script_name = CreateNameForOldScript(script); + + // Update the script text and create a new script representing an old + // version of the script. + var old_script = %LiveEditReplaceScript(script, new_source, + old_script_name); + + var link_to_old_script_report = new Array(); + change_log.push( { linked_to_old_script: link_to_old_script_report } ); + + // We need to link to old script all former nested functions. + for (var i = 0; i < link_to_old_script_list.length; i++) { + LinkToOldScript( + FindFunctionInfo(link_to_old_script_list[i].array_index), + link_to_old_script_list[i]); } } + + + for (var i = 0; i < replace_code_list.length; i++) { + PatchCode(replace_code_list[i].corresponding_node.info, + FindFunctionInfo(replace_code_list[i].array_index)); + } - var link_to_old_script_report = new Array(); - change_log.push( { linked_to_old_script: link_to_old_script_report } ); - - // We need to link to old script all former nested functions. - for (var i = function_being_patched + 1; i < old_next_sibling; i++) { - LinkToOldScript(FindFunctionInfo(i), old_script); + var position_patch_report = new Array(); + change_log.push( {position_patched: position_patch_report} ); + + for (var i = 0; i < update_positions_list.length; i++) { + // TODO(LiveEdit): take into account wether it's source_changed or + // unchanged and whether positions changed at all. + PatchPositions(update_positions_list[i].info, + FindFunctionInfo(update_positions_list[i].array_index)); } } // Function is public. - this.ApplyPatch = ApplyPatch; + this.ApplyPatchMultiChunk = ApplyPatchMultiChunk; + function Assert(condition, message) { if (!condition) { @@ -332,6 +336,296 @@ Debug.LiveEdit = new function() { } } } + + function DiffChunk(pos1, pos2, len1, len2) { + this.pos1 = pos1; + this.pos2 = pos2; + this.len1 = len1; + this.len2 = len2; + } + + function PosTranslator(diff_array) { + var chunks = new Array(); + var pos1 = 0; + var pos2 = 0; + for (var i = 0; i < diff_array.length; i += 3) { + pos2 += diff_array[i] - pos1 + pos2; + pos1 = diff_array[i]; + chunks.push(new DiffChunk(pos1, pos2, diff_array[i + 1] - pos1, + diff_array[i + 2] - pos2)); + pos1 = diff_array[i + 1]; + pos2 = diff_array[i + 2]; + } + this.chunks = chunks; + } + PosTranslator.prototype.GetChunks = function() { + return this.chunks; + } + + PosTranslator.prototype.Translate = function(pos, inside_chunk_handler) { + var array = this.chunks; + if (array.length == 0 || pos < array[0]) { + return pos; + } + var chunk_index1 = 0; + var chunk_index2 = array.length - 1; + + while (chunk_index1 < chunk_index2) { + var middle_index = (chunk_index1 + chunk_index2) / 2; + if (pos < array[middle_index + 1].pos1) { + chunk_index2 = middle_index; + } else { + chunk_index1 = middle_index + 1; + } + } + var chunk = array[chunk_index1]; + if (pos >= chunk.pos1 + chunk.len1) { + return pos += chunk.pos2 + chunk.len2 - chunk.pos1 - chunk.len1; + } + + if (!inside_chunk_handler) { + inside_chunk_handler = PosTranslator.default_inside_chunk_handler; + } + inside_chunk_handler(pos, chunk); + } + + PosTranslator.default_inside_chunk_handler = function() { + Assert(false, "Cannot translate position in chaged area"); + } + + var FunctionStatus = { + // No change to function or its inner functions; however its positions + // in script may have been shifted. + UNCHANGED: "unchanged", + // The code of a function remains unchanged, but something happened inside + // some inner functions. + SOURCE_CHANGED: "source changed", + // The code of a function is changed or some nested function cannot be + // properly patched so this function must be recompiled. + CHANGED: "changed", + // Function is changed but cannot be patched. + DAMAGED: "damaged" + } + + function CodeInfoTreeNode(code_info, children, array_index) { + this.info = code_info; + this.children = children; + // an index in array of compile_info + this.array_index = array_index; + this.parent = void(0); + + this.status = FunctionStatus.UNCHANGED; + // Status explanation is used for debugging purposes and will be shown + // in user UI if some explanations are needed. + this.status_explanation = void(0); + this.new_start_pos = void(0); + this.new_end_pos = void(0); + this.corresponding_node = void(0); + } + + // From array of function infos that is implicitly a tree creates + // an actual tree of functions in script. + function BuildCodeInfoTree(code_info_array) { + // Throughtout all function we iterate over input array. + var index = 0; + + // Recursive function that builds a branch of tree. + function BuildNode() { + var my_index = index; + index++; + var child_array = new Array(); + while (index < code_info_array.length && + code_info_array[index].outer_index == my_index) { + child_array.push(BuildNode()); + } + var node = new CodeInfoTreeNode(code_info_array[my_index], child_array, + my_index); + for (var i = 0; i < child_array.length; i++) { + child_array[i].parent = node; + } + return node; + } + + var root = BuildNode(); + Assert(index == code_info_array.length); + return root; + } + + // Applies a list of the textual diff chunks onto the tree of functions. + // Determines status of each function (from unchanged to damaged). However + // children of unchanged functions are ignored. + function MarkChangedFunctions(code_info_tree, chunks) { + + // A convenient interator over diff chunks that also translates + // positions from old to new in a current non-changed part of script. + var chunk_it = new function() { + var chunk_index = 0; + var pos_diff = 0; + this.current = function() { return chunks[chunk_index]; } + this.next = function() { + var chunk = chunks[chunk_index]; + pos_diff = chunk.pos2 + chunk.len2 - (chunk.pos1 + chunk.len1); + chunk_index++; + } + this.done = function() { return chunk_index >= chunks.length; } + this.TranslatePos = function(pos) { return pos + pos_diff; } + }; + + // A recursive function that processes internals of a function and all its + // inner functions. Iterator chunk_it initially points to a chunk that is + // below function start. + function ProcessInternals(info_node) { + info_node.new_start_pos = chunk_it.TranslatePos( + info_node.info.start_position); + var child_index = 0; + var code_changed = false; + var source_changed = false; + // Simultaneously iterates over child functions and over chunks. + while (!chunk_it.done() && + chunk_it.current().pos1 < info_node.info.end_position) { + if (child_index < info_node.children.length) { + var child = info_node.children[child_index]; + + if (child.info.end_position <= chunk_it.current().pos1) { + ProcessUnchangedChild(child); + child_index++; + continue; + } else if (child.info.start_position >= + chunk_it.current().pos1 + chunk_it.current().len1) { + code_changed = true; + chunk_it.next(); + continue; + } else if (child.info.start_position <= chunk_it.current().pos1 && + child.info.end_position >= chunk_it.current().pos1 + + chunk_it.current().len1) { + ProcessInternals(child); + source_changed = source_changed || + ( child.status != FunctionStatus.UNCHANGED ); + code_changed = code_changed || + ( child.status == FunctionStatus.DAMAGED ); + child_index++; + continue; + } else { + code_changed = true; + child.status = FunctionStatus.DAMAGED; + child.status_explanation = + "Text diff overlaps with function boundary"; + child_index++; + continue; + } + } else { + if (chunk_it.current().pos1 + chunk_it.current().len1 <= + info_node.info.end_position) { + info_node.status = FunctionStatus.CHANGED; + chunk_it.next(); + continue; + } else { + info_node.status = FunctionStatus.DAMAGED; + info_node.status_explanation = + "Text diff overlaps with function boundary"; + return; + } + } + Assert("Unreachable", false); + } + while (child_index < info_node.children.length) { + var child = info_node.children[child_index]; + ProcessUnchangedChild(child); + child_index++; + } + if (code_changed) { + info_node.status = FunctionStatus.CHANGED; + } else if (source_changed) { + info_node.status = FunctionStatus.SOURCE_CHANGED; + } + info_node.new_end_pos = + chunk_it.TranslatePos(info_node.info.end_position); + } + + function ProcessUnchangedChild(node) { + node.new_start_pos = chunk_it.TranslatePos(node.info.start_position); + node.new_end_pos = chunk_it.TranslatePos(node.info.end_position); + } + + ProcessInternals(code_info_tree); + } + + // For ecah old function (if it is not damaged) tries to find a corresponding + // function in new script. Typically it should succeed (non-damaged functions + // by definition may only have changes inside their bodies). However there are + // reasons for corresponence not to be found; function with unmodified text + // in new script may become enclosed into other function; the innocent change + // inside function body may in fact be something like "} function B() {" that + // splits a function into 2 functions. + function FindCorrespondingFunctions(old_code_tree, new_code_tree) { + + // A recursive function that tries to find a correspondence for all + // child functions and for their inner functions. + function ProcessChildren(old_node, new_node) { + var old_children = old_node.children; + var new_children = new_node.children; + + var old_index = 0; + var new_index = 0; + while (old_index < old_children.length) { + if (old_children[old_index].status == FunctionStatus.DAMAGED) { + old_index++; + } else if (new_index < new_children.length) { + if (new_children[new_index].info.start_position < + old_children[old_index].new_start_pos) { + new_index++; + } else if (new_children[new_index].info.start_position == + old_children[old_index].new_start_pos) { + if (new_children[new_index].info.end_position == + old_children[old_index].new_end_pos) { + old_children[old_index].corresponding_node = + new_children[new_index]; + if (old_children[old_index].status != FunctionStatus.UNCHANGED) { + ProcessChildren(old_children[old_index], + new_children[new_index]); + if (old_children[old_index].status == FunctionStatus.DAMAGED) { + old_node.status = FunctionStatus.CHANGED; + } + } + } else { + old_children[old_index].status = FunctionStatus.DAMAGED; + old_children[old_index].status_explanation = + "No corresponding function in new script found"; + old_node.status = FunctionStatus.CHANGED; + } + new_index++; + old_index++; + } else { + old_children[old_index].status = FunctionStatus.DAMAGED; + old_children[old_index].status_explanation = + "No corresponding function in new script found"; + old_node.status = FunctionStatus.CHANGED; + old_index++; + } + } else { + old_children[old_index].status = FunctionStatus.DAMAGED; + old_children[old_index].status_explanation = + "No corresponding function in new script found"; + old_node.status = FunctionStatus.CHANGED; + old_index++; + } + } + + if (old_node.status == FunctionStatus.CHANGED) { + if (!CompareFunctionExpectations(old_node.info, new_node.info)) { + old_node.status = FunctionStatus.DAMAGED; + old_node.status_explanation = "Changed code expectations"; + } + } + } + + ProcessChildren(old_code_tree, new_code_tree); + + old_code_tree.corresponding_node = new_code_tree; + Assert(old_code_tree.status != FunctionStatus.DAMAGED, + "Script became damaged"); + } + // An object describing function compilation details. Its index fields // apply to indexes inside array that stores these objects. @@ -469,13 +763,12 @@ Debug.LiveEdit = new function() { // LiveEdit main entry point: changes a script text to a new string. function SetScriptSource(script, new_source, change_log) { var old_source = script.source; - var diff = FindSimpleDiff(old_source, new_source); - if (!diff) { + var diff = CompareStringsLinewise(old_source, new_source); + if (diff.length == 0) { + change_log.push( { empty_diff: true } ); return; } - ApplyPatch(script, diff.change_pos, diff.old_len, - new_source.substring(diff.change_pos, diff.change_pos + diff.new_len), - change_log); + ApplyPatchMultiChunk(script, diff, new_source, change_log); } // Function is public. this.SetScriptSource = SetScriptSource; |