xref: /external/v8/src/debug/liveedit.js

// Copyright 2012 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// LiveEdit feature implementation. The script should be executed after
// debug.js.

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

(function(global, utils) {
  "use strict";

  // -------------------------------------------------------------------
  // Imports

  var FindScriptSourcePosition = global.Debug.findScriptSourcePosition;
  var GlobalArray = global.Array;
  var MathFloor = global.Math.floor;
  var MathMax = global.Math.max;
  var SyntaxError = global.SyntaxError;

  // -------------------------------------------------------------------

  // 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, preview_only,
      change_log) {

    var old_source = script.source;

    // Gather compile information about old version of script.
    var old_compile_info = GatherCompileInfo(old_source, script);

    // Build tree structures for old and new versions of the script.
    var root_old_node = BuildCodeInfoTree(old_compile_info);

    var pos_translator = new PosTranslator(diff_array);

    // Analyze changes.
    MarkChangedFunctions(root_old_node, pos_translator.GetChunks());

    // Find all SharedFunctionInfo's that were compiled from this script.
    FindLiveSharedInfos(root_old_node, script);

    // Gather compile information about new version of script.
    var new_compile_info;
    try {
      new_compile_info = GatherCompileInfo(new_source, script);
    } catch (e) {
      var failure =
          new Failure("Failed to compile new version of script: " + e);
      if (e instanceof SyntaxError) {
        var details = {
          type: "liveedit_compile_error",
          syntaxErrorMessage: e.message
        };
        CopyErrorPositionToDetails(e, details);
        failure.details = details;
      }
      throw failure;
    }

    var max_function_literal_id = new_compile_info.reduce(
        (max, info) => MathMax(max, info.function_literal_id), 0);

    var root_new_node = BuildCodeInfoTree(new_compile_info);

    // Link recompiled script data with other data.
    FindCorrespondingFunctions(root_old_node, root_new_node);

    // Prepare to-do lists.
    var replace_code_list = new GlobalArray();
    var link_to_old_script_list = new GlobalArray();
    var link_to_original_script_list = new GlobalArray();
    var update_positions_list = new GlobalArray();

    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]);
        }
      }

      // Recursively collects all newly compiled functions that are going into
      // business and should have link to the actual script updated.
      function CollectNew(node_list) {
        for (var i = 0; i < node_list.length; i++) {
          link_to_original_script_list.push(node_list[i]);
          CollectNew(node_list[i].children);
        }
      }

      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);
        CollectNew(old_node.unmatched_new_nodes);
      }
      for (var i = 0; i < old_node.children.length; i++) {
        HarvestTodo(old_node.children[i]);
      }
    }

    var preview_description = {
        change_tree: DescribeChangeTree(root_old_node),
        textual_diff: {
          old_len: old_source.length,
          new_len: new_source.length,
          chunks: diff_array
        },
        updated: false
    };

    if (preview_only) {
      return preview_description;
    }

    HarvestTodo(root_old_node);

    // Collect shared infos for functions whose code need to be patched.
    var replaced_function_old_infos = new GlobalArray();
    var replaced_function_new_infos = new GlobalArray();
    for (var i = 0; i < replace_code_list.length; i++) {
      var old_infos = replace_code_list[i].live_shared_function_infos;
      var new_info =
          replace_code_list[i].corresponding_node.info.shared_function_info;

      if (old_infos) {
        for (var j = 0; j < old_infos.length; j++) {
          replaced_function_old_infos.push(old_infos[j]);
          replaced_function_new_infos.push(new_info);
        }
      }
    }

    // We haven't changed anything before this line yet.
    // Committing all changes.

    // Check that function being patched is not currently on stack or drop them.
    var dropped_functions_number =
        CheckStackActivations(replaced_function_old_infos,
                              replaced_function_new_infos,
                              change_log);

    // Our current implementation requires client to manually issue "step in"
    // command for correct stack state if the stack was modified.
    preview_description.stack_modified = dropped_functions_number != 0;

    var old_script;

    // Create an old script only if there are function that should be linked
    // to old version.
    if (link_to_old_script_list.length == 0) {
      %LiveEditReplaceScript(script, new_source, null);
      old_script = UNDEFINED;
    } else {
      var old_script_name = CreateNameForOldScript(script);

      // Update the script text and create a new script representing an old
      // version of the script.
      old_script = %LiveEditReplaceScript(script, new_source, old_script_name);

      var link_to_old_script_report = new GlobalArray();
      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(link_to_old_script_list[i], old_script,
            link_to_old_script_report);
      }

      preview_description.created_script_name = old_script_name;
    }

    for (var i = 0; i < replace_code_list.length; i++) {
      PatchFunctionCode(replace_code_list[i], change_log);
    }

    var position_patch_report = new GlobalArray();
    change_log.push( {position_patched: position_patch_report} );

    for (var i = 0; i < update_positions_list.length; i++) {
      // TODO(LiveEdit): take into account whether it's source_changed or
      // unchanged and whether positions changed at all.
      PatchPositions(update_positions_list[i], diff_array,
          position_patch_report);

      if (update_positions_list[i].live_shared_function_infos) {
        var new_function_literal_id =
            update_positions_list[i]
                .corresponding_node.info.function_literal_id;
        update_positions_list[i].live_shared_function_infos.forEach(function(
            info) {
          %LiveEditFunctionSourceUpdated(
              info.raw_array, new_function_literal_id);
        });
      }
    }

    %LiveEditFixupScript(script, max_function_literal_id);

    // Link all the functions we're going to use to an actual script.
    for (var i = 0; i < link_to_original_script_list.length; i++) {
      %LiveEditFunctionSetScript(
          link_to_original_script_list[i].info.shared_function_info, script);
    }

    preview_description.updated = true;
    return preview_description;
  }

  // Fully compiles source string as a script. Returns Array of
  // FunctionCompileInfo -- a descriptions of all functions of the script.
  // Elements of array are ordered by start positions of functions (from top
  // to bottom) in the source. Fields outer_index and next_sibling_index help
  // to navigate the nesting structure of functions.
  //
  // All functions get compiled linked to script provided as parameter script.
  // TODO(LiveEdit): consider not using actual scripts as script, because
  // we have to manually erase all links right after compile.
  function GatherCompileInfo(source, script) {
    // Get function info, elements are partially sorted (it is a tree of
    // nested functions serialized as parent followed by serialized children.
    var raw_compile_info = %LiveEditGatherCompileInfo(script, source);

    // Sort function infos by start position field.
    var compile_info = new GlobalArray();
    var old_index_map = new GlobalArray();
    for (var i = 0; i < raw_compile_info.length; i++) {
      var info = new FunctionCompileInfo(raw_compile_info[i]);
      // Remove all links to the actual script. Breakpoints system and
      // LiveEdit itself believe that any function in heap that points to a
      // particular script is a regular function.
      // For some functions we will restore this link later.
      %LiveEditFunctionSetScript(info.shared_function_info, UNDEFINED);
      compile_info.push(info);
      old_index_map.push(i);
    }

    for (var i = 0; i < compile_info.length; i++) {
      var k = i;
      for (var j = i + 1; j < compile_info.length; j++) {
        if (compile_info[k].start_position > compile_info[j].start_position) {
          k = j;
        }
      }
      if (k != i) {
        var temp_info = compile_info[k];
        var temp_index = old_index_map[k];
        compile_info[k] = compile_info[i];
        old_index_map[k] = old_index_map[i];
        compile_info[i] = temp_info;
        old_index_map[i] = temp_index;
      }
    }

    // After sorting update outer_index field using old_index_map. Also
    // set next_sibling_index field.
    var current_index = 0;

    // The recursive function, that goes over all children of a particular
    // node (i.e. function info).
    function ResetIndexes(new_parent_index, old_parent_index) {
      var previous_sibling = -1;
      while (current_index < compile_info.length &&
          compile_info[current_index].outer_index == old_parent_index) {
        var saved_index = current_index;
        compile_info[saved_index].outer_index = new_parent_index;
        if (previous_sibling != -1) {
          compile_info[previous_sibling].next_sibling_index = saved_index;
        }
        previous_sibling = saved_index;
        current_index++;
        ResetIndexes(saved_index, old_index_map[saved_index]);
      }
      if (previous_sibling != -1) {
        compile_info[previous_sibling].next_sibling_index = -1;
      }
    }

    ResetIndexes(-1, -1);
    Assert(current_index == compile_info.length);

    return compile_info;
  }


  // Replaces function's Code.
  function PatchFunctionCode(old_node, change_log) {
    var new_info = old_node.corresponding_node.info;
    if (old_node.live_shared_function_infos) {
      old_node.live_shared_function_infos.forEach(function (old_info) {
        %LiveEditReplaceFunctionCode(new_info.raw_array,
                                     old_info.raw_array);

        // The function got a new code. However, this new code brings all new
        // instances of SharedFunctionInfo for nested functions. However,
        // we want the original instances to be used wherever possible.
        // (This is because old instances and new instances will be both
        // linked to a script and breakpoints subsystem does not really
        // expects this; neither does LiveEdit subsystem on next call).
        for (var i = 0; i < old_node.children.length; i++) {
          if (old_node.children[i].corresponding_node) {
            var corresponding_child_info =
                old_node.children[i].corresponding_node.info.
                    shared_function_info;

            if (old_node.children[i].live_shared_function_infos) {
              old_node.children[i].live_shared_function_infos.
                  forEach(function (old_child_info) {
                    %LiveEditReplaceRefToNestedFunction(
                        old_info.info,
                        corresponding_child_info,
                        old_child_info.info);
                  });
            }
          }
        }
      });

      change_log.push( {function_patched: new_info.function_name} );
    } else {
      change_log.push( {function_patched: new_info.function_name,
          function_info_not_found: true} );
    }
  }


  // 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(old_info_node, old_script, report_array) {
    if (old_info_node.live_shared_function_infos) {
      old_info_node.live_shared_function_infos.
          forEach(function (info) {
            %LiveEditFunctionSetScript(info.info, old_script);
          });

      report_array.push( { name: old_info_node.info.function_name } );
    } else {
      report_array.push(
          { name: old_info_node.info.function_name, not_found: true } );
    }
  }

  function Assert(condition, message) {
    if (!condition) {
      if (message) {
        throw "Assert " + message;
      } else {
        throw "Assert";
      }
    }
  }

  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 GlobalArray();
    var current_diff = 0;
    for (var i = 0; i < diff_array.length; i += 3) {
      var pos1_begin = diff_array[i];
      var pos2_begin = pos1_begin + current_diff;
      var pos1_end = diff_array[i + 1];
      var pos2_end = diff_array[i + 2];
      chunks.push(new DiffChunk(pos1_begin, pos2_begin, pos1_end - pos1_begin,
          pos2_end - pos2_begin));
      current_diff = pos2_end - pos1_end;
    }
    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].pos1) {
      return pos;
    }
    var chunk_index1 = 0;
    var chunk_index2 = array.length - 1;

    while (chunk_index1 < chunk_index2) {
      var middle_index = MathFloor((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.DefaultInsideChunkHandler;
    }
    return inside_chunk_handler(pos, chunk);
  };

  PosTranslator.DefaultInsideChunkHandler = function(pos, diff_chunk) {
    Assert(false, "Cannot translate position in changed area");
  };

  PosTranslator.ShiftWithTopInsideChunkHandler =
      function(pos, diff_chunk) {
    // We carelessly do not check whether we stay inside the chunk after
    // translation.
    return pos - diff_chunk.pos1 + diff_chunk.pos2;
  };

  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 = UNDEFINED;

    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 = UNDEFINED;
    this.new_start_pos = UNDEFINED;
    this.new_end_pos = UNDEFINED;
    this.corresponding_node = UNDEFINED;
    this.unmatched_new_nodes = UNDEFINED;

    // 'Textual' correspondence/matching is weaker than 'pure'
    // correspondence/matching. We need 'textual' level for visual presentation
    // in UI, we use 'pure' level for actual code manipulation.
    // Sometimes only function body is changed (functions in old and new script
    // textually correspond), but we cannot patch the code, so we see them
    // as an old function deleted and new function created.
    this.textual_corresponding_node = UNDEFINED;
    this.textually_unmatched_new_nodes = UNDEFINED;

    this.live_shared_function_infos = UNDEFINED;
  }

  // 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 GlobalArray();
      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 iterator 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 each 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 correspondence 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 ProcessNode(old_node, new_node) {
      var scope_change_description =
          IsFunctionContextLocalsChanged(old_node.info, new_node.info);
      if (scope_change_description) {
        old_node.status = FunctionStatus.CHANGED;
      }

      var old_children = old_node.children;
      var new_children = new_node.children;

      var unmatched_new_nodes_list = [];
      var textually_unmatched_new_nodes_list = [];

      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) {
            unmatched_new_nodes_list.push(new_children[new_index]);
            textually_unmatched_new_nodes_list.push(new_children[new_index]);
            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];
              old_children[old_index].textual_corresponding_node =
                  new_children[new_index];
              if (scope_change_description) {
                old_children[old_index].status = FunctionStatus.DAMAGED;
                old_children[old_index].status_explanation =
                    "Enclosing function is now incompatible. " +
                    scope_change_description;
                old_children[old_index].corresponding_node = UNDEFINED;
              } else if (old_children[old_index].status !=
                  FunctionStatus.UNCHANGED) {
                ProcessNode(old_children[old_index],
                    new_children[new_index]);
                if (old_children[old_index].status == FunctionStatus.DAMAGED) {
                  unmatched_new_nodes_list.push(
                      old_children[old_index].corresponding_node);
                  old_children[old_index].corresponding_node = UNDEFINED;
                  old_node.status = FunctionStatus.CHANGED;
                }
              } else {
                ProcessNode(old_children[old_index], new_children[new_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;
              unmatched_new_nodes_list.push(new_children[new_index]);
              textually_unmatched_new_nodes_list.push(new_children[new_index]);
            }
            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++;
        }
      }

      while (new_index < new_children.length) {
        unmatched_new_nodes_list.push(new_children[new_index]);
        textually_unmatched_new_nodes_list.push(new_children[new_index]);
        new_index++;
      }

      if (old_node.status == FunctionStatus.CHANGED) {
        if (old_node.info.param_num != new_node.info.param_num) {
          old_node.status = FunctionStatus.DAMAGED;
          old_node.status_explanation = "Changed parameter number: " +
              old_node.info.param_num + " and " + new_node.info.param_num;
        }
      }
      old_node.unmatched_new_nodes = unmatched_new_nodes_list;
      old_node.textually_unmatched_new_nodes =
          textually_unmatched_new_nodes_list;
    }

    ProcessNode(old_code_tree, new_code_tree);

    old_code_tree.corresponding_node = new_code_tree;
    old_code_tree.textual_corresponding_node = new_code_tree;

    Assert(old_code_tree.status != FunctionStatus.DAMAGED,
        "Script became damaged");
  }

  function FindLiveSharedInfos(old_code_tree, script) {
    var shared_raw_list = %LiveEditFindSharedFunctionInfosForScript(script);

    var shared_infos = new GlobalArray();

    for (var i = 0; i < shared_raw_list.length; i++) {
      shared_infos.push(new SharedInfoWrapper(shared_raw_list[i]));
    }

    // Finds all SharedFunctionInfos that corresponds to compile info
    // in old version of the script.
    function FindFunctionInfos(compile_info) {
      var wrappers = [];

      for (var i = 0; i < shared_infos.length; i++) {
        var wrapper = shared_infos[i];
        if (wrapper.start_position == compile_info.start_position &&
            wrapper.end_position == compile_info.end_position) {
          wrappers.push(wrapper);
        }
      }

      if (wrappers.length > 0) {
        return wrappers;
      }
    }

    function TraverseTree(node) {
      node.live_shared_function_infos = FindFunctionInfos(node.info);

      for (var i = 0; i < node.children.length; i++) {
        TraverseTree(node.children[i]);
      }
    }

    TraverseTree(old_code_tree);
  }


  // An object describing function compilation details. Its index fields
  // apply to indexes inside array that stores these objects.
  function FunctionCompileInfo(raw_array) {
    this.function_name = raw_array[0];
    this.start_position = raw_array[1];
    this.end_position = raw_array[2];
    this.param_num = raw_array[3];
    this.scope_info = raw_array[4];
    this.outer_index = raw_array[5];
    this.shared_function_info = raw_array[6];
    this.function_literal_id = raw_array[7];
    this.next_sibling_index = null;
    this.raw_array = raw_array;
  }

  function SharedInfoWrapper(raw_array) {
    this.function_name = raw_array[0];
    this.start_position = raw_array[1];
    this.end_position = raw_array[2];
    this.info = raw_array[3];
    this.raw_array = raw_array;
  }

  // Changes positions (including all statements) in function.
  function PatchPositions(old_info_node, diff_array, report_array) {
    if (old_info_node.live_shared_function_infos) {
      old_info_node.live_shared_function_infos.forEach(function (info) {
          %LiveEditPatchFunctionPositions(info.raw_array,
                                          diff_array);
      });

      report_array.push( { name: old_info_node.info.function_name } );
    } else {
      // TODO(LiveEdit): function is not compiled yet or is already collected.
      report_array.push(
          { name: old_info_node.info.function_name, info_not_found: true } );
    }
  }

  // Adds a suffix to script name to mark that it is old version.
  function CreateNameForOldScript(script) {
    // TODO(635): try better than this; support several changes.
    return script.name + " (old)";
  }

  // Compares a function scope heap structure, old and new version, whether it
  // changed or not. Returns explanation if they differ.
  function IsFunctionContextLocalsChanged(function_info1, function_info2) {
    var scope_info1 = function_info1.scope_info;
    var scope_info2 = function_info2.scope_info;

    var scope_info1_text;
    var scope_info2_text;

    if (scope_info1) {
      scope_info1_text = scope_info1.toString();
    } else {
      scope_info1_text = "";
    }
    if (scope_info2) {
      scope_info2_text = scope_info2.toString();
    } else {
      scope_info2_text = "";
    }

    if (scope_info1_text != scope_info2_text) {
      return "Variable map changed: [" + scope_info1_text +
          "] => [" + scope_info2_text + "]";
    }
    // No differences. Return undefined.
    return;
  }

  // Minifier forward declaration.
  var FunctionPatchabilityStatus;

  // For array of wrapped shared function infos checks that none of them
  // have activations on stack (of any thread). Throws a Failure exception
  // if this proves to be false.
  function CheckStackActivations(old_shared_wrapper_list,
                                 new_shared_list,
                                 change_log) {
    var old_shared_list = new GlobalArray();
    for (var i = 0; i < old_shared_wrapper_list.length; i++) {
      old_shared_list[i] = old_shared_wrapper_list[i].info;
    }
    var result = %LiveEditCheckAndDropActivations(
                     old_shared_list, new_shared_list, true);
    if (result[old_shared_wrapper_list.length]) {
      // Extra array element may contain error message.
      throw new Failure(result[old_shared_wrapper_list.length]);
    }

    var problems = new GlobalArray();
    var dropped = new GlobalArray();
    for (var i = 0; i < old_shared_list.length; i++) {
      var shared = old_shared_wrapper_list[i];
      if (result[i] == FunctionPatchabilityStatus.REPLACED_ON_ACTIVE_STACK) {
        dropped.push({ name: shared.function_name } );
      } else if (result[i] != FunctionPatchabilityStatus.AVAILABLE_FOR_PATCH) {
        var description = {
            name: shared.function_name,
            start_pos: shared.start_position,
            end_pos: shared.end_position,
            replace_problem:
                FunctionPatchabilityStatus.SymbolName(result[i])
        };
        problems.push(description);
      }
    }
    if (dropped.length > 0) {
      change_log.push({ dropped_from_stack: dropped });
    }
    if (problems.length > 0) {
      change_log.push( { functions_on_stack: problems } );
      throw new Failure("Blocked by functions on stack");
    }

    return dropped.length;
  }

  // A copy of the FunctionPatchabilityStatus enum from liveedit.h
  var FunctionPatchabilityStatus = {
      AVAILABLE_FOR_PATCH: 1,
      BLOCKED_ON_ACTIVE_STACK: 2,
      BLOCKED_ON_OTHER_STACK: 3,
      BLOCKED_UNDER_NATIVE_CODE: 4,
      REPLACED_ON_ACTIVE_STACK: 5,
      BLOCKED_UNDER_GENERATOR: 6,
      BLOCKED_ACTIVE_GENERATOR: 7,
      BLOCKED_NO_NEW_TARGET_ON_RESTART: 8
  };

  FunctionPatchabilityStatus.SymbolName = function(code) {
    var enumeration = FunctionPatchabilityStatus;
    for (var name in enumeration) {
      if (enumeration[name] == code) {
        return name;
      }
    }
  };


  // A logical failure in liveedit process. This means that change_log
  // is valid and consistent description of what happened.
  function Failure(message) {
    this.message = message;
  }

  Failure.prototype.toString = function() {
    return "LiveEdit Failure: " + this.message;
  };

  function CopyErrorPositionToDetails(e, details) {
    function createPositionStruct(script, position) {
      if (position == -1) return;
      var location = script.locationFromPosition(position, true);
      if (location == null) return;
      return {
        line: location.line + 1,
        column: location.column + 1,
        position: position
      };
    }

    if (!("scriptObject" in e) || !("startPosition" in e)) {
      return;
    }

    var script = e.scriptObject;

    var position_struct = {
      start: createPositionStruct(script, e.startPosition),
      end: createPositionStruct(script, e.endPosition)
    };
    details.position = position_struct;
  }

  // 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 = CompareStrings(old_source, new_source);
    return ApplyPatchMultiChunk(script, diff, new_source, preview_only,
        change_log);
  }

  function CompareStrings(s1, s2) {
    return %LiveEditCompareStrings(s1, s2);
  }

  // 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.
  // 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 ApplySingleChunkPatch(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, false, change_log);
  }

  // Creates JSON description for a change tree.
  function DescribeChangeTree(old_code_tree) {

    function ProcessOldNode(node) {
      var child_infos = [];
      for (var i = 0; i < node.children.length; i++) {
        var child = node.children[i];
        if (child.status != FunctionStatus.UNCHANGED) {
          child_infos.push(ProcessOldNode(child));
        }
      }
      var new_child_infos = [];
      if (node.textually_unmatched_new_nodes) {
        for (var i = 0; i < node.textually_unmatched_new_nodes.length; i++) {
          var child = node.textually_unmatched_new_nodes[i];
          new_child_infos.push(ProcessNewNode(child));
        }
      }
      var res = {
        name: node.info.function_name,
        positions: DescribePositions(node),
        status: node.status,
        children: child_infos,
        new_children: new_child_infos
      };
      if (node.status_explanation) {
        res.status_explanation = node.status_explanation;
      }
      if (node.textual_corresponding_node) {
        res.new_positions = DescribePositions(node.textual_corresponding_node);
      }
      return res;
    }

    function ProcessNewNode(node) {
      var child_infos = [];
      // Do not list ancestors.
      if (false) {
        for (var i = 0; i < node.children.length; i++) {
          child_infos.push(ProcessNewNode(node.children[i]));
        }
      }
      var res = {
        name: node.info.function_name,
        positions: DescribePositions(node),
        children: child_infos,
      };
      return res;
    }

    function DescribePositions(node) {
      return {
        start_position: node.info.start_position,
        end_position: node.info.end_position
      };
    }

    return ProcessOldNode(old_code_tree);
  }

  // -------------------------------------------------------------------
  // Exports

  var LiveEdit = {};
  LiveEdit.SetScriptSource = SetScriptSource;
  LiveEdit.ApplyPatchMultiChunk = ApplyPatchMultiChunk;
  LiveEdit.Failure = Failure;

  LiveEdit.TestApi = {
    PosTranslator: PosTranslator,
    CompareStrings: CompareStrings,
    ApplySingleChunkPatch: ApplySingleChunkPatch
  };

  global.Debug.LiveEdit = LiveEdit;

})