liveedit-debugger.js 39.5 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4 5 6 7

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

8 9 10 11 12 13 14 15 16 17 18 19 20 21
// 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.
22 23 24

"use strict";

25 26
Debug.LiveEdit = new function() {

27 28
  // Forward declaration for minifier.
  var FunctionStatus;
29

30 31
  var NEEDS_STEP_IN_PROPERTY_NAME = "stack_update_needs_step_in";

32 33 34
  // 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)
35 36
  function ApplyPatchMultiChunk(script, diff_array, new_source, preview_only,
      change_log) {
37

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
38
    var old_source = script.source;
39

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
40
    // Gather compile information about old version of script.
41
    var old_compile_info = GatherCompileInfo(old_source, script);
42

43 44 45 46 47 48 49 50 51 52
    // 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);
53

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
54 55 56
    // Gather compile information about new version of script.
    var new_compile_info;
    try {
57
      new_compile_info = GatherCompileInfo(new_source, script);
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
58
    } catch (e) {
59 60 61 62 63 64 65 66 67 68 69
      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;
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
70
    }
71 72
    var root_new_node = BuildCodeInfoTree(new_compile_info);

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

76 77 78
    // Prepare to-do lists.
    var replace_code_list = new Array();
    var link_to_old_script_list = new Array();
79
    var link_to_original_script_list = new Array();
80 81 82 83 84 85 86 87 88
    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]);
        }
      }
89 90

      // Recursively collects all newly compiled functions that are going into
91
      // business and should have link to the actual script updated.
92 93 94 95 96 97
      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);
        }
      }
98

99 100 101 102 103 104 105 106 107 108
      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);
109
        CollectNew(old_node.unmatched_new_nodes);
110 111 112 113
      }
      for (var i = 0; i < old_node.children.length; i++) {
        HarvestTodo(old_node.children[i]);
      }
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
114
    }
115

116 117 118 119 120 121 122 123 124
    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
    };
125

126 127 128
    if (preview_only) {
      return preview_description;
    }
129

130
    HarvestTodo(root_old_node);
131

132 133 134
    // 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++) {
135 136 137 138
      var live_shared_function_infos =
          replace_code_list[i].live_shared_function_infos;

      if (live_shared_function_infos) {
139 140
        for (var j = 0; j < live_shared_function_infos.length; j++) {
          replaced_function_infos.push(live_shared_function_infos[j]);
141
        }
142 143 144 145
      }
    }

    // We haven't changed anything before this line yet.
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
146
    // Committing all changes.
147

148 149 150
    // Check that function being patched is not currently on stack or drop them.
    var dropped_functions_number =
        CheckStackActivations(replaced_function_infos, change_log);
151 152 153

    preview_description.stack_modified = dropped_functions_number != 0;

154 155
    // Our current implementation requires client to manually issue "step in"
    // command for correct stack state.
156
    preview_description[NEEDS_STEP_IN_PROPERTY_NAME] =
157 158
        preview_description.stack_modified;

159
    // Start with breakpoints. Convert their line/column positions and
160 161
    // temporary remove.
    var break_points_restorer = TemporaryRemoveBreakPoints(script, change_log);
162

163 164 165 166 167 168
    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);
169
      old_script = UNDEFINED;
170
    } else {
171
      var old_script_name = CreateNameForOldScript(script);
172

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

178 179
      var link_to_old_script_report = new Array();
      change_log.push( { linked_to_old_script: link_to_old_script_report } );
180

181 182
      // We need to link to old script all former nested functions.
      for (var i = 0; i < link_to_old_script_list.length; i++) {
183 184
        LinkToOldScript(link_to_old_script_list[i], old_script,
            link_to_old_script_report);
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
185
      }
186

187
      preview_description.created_script_name = old_script_name;
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
188
    }
189

190 191 192 193 194
    // Link to an actual script all the functions that we are going to use.
    for (var i = 0; i < link_to_original_script_list.length; i++) {
      %LiveEditFunctionSetScript(
          link_to_original_script_list[i].info.shared_function_info, script);
    }
195 196

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

200 201
    var position_patch_report = new Array();
    change_log.push( {position_patched: position_patch_report} );
202

203
    for (var i = 0; i < update_positions_list.length; i++) {
204
      // TODO(LiveEdit): take into account whether it's source_changed or
205
      // unchanged and whether positions changed at all.
206 207
      PatchPositions(update_positions_list[i], diff_array,
          position_patch_report);
208 209 210 211 212 213 214

      if (update_positions_list[i].live_shared_function_infos) {
        update_positions_list[i].live_shared_function_infos.
            forEach(function (info) {
                %LiveEditFunctionSourceUpdated(info.raw_array);
              });
      }
215
    }
216

217
    break_points_restorer(pos_translator, old_script);
218

219 220
    preview_description.updated = true;
    return preview_description;
221
  }
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
222
  // Function is public.
223 224
  this.ApplyPatchMultiChunk = ApplyPatchMultiChunk;

225

226 227 228 229 230 231 232 233
  // 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
234
  // we have to manually erase all links right after compile.
235 236 237 238 239 240 241 242 243 244 245 246 247 248
  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 Array();
    var old_index_map = new Array();
    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.
249
      %LiveEditFunctionSetScript(info.shared_function_info, UNDEFINED);
250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
      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;
      }
    }

271
    // After sorting update outer_index field using old_index_map. Also
272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300
    // 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;
  }

301

302 303 304
  // Replaces function's Code.
  function PatchFunctionCode(old_node, change_log) {
    var new_info = old_node.corresponding_node.info;
305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324
    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) {
325 326 327 328
                    %LiveEditReplaceRefToNestedFunction(
                        old_info.info,
                        corresponding_child_info,
                        old_child_info.info);
329 330
                  });
            }
331 332
          }
        }
333
      });
334

335 336 337 338 339 340 341
      change_log.push( {function_patched: new_info.function_name} );
    } else {
      change_log.push( {function_patched: new_info.function_name,
          function_info_not_found: true} );
    }
  }

342

343 344 345 346
  // 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) {
347 348 349 350 351 352 353
    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 } );
354 355 356 357 358
    } else {
      report_array.push(
          { name: old_info_node.info.function_name, not_found: true } );
    }
  }
359

360 361 362 363

  // Returns function that restores breakpoints.
  function TemporaryRemoveBreakPoints(original_script, change_log) {
    var script_break_points = GetScriptBreakPoints(original_script);
364

365 366 367 368 369 370 371 372
    var break_points_update_report = [];
    change_log.push( { break_points_update: break_points_update_report } );

    var break_point_old_positions = [];
    for (var i = 0; i < script_break_points.length; i++) {
      var break_point = script_break_points[i];

      break_point.clear();
373 374

      // TODO(LiveEdit): be careful with resource offset here.
375 376
      var break_point_position = Debug.findScriptSourcePosition(original_script,
          break_point.line(), break_point.column());
377

378 379 380 381
      var old_position_description = {
          position: break_point_position,
          line: break_point.line(),
          column: break_point.column()
382
      };
383 384
      break_point_old_positions.push(old_position_description);
    }
385 386


387 388 389 390 391 392 393 394 395 396
    // Restores breakpoints and creates their copies in the "old" copy of
    // the script.
    return function (pos_translator, old_script_copy_opt) {
      // Update breakpoints (change positions and restore them in old version
      // of script.
      for (var i = 0; i < script_break_points.length; i++) {
        var break_point = script_break_points[i];
        if (old_script_copy_opt) {
          var clone = break_point.cloneForOtherScript(old_script_copy_opt);
          clone.set(old_script_copy_opt);
397

398 399 400
          break_points_update_report.push( {
            type: "copied_to_old",
            id: break_point.number(),
401
            new_id: clone.number(),
402 403 404
            positions: break_point_old_positions[i]
            } );
        }
405

406 407 408
        var updated_position = pos_translator.Translate(
            break_point_old_positions[i].position,
            PosTranslator.ShiftWithTopInsideChunkHandler);
409

410 411 412 413 414 415 416 417 418
        var new_location =
            original_script.locationFromPosition(updated_position, false);

        break_point.update_positions(new_location.line, new_location.column);

        var new_position_description = {
            position: updated_position,
            line: new_location.line,
            column: new_location.column
419
        };
420

421
        break_point.set(original_script);
422

423 424 425 426 427 428
        break_points_update_report.push( { type: "position_changed",
          id: break_point.number(),
          old_positions: break_point_old_positions[i],
          new_positions: new_position_description
          } );
      }
429
    };
430 431
  }

432

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
433 434 435 436 437 438 439 440
  function Assert(condition, message) {
    if (!condition) {
      if (message) {
        throw "Assert " + message;
      } else {
        throw "Assert";
      }
    }
441
  }
442 443 444 445 446 447 448

  function DiffChunk(pos1, pos2, len1, len2) {
    this.pos1 = pos1;
    this.pos2 = pos2;
    this.len1 = len1;
    this.len2 = len2;
  }
449

450 451
  function PosTranslator(diff_array) {
    var chunks = new Array();
452
    var current_diff = 0;
453
    for (var i = 0; i < diff_array.length; i += 3) {
454 455 456 457 458 459
      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));
460
      current_diff = pos2_end - pos1_end;
461 462 463 464 465
    }
    this.chunks = chunks;
  }
  PosTranslator.prototype.GetChunks = function() {
    return this.chunks;
466
  };
467

468
  PosTranslator.prototype.Translate = function(pos, inside_chunk_handler) {
469
    var array = this.chunks;
470
    if (array.length == 0 || pos < array[0].pos1) {
471 472 473 474 475 476
      return pos;
    }
    var chunk_index1 = 0;
    var chunk_index2 = array.length - 1;

    while (chunk_index1 < chunk_index2) {
477
      var middle_index = Math.floor((chunk_index1 + chunk_index2) / 2);
478 479 480 481 482 483 484 485
      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) {
486
      return pos + chunk.pos2 + chunk.len2 - chunk.pos1 - chunk.len1;
487
    }
488

489
    if (!inside_chunk_handler) {
490
      inside_chunk_handler = PosTranslator.DefaultInsideChunkHandler;
491
    }
492
    return inside_chunk_handler(pos, chunk);
493
  };
494

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

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

506 507
  var FunctionStatus = {
      // No change to function or its inner functions; however its positions
508
      // in script may have been shifted.
509 510 511 512 513 514 515 516 517
      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"
518
  };
519

520 521 522 523
  function CodeInfoTreeNode(code_info, children, array_index) {
    this.info = code_info;
    this.children = children;
    // an index in array of compile_info
524
    this.array_index = array_index;
525
    this.parent = UNDEFINED;
526

527 528 529
    this.status = FunctionStatus.UNCHANGED;
    // Status explanation is used for debugging purposes and will be shown
    // in user UI if some explanations are needed.
530 531 532 533 534
    this.status_explanation = UNDEFINED;
    this.new_start_pos = UNDEFINED;
    this.new_end_pos = UNDEFINED;
    this.corresponding_node = UNDEFINED;
    this.unmatched_new_nodes = UNDEFINED;
535

536 537 538 539 540
    // '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
541
    // as an old function deleted and new function created.
542 543
    this.textual_corresponding_node = UNDEFINED;
    this.textually_unmatched_new_nodes = UNDEFINED;
544

545
    this.live_shared_function_infos = UNDEFINED;
546
  }
547

548 549 550 551 552 553
  // 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;

554
    // Recursive function that builds a branch of tree.
555 556 557 558 559 560 561 562 563 564 565 566 567 568 569
    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;
    }
570

571 572 573 574 575 576 577 578 579 580
    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) {

581
    // A convenient iterator over diff chunks that also translates
582 583 584 585
    // 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;
586
      this.current = function() { return chunks[chunk_index]; };
587 588
      this.next = function() {
        var chunk = chunks[chunk_index];
589
        pos_diff = chunk.pos2 + chunk.len2 - (chunk.pos1 + chunk.len1);
590
        chunk_index++;
591 592 593
      };
      this.done = function() { return chunk_index >= chunks.length; };
      this.TranslatePos = function(pos) { return pos + pos_diff; };
594 595 596 597 598 599 600
    };

    // 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(
601
          info_node.info.start_position);
602 603 604 605 606 607 608 609
      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];
610

611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638
          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 {
639
          if (chunk_it.current().pos1 + chunk_it.current().len1 <=
640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663
              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 =
664
          chunk_it.TranslatePos(info_node.info.end_position);
665
    }
666

667 668 669 670
    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);
    }
671

672 673 674
    ProcessInternals(code_info_tree);
  }

675
  // For each old function (if it is not damaged) tries to find a corresponding
676 677
  // function in new script. Typically it should succeed (non-damaged functions
  // by definition may only have changes inside their bodies). However there are
678
  // reasons for correspondence not to be found; function with unmodified text
679 680 681 682 683 684 685
  // 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.
686 687 688 689 690 691 692
    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;
      }

693 694
      var old_children = old_node.children;
      var new_children = new_node.children;
695

696
      var unmatched_new_nodes_list = [];
697
      var textually_unmatched_new_nodes_list = [];
698 699 700 701 702 703 704 705 706

      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) {
707
            unmatched_new_nodes_list.push(new_children[new_index]);
708
            textually_unmatched_new_nodes_list.push(new_children[new_index]);
709 710 711 712 713 714 715
            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];
716 717
              old_children[old_index].textual_corresponding_node =
                  new_children[new_index];
718 719 720 721 722
              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;
723
                old_children[old_index].corresponding_node = UNDEFINED;
724 725 726
              } else if (old_children[old_index].status !=
                  FunctionStatus.UNCHANGED) {
                ProcessNode(old_children[old_index],
727 728
                    new_children[new_index]);
                if (old_children[old_index].status == FunctionStatus.DAMAGED) {
729 730
                  unmatched_new_nodes_list.push(
                      old_children[old_index].corresponding_node);
731
                  old_children[old_index].corresponding_node = UNDEFINED;
732 733 734 735 736 737 738 739
                  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;
740
              unmatched_new_nodes_list.push(new_children[new_index]);
741
              textually_unmatched_new_nodes_list.push(new_children[new_index]);
742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759
            }
            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++;
        }
      }
760

761 762
      while (new_index < new_children.length) {
        unmatched_new_nodes_list.push(new_children[new_index]);
763
        textually_unmatched_new_nodes_list.push(new_children[new_index]);
764 765
        new_index++;
      }
766

767
      if (old_node.status == FunctionStatus.CHANGED) {
768
        if (old_node.info.param_num != new_node.info.param_num) {
769
          old_node.status = FunctionStatus.DAMAGED;
770 771
          old_node.status_explanation = "Changed parameter number: " +
              old_node.info.param_num + " and " + new_node.info.param_num;
772 773
        }
      }
774
      old_node.unmatched_new_nodes = unmatched_new_nodes_list;
775 776
      old_node.textually_unmatched_new_nodes =
          textually_unmatched_new_nodes_list;
777 778
    }

779
    ProcessNode(old_code_tree, new_code_tree);
780

781
    old_code_tree.corresponding_node = new_code_tree;
782 783
    old_code_tree.textual_corresponding_node = new_code_tree;

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

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

791
    var shared_infos = new Array();
792

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

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

802 803 804 805
      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) {
806
          wrappers.push(wrapper);
807 808
        }
      }
809 810 811 812

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

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

818 819 820 821 822 823 824
      for (var i = 0; i < node.children.length; i++) {
        TraverseTree(node.children[i]);
      }
    }

    TraverseTree(old_code_tree);
  }
825

826

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
827 828 829 830 831 832 833 834
  // 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.code = raw_array[4];
835 836 837 838
    this.code_scope_info = raw_array[5];
    this.scope_info = raw_array[6];
    this.outer_index = raw_array[7];
    this.shared_function_info = raw_array[8];
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
839 840
    this.next_sibling_index = null;
    this.raw_array = raw_array;
841
  }
842

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
843 844 845 846 847 848
  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;
849
  }
850

851
  // Changes positions (including all statements) in function.
852
  function PatchPositions(old_info_node, diff_array, report_array) {
853 854 855 856 857 858 859 860
    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 {
861
      // TODO(LiveEdit): function is not compiled yet or is already collected.
862
      report_array.push(
863 864 865 866
          { name: old_info_node.info.function_name, info_not_found: true } );
    }
  }

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
867 868 869 870
  // 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)";
871
  }
872

873
  // Compares a function scope heap structure, old and new version, whether it
874
  // changed or not. Returns explanation if they differ.
875
  function IsFunctionContextLocalsChanged(function_info1, function_info2) {
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
876 877
    var scope_info1 = function_info1.scope_info;
    var scope_info2 = function_info2.scope_info;
878

879 880 881
    var scope_info1_text;
    var scope_info2_text;

882
    if (scope_info1) {
883
      scope_info1_text = scope_info1.toString();
884 885
    } else {
      scope_info1_text = "";
886
    }
887
    if (scope_info2) {
888
      scope_info2_text = scope_info2.toString();
889 890
    } else {
      scope_info2_text = "";
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
891
    }
892

893
    if (scope_info1_text != scope_info2_text) {
894 895
      return "Variable map changed: [" + scope_info1_text +
          "] => [" + scope_info2_text + "]";
896 897 898
    }
    // No differences. Return undefined.
    return;
899
  }
900

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
901 902
  // Minifier forward declaration.
  var FunctionPatchabilityStatus;
903

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
904 905 906 907 908 909 910 911 912 913 914 915 916
  // 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(shared_wrapper_list, change_log) {
    var shared_list = new Array();
    for (var i = 0; i < shared_wrapper_list.length; i++) {
      shared_list[i] = shared_wrapper_list[i].info;
    }
    var result = %LiveEditCheckAndDropActivations(shared_list, true);
    if (result[shared_list.length]) {
      // Extra array element may contain error message.
      throw new Failure(result[shared_list.length]);
    }
917

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
918 919 920 921 922 923 924 925 926
    var problems = new Array();
    var dropped = new Array();
    for (var i = 0; i < shared_list.length; i++) {
      var shared = 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,
927
            start_pos: shared.start_position,
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
928 929 930 931 932 933 934 935 936 937 938 939 940 941
            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");
    }
942

943
    return dropped.length;
944
  }
945

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
946 947 948 949 950 951
  // 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,
952 953 954
      REPLACED_ON_ACTIVE_STACK: 5,
      BLOCKED_UNDER_GENERATOR: 6,
      BLOCKED_ACTIVE_GENERATOR: 7
955
  };
956

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
957
  FunctionPatchabilityStatus.SymbolName = function(code) {
958
    var enumeration = FunctionPatchabilityStatus;
959
    for (var name in enumeration) {
960
      if (enumeration[name] == code) {
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
961 962
        return name;
      }
963
    }
964
  };
965 966


peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
967 968 969 970
  // 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;
971
  }
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
972 973
  // Function (constructor) is public.
  this.Failure = Failure;
974

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
975 976
  Failure.prototype.toString = function() {
    return "LiveEdit Failure: " + this.message;
977
  };
978

979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003
  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;
  }

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
1004 1005 1006
  // A testing entry.
  function GetPcFromSourcePos(func, source_pos) {
    return %GetFunctionCodePositionFromSource(func, source_pos);
1007
  }
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
1008 1009
  // Function is public.
  this.GetPcFromSourcePos = GetPcFromSourcePos;
1010

1011
  // LiveEdit main entry point: changes a script text to a new string.
1012
  function SetScriptSource(script, new_source, preview_only, change_log) {
1013
    var old_source = script.source;
1014
    var diff = CompareStrings(old_source, new_source);
1015 1016
    return ApplyPatchMultiChunk(script, diff, new_source, preview_only,
        change_log);
1017
  }
1018 1019
  // Function is public.
  this.SetScriptSource = SetScriptSource;
1020

1021
  function CompareStrings(s1, s2) {
1022
    return %LiveEditCompareStrings(s1, s2);
1023
  }
1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035

  // 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;
1036

1037 1038 1039
    // Prepare new source string.
    var new_source = old_source.substring(0, change_pos) +
        new_str + old_source.substring(change_pos + change_len);
1040

1041 1042
    return ApplyPatchMultiChunk(script,
        [ change_pos, change_pos + change_len, change_pos + new_str.length],
1043 1044
        new_source, false, change_log);
  }
1045

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

1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068
    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,
1069
        new_children: new_child_infos
1070 1071 1072 1073 1074 1075 1076 1077 1078
      };
      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;
    }
1079

1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094
    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;
    }
1095

1096 1097 1098 1099 1100 1101
    function DescribePositions(node) {
      return {
        start_position: node.info.start_position,
        end_position: node.info.end_position
      };
    }
1102

1103
    return ProcessOldNode(old_code_tree);
1104 1105
  }

1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117
  // Restarts call frame and returns value similar to what LiveEdit returns.
  function RestartFrame(frame_mirror) {
    var result = frame_mirror.restart();
    if (IS_STRING(result)) {
      throw new Failure("Failed to restart frame: " + result);
    }
    var result = {};
    result[NEEDS_STEP_IN_PROPERTY_NAME] = true;
    return result;
  }
  // Function is public.
  this.RestartFrame = RestartFrame;
1118

1119 1120 1121
  // Functions are public for tests.
  this.TestApi = {
    PosTranslator: PosTranslator,
1122
    CompareStrings: CompareStrings,
1123
    ApplySingleChunkPatch: ApplySingleChunkPatch
1124 1125
  };
};