liveedit.js 37.6 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

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

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
(function(global, utils) {
  "use strict";
25

26 27 28 29 30 31
  // -------------------------------------------------------------------
  // Imports

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

  // -------------------------------------------------------------------
36

37 38
  // Forward declaration for minifier.
  var FunctionStatus;
39

40 41 42
  // 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)
43 44
  function ApplyPatchMultiChunk(script, diff_array, new_source, preview_only,
      change_log) {
45

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

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

51 52 53 54 55 56 57 58 59 60
    // 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);
61

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
62 63 64
    // Gather compile information about new version of script.
    var new_compile_info;
    try {
65
      new_compile_info = GatherCompileInfo(new_source, script);
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
66
    } catch (e) {
67 68 69 70 71 72 73 74 75 76 77
      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
78
    }
79 80 81 82

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

83 84
    var root_new_node = BuildCodeInfoTree(new_compile_info);

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

88
    // Prepare to-do lists.
89 90 91 92
    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();
93 94 95 96 97 98 99 100

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

      // Recursively collects all newly compiled functions that are going into
103
      // business and should have link to the actual script updated.
104 105 106 107 108 109
      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);
        }
      }
110

111 112 113 114 115 116 117 118 119 120
      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);
121
        CollectNew(old_node.unmatched_new_nodes);
122 123 124 125
      }
      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
126
    }
127

128 129 130 131 132 133 134 135 136
    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
    };
137

138 139 140
    if (preview_only) {
      return preview_description;
    }
141

142
    HarvestTodo(root_old_node);
143

144
    // Collect shared infos for functions whose code need to be patched.
145 146
    var replaced_function_old_infos = new GlobalArray();
    var replaced_function_new_infos = new GlobalArray();
147
    for (var i = 0; i < replace_code_list.length; i++) {
148 149 150 151 152 153 154 155
      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);
156
        }
157 158 159 160
      }
    }

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

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

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

173 174 175 176 177 178
    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);
179
      old_script = UNDEFINED;
180
    } else {
181
      var old_script_name = CreateNameForOldScript(script);
182

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

187
      var link_to_old_script_report = new GlobalArray();
188
      change_log.push( { linked_to_old_script: link_to_old_script_report } );
189

190 191
      // We need to link to old script all former nested functions.
      for (var i = 0; i < link_to_old_script_list.length; i++) {
192 193
        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
194
      }
195

196
      preview_description.created_script_name = old_script_name;
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
197
    }
198

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

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

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

      if (update_positions_list[i].live_shared_function_infos) {
213 214 215 216 217 218 219 220
        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);
        });
221
      }
222
    }
223

224 225 226 227 228 229 230 231
    %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);
    }

232 233
    preview_description.updated = true;
    return preview_description;
234
  }
235

236 237 238 239 240 241 242 243
  // 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
244
  // we have to manually erase all links right after compile.
245 246 247 248 249 250
  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.
251 252
    var compile_info = new GlobalArray();
    var old_index_map = new GlobalArray();
253 254 255 256 257 258
    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.
259
      %LiveEditFunctionSetScript(info.shared_function_info, UNDEFINED);
260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280
      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;
      }
    }

281
    // After sorting update outer_index field using old_index_map. Also
282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310
    // 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;
  }

311

312 313 314
  // Replaces function's Code.
  function PatchFunctionCode(old_node, change_log) {
    var new_info = old_node.corresponding_node.info;
315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334
    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) {
335 336 337 338
                    %LiveEditReplaceRefToNestedFunction(
                        old_info.info,
                        corresponding_child_info,
                        old_child_info.info);
339 340
                  });
            }
341 342
          }
        }
343
      });
344

345 346 347 348 349 350 351
      change_log.push( {function_patched: new_info.function_name} );
    } else {
      change_log.push( {function_patched: new_info.function_name,
          function_info_not_found: true} );
    }
  }

352

353 354 355 356
  // 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) {
357 358 359 360 361 362 363
    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 } );
364 365 366 367 368
    } else {
      report_array.push(
          { name: old_info_node.info.function_name, not_found: true } );
    }
  }
369

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
370 371 372 373 374 375 376 377
  function Assert(condition, message) {
    if (!condition) {
      if (message) {
        throw "Assert " + message;
      } else {
        throw "Assert";
      }
    }
378
  }
379 380 381 382 383 384 385

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

387
  function PosTranslator(diff_array) {
388
    var chunks = new GlobalArray();
389
    var current_diff = 0;
390
    for (var i = 0; i < diff_array.length; i += 3) {
391 392 393 394 395 396
      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));
397
      current_diff = pos2_end - pos1_end;
398 399 400 401 402
    }
    this.chunks = chunks;
  }
  PosTranslator.prototype.GetChunks = function() {
    return this.chunks;
403
  };
404

405
  PosTranslator.prototype.Translate = function(pos, inside_chunk_handler) {
406
    var array = this.chunks;
407
    if (array.length == 0 || pos < array[0].pos1) {
408 409 410 411 412 413
      return pos;
    }
    var chunk_index1 = 0;
    var chunk_index2 = array.length - 1;

    while (chunk_index1 < chunk_index2) {
414
      var middle_index = MathFloor((chunk_index1 + chunk_index2) / 2);
415 416 417 418 419 420 421 422
      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) {
423
      return pos + chunk.pos2 + chunk.len2 - chunk.pos1 - chunk.len1;
424
    }
425

426
    if (!inside_chunk_handler) {
427
      inside_chunk_handler = PosTranslator.DefaultInsideChunkHandler;
428
    }
429
    return inside_chunk_handler(pos, chunk);
430
  };
431

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

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

443 444
  var FunctionStatus = {
      // No change to function or its inner functions; however its positions
445
      // in script may have been shifted.
446 447 448 449 450 451 452 453 454
      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"
455
  };
456

457 458 459 460
  function CodeInfoTreeNode(code_info, children, array_index) {
    this.info = code_info;
    this.children = children;
    // an index in array of compile_info
461
    this.array_index = array_index;
462
    this.parent = UNDEFINED;
463

464 465 466
    this.status = FunctionStatus.UNCHANGED;
    // Status explanation is used for debugging purposes and will be shown
    // in user UI if some explanations are needed.
467 468 469 470 471
    this.status_explanation = UNDEFINED;
    this.new_start_pos = UNDEFINED;
    this.new_end_pos = UNDEFINED;
    this.corresponding_node = UNDEFINED;
    this.unmatched_new_nodes = UNDEFINED;
472

473 474 475 476 477
    // '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
478
    // as an old function deleted and new function created.
479 480
    this.textual_corresponding_node = UNDEFINED;
    this.textually_unmatched_new_nodes = UNDEFINED;
481

482
    this.live_shared_function_infos = UNDEFINED;
483
  }
484

485 486 487 488 489 490
  // 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;

491
    // Recursive function that builds a branch of tree.
492 493 494
    function BuildNode() {
      var my_index = index;
      index++;
495
      var child_array = new GlobalArray();
496 497 498 499 500 501 502 503 504 505 506
      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;
    }
507

508 509 510 511 512 513 514 515 516 517
    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) {

518
    // A convenient iterator over diff chunks that also translates
519 520 521 522
    // 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;
523
      this.current = function() { return chunks[chunk_index]; };
524 525
      this.next = function() {
        var chunk = chunks[chunk_index];
526
        pos_diff = chunk.pos2 + chunk.len2 - (chunk.pos1 + chunk.len1);
527
        chunk_index++;
528 529 530
      };
      this.done = function() { return chunk_index >= chunks.length; };
      this.TranslatePos = function(pos) { return pos + pos_diff; };
531 532 533 534 535 536 537
    };

    // 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(
538
          info_node.info.start_position);
539 540 541 542 543 544 545 546
      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];
547

548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575
          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 {
576
          if (chunk_it.current().pos1 + chunk_it.current().len1 <=
577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600
              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 =
601
          chunk_it.TranslatePos(info_node.info.end_position);
602
    }
603

604 605 606 607
    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);
    }
608

609 610 611
    ProcessInternals(code_info_tree);
  }

612
  // For each old function (if it is not damaged) tries to find a corresponding
613 614
  // function in new script. Typically it should succeed (non-damaged functions
  // by definition may only have changes inside their bodies). However there are
615
  // reasons for correspondence not to be found; function with unmodified text
616 617 618 619 620 621 622
  // 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.
623 624 625 626
    function ProcessNode(old_node, new_node) {
      var scope_change_description =
          IsFunctionContextLocalsChanged(old_node.info, new_node.info);
      if (scope_change_description) {
627
        old_node.status = FunctionStatus.CHANGED;
628 629
      }

630 631
      var old_children = old_node.children;
      var new_children = new_node.children;
632

633
      var unmatched_new_nodes_list = [];
634
      var textually_unmatched_new_nodes_list = [];
635 636 637 638 639 640 641 642 643

      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) {
644
            unmatched_new_nodes_list.push(new_children[new_index]);
645
            textually_unmatched_new_nodes_list.push(new_children[new_index]);
646 647 648 649 650 651 652
            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];
653 654
              old_children[old_index].textual_corresponding_node =
                  new_children[new_index];
655 656 657 658 659
              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;
660
                old_children[old_index].corresponding_node = UNDEFINED;
661 662 663
              } else if (old_children[old_index].status !=
                  FunctionStatus.UNCHANGED) {
                ProcessNode(old_children[old_index],
664 665
                    new_children[new_index]);
                if (old_children[old_index].status == FunctionStatus.DAMAGED) {
666 667
                  unmatched_new_nodes_list.push(
                      old_children[old_index].corresponding_node);
668
                  old_children[old_index].corresponding_node = UNDEFINED;
669 670
                  old_node.status = FunctionStatus.CHANGED;
                }
671 672
              } else {
                ProcessNode(old_children[old_index], new_children[new_index]);
673 674 675 676 677 678
              }
            } 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;
679
              unmatched_new_nodes_list.push(new_children[new_index]);
680
              textually_unmatched_new_nodes_list.push(new_children[new_index]);
681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698
            }
            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++;
        }
      }
699

700 701
      while (new_index < new_children.length) {
        unmatched_new_nodes_list.push(new_children[new_index]);
702
        textually_unmatched_new_nodes_list.push(new_children[new_index]);
703 704
        new_index++;
      }
705

706
      if (old_node.status == FunctionStatus.CHANGED) {
707
        if (old_node.info.param_num != new_node.info.param_num) {
708
          old_node.status = FunctionStatus.DAMAGED;
709 710
          old_node.status_explanation = "Changed parameter number: " +
              old_node.info.param_num + " and " + new_node.info.param_num;
711 712
        }
      }
713
      old_node.unmatched_new_nodes = unmatched_new_nodes_list;
714 715
      old_node.textually_unmatched_new_nodes =
          textually_unmatched_new_nodes_list;
716 717
    }

718
    ProcessNode(old_code_tree, new_code_tree);
719

720
    old_code_tree.corresponding_node = new_code_tree;
721 722
    old_code_tree.textual_corresponding_node = new_code_tree;

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

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

730
    var shared_infos = new GlobalArray();
731

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

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

741 742 743 744
      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) {
745
          wrappers.push(wrapper);
746 747
        }
      }
748 749 750 751

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

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

757 758 759 760 761 762 763
      for (var i = 0; i < node.children.length; i++) {
        TraverseTree(node.children[i]);
      }
    }

    TraverseTree(old_code_tree);
  }
764

765

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
766 767 768 769 770 771 772
  // 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];
773 774 775
    this.scope_info = raw_array[4];
    this.outer_index = raw_array[5];
    this.shared_function_info = raw_array[6];
776
    this.function_literal_id = raw_array[7];
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
777 778
    this.next_sibling_index = null;
    this.raw_array = raw_array;
779
  }
780

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
781 782 783 784 785 786
  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;
787
  }
788

789
  // Changes positions (including all statements) in function.
790
  function PatchPositions(old_info_node, diff_array, report_array) {
791 792 793 794 795 796 797 798
    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 {
799
      // TODO(LiveEdit): function is not compiled yet or is already collected.
800
      report_array.push(
801 802 803 804
          { name: old_info_node.info.function_name, info_not_found: true } );
    }
  }

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
805 806 807 808
  // 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)";
809
  }
810

811
  // Compares a function scope heap structure, old and new version, whether it
812
  // changed or not. Returns explanation if they differ.
813
  function IsFunctionContextLocalsChanged(function_info1, function_info2) {
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
814 815
    var scope_info1 = function_info1.scope_info;
    var scope_info2 = function_info2.scope_info;
816

817 818 819
    var scope_info1_text;
    var scope_info2_text;

820
    if (scope_info1) {
821
      scope_info1_text = scope_info1.toString();
822 823
    } else {
      scope_info1_text = "";
824
    }
825
    if (scope_info2) {
826
      scope_info2_text = scope_info2.toString();
827 828
    } else {
      scope_info2_text = "";
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
829
    }
830

831
    if (scope_info1_text != scope_info2_text) {
832 833
      return "Variable map changed: [" + scope_info1_text +
          "] => [" + scope_info2_text + "]";
834 835 836
    }
    // No differences. Return undefined.
    return;
837
  }
838

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
839 840
  // Minifier forward declaration.
  var FunctionPatchabilityStatus;
841

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
842 843 844
  // 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.
845 846 847 848 849 850 851 852 853 854
  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]) {
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
855
      // Extra array element may contain error message.
856
      throw new Failure(result[old_shared_wrapper_list.length]);
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
857
    }
858

859 860
    var problems = new GlobalArray();
    var dropped = new GlobalArray();
861 862
    for (var i = 0; i < old_shared_list.length; i++) {
      var shared = old_shared_wrapper_list[i];
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
863 864 865 866 867
      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,
868
            start_pos: shared.start_position,
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
869 870 871 872 873 874 875 876 877 878 879 880 881 882
            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");
    }
883

884
    return dropped.length;
885
  }
886

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
887 888 889 890 891 892
  // 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,
893 894
      REPLACED_ON_ACTIVE_STACK: 5,
      BLOCKED_UNDER_GENERATOR: 6,
895 896
      BLOCKED_ACTIVE_GENERATOR: 7,
      BLOCKED_NO_NEW_TARGET_ON_RESTART: 8
897
  };
898

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
899
  FunctionPatchabilityStatus.SymbolName = function(code) {
900
    var enumeration = FunctionPatchabilityStatus;
901
    for (var name in enumeration) {
902
      if (enumeration[name] == code) {
peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
903 904
        return name;
      }
905
    }
906
  };
907 908


peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
909 910 911 912
  // 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;
913
  }
914

peter.rybin@gmail.com's avatar
peter.rybin@gmail.com committed
915 916
  Failure.prototype.toString = function() {
    return "LiveEdit Failure: " + this.message;
917
  };
918

919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943
  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;
  }

944
  // LiveEdit main entry point: changes a script text to a new string.
945
  function SetScriptSource(script, new_source, preview_only, change_log) {
946
    var old_source = script.source;
947
    var diff = CompareStrings(old_source, new_source);
948 949
    return ApplyPatchMultiChunk(script, diff, new_source, preview_only,
        change_log);
950
  }
951

952
  function CompareStrings(s1, s2) {
953
    return %LiveEditCompareStrings(s1, s2);
954
  }
955 956 957 958 959 960 961 962 963 964 965 966

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

968 969 970
    // Prepare new source string.
    var new_source = old_source.substring(0, change_pos) +
        new_str + old_source.substring(change_pos + change_len);
971

972 973
    return ApplyPatchMultiChunk(script,
        [ change_pos, change_pos + change_len, change_pos + new_str.length],
974 975
        new_source, false, change_log);
  }
976

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

980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999
    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,
1000
        new_children: new_child_infos
1001 1002 1003 1004 1005 1006 1007 1008 1009
      };
      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;
    }
1010

1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025
    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;
    }
1026

1027 1028 1029 1030 1031 1032
    function DescribePositions(node) {
      return {
        start_position: node.info.start_position,
        end_position: node.info.end_position
      };
    }
1033

1034
    return ProcessOldNode(old_code_tree);
1035 1036
  }

1037 1038 1039 1040 1041 1042 1043 1044 1045
  // -------------------------------------------------------------------
  // Exports

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

  LiveEdit.TestApi = {
1046
    PosTranslator: PosTranslator,
1047
    CompareStrings: CompareStrings,
1048
    ApplySingleChunkPatch: ApplySingleChunkPatch
1049
  };
1050

1051 1052 1053 1054 1055
  // Functions needed by the debugger runtime.
  utils.InstallConstants(utils, [
    "SetScriptSource", LiveEdit.SetScriptSource,
  ]);

1056 1057 1058
  global.Debug.LiveEdit = LiveEdit;

})