Fix Issue 1320: LiveEdit: text differencer fails with out of memory on large files

src/liveedit.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 41 matching lines @@
                          Handle<Object> value) {
   // Ignore return value from SetElement. It can only be a failure if there
   // are element setters causing exceptions and the debugger context has none
   // of these.
   Handle<Object> no_failure;
   no_failure = SetElement(object, index, value, kNonStrictMode);
   ASSERT(!no_failure.is_null());
   USE(no_failure);
 }
 
+// Creates string expression and throws it in V8 isolate.
+void ThrowStringException(const char* str, Isolate* isolate) {
+  Vector<const char> str_vector(str, strlen(str));
+  MaybeObject* maybe_exception =
+      isolate->heap()->AllocateStringFromAscii(str_vector);
+  Object* exception;
+  if (maybe_exception->ToObject(&exception)) {
+    isolate->Throw(exception, NULL);
+  }
+}
+
 // A simple implementation of dynamic programming algorithm. It solves
-// the problem of finding the difference of 2 arrays. It uses a table of results
-// of subproblems. Each cell contains a number together with 2-bit flag
+// the problem of finding the difference of 2 arrays. It uses a table of
+// results of subproblems. Each cell contains a number together with 2-bit flag
 // that helps building the chunk list.
 class Differencer {
  public:
-  explicit Differencer(Comparator::Input* input)
-      : input_(input), len1_(input->getLength1()), len2_(input->getLength2()) {
-    buffer_ = NewArray<int>(len1_ * len2_);
+  explicit Differencer(Comparator::Input* input, Isolate* isolate,
+                       bool* has_exception)
+      : input_(input), buffer_(NULL), len1_(input->getLength1()),
+        len2_(input->getLength2()) {
+    // Put multiply result into a bigger integer.
+    int64_t multiply =
+        static_cast<int64_t>(len1_) * static_cast<int64_t>(len2_);
+
+    // Maximum table size is max_int. Within this limit it's easy to check
+    // for multiply overflow. Should we support bigger numbers?
+    if (multiply > kMaxInt) {
+      ThrowStringException("Too many lines: differencer table size is too big",
+          isolate);
+      *has_exception = true;
+      return;
+    }
+    multiply *= sizeof(int);  // NOLINT
+    size_t size = multiply;
+    if (size != multiply) {
+      // Shouldn't be reachable.
+      ThrowStringException(
+          "Too many lines: "
+          "differencer table buffer size doesn't fit into size_t", isolate);
+      *has_exception = true;
+      return;
+    }
+    void* p = malloc(size);
+    if (p == NULL) {
+      ThrowStringException(
+          "Too many lines: not enough memory for differencer table buffer",
+          isolate);
+      *has_exception = true;
+      return;
+    }
+    buffer_ = reinterpret_cast<int*>(p);
   }
+
   ~Differencer() {
-    DeleteArray(buffer_);
+    if (buffer_ != NULL) {
+      free(buffer_);
+    }
   }
 
   void Initialize() {
     int array_size = len1_ * len2_;
     for (int i = 0; i < array_size; i++) {
       buffer_[i] = kEmptyCellValue;
     }
   }
 
   // Makes sure that result for the full problem is calculated and stored
@@ skipping 168 matching lines @@
       if (has_open_chunk_) {
         chunk_writer_->AddChunk(pos1_begin_, pos2_begin_,
                                 pos1_ - pos1_begin_, pos2_ - pos2_begin_);
         has_open_chunk_ = false;
       }
     }
   };
 };
 
 
-void Comparator::CalculateDifference(Comparator::Input* input,
-                                     Comparator::Output* result_writer) {
-  Differencer differencer(input);
+MUST_USE_RESULT MaybeObject/*<void>*/* Comparator::CalculateDifference(
+    Comparator::Input* input, Comparator::Output* result_writer,
+    Isolate* isolate) {
+  bool has_exception = false;
+  Differencer differencer(input, isolate, &has_exception);
+  if (has_exception) {
+    return Failure::Exception();
+  }
   differencer.Initialize();
   differencer.FillTable();
   differencer.SaveResult(result_writer);
+  return Smi::FromInt(0);  // Unused value.
 }
 
 
 static bool CompareSubstrings(Handle<String> s1, int pos1,
                               Handle<String> s2, int pos2, int len) {
   for (int i = 0; i < len; i++) {
     if (s1->Get(i + pos1) != s2->Get(i + pos2)) {
       return false;
     }
   }
@@ skipping 157 matching lines @@
   LineEndsWrapper line_ends2_;
 };
 
 
 // Stores compare result in JSArray. For each chunk tries to conduct
 // a fine-grained nested diff token-wise.
 class TokenizingLineArrayCompareOutput : public Comparator::Output {
  public:
   TokenizingLineArrayCompareOutput(LineEndsWrapper line_ends1,
                                    LineEndsWrapper line_ends2,
-                                   Handle<String> s1, Handle<String> s2)
-      : line_ends1_(line_ends1), line_ends2_(line_ends2), s1_(s1), s2_(s2) {
+                                   Handle<String> s1, Handle<String> s2,
+                                   Isolate* isolate)
+      : line_ends1_(line_ends1), line_ends2_(line_ends2), s1_(s1), s2_(s2),
+        isolate_(isolate) {
   }
 
   void AddChunk(int line_pos1, int line_pos2, int line_len1, int line_len2) {
     int char_pos1 = line_ends1_.GetLineStart(line_pos1);
     int char_pos2 = line_ends2_.GetLineStart(line_pos2);
     int char_len1 = line_ends1_.GetLineStart(line_pos1 + line_len1) - char_pos1;
     int char_len2 = line_ends2_.GetLineStart(line_pos2 + line_len2) - char_pos2;
 
     if (char_len1 < CHUNK_LEN_LIMIT && char_len2 < CHUNK_LEN_LIMIT) {
       // Chunk is small enough to conduct a nested token-level diff.
       HandleScope subTaskScope;
 
       TokensCompareInput tokens_input(s1_, char_pos1, char_len1,
                                       s2_, char_pos2, char_len2);
       TokensCompareOutput tokens_output(&array_writer_, char_pos1,
                                           char_pos2);
 
-      Comparator::CalculateDifference(&tokens_input, &tokens_output);
+      MaybeObject* res = Comparator::CalculateDifference(&tokens_input,

[Søren Thygesen Gjesse, 2011/05/31 08:03:09]

All arguments on same line or each argument on separate lines.

+          &tokens_output, isolate_);
+      if (res->IsFailure()) {
+        // We asked for a small amount of memory, this should not happen.
+        UNREACHABLE();
+      }
     } else {
       array_writer_.WriteChunk(char_pos1, char_pos2, char_len1, char_len2);
     }
   }
 
   Handle<JSArray> GetResult() {
     return array_writer_.GetResult();
   }
 
  private:
   static const int CHUNK_LEN_LIMIT = 800;
 
   CompareOutputArrayWriter array_writer_;
   LineEndsWrapper line_ends1_;
   LineEndsWrapper line_ends2_;
   Handle<String> s1_;
   Handle<String> s2_;
+  Isolate* isolate_;
 };
 
 
-Handle<JSArray> LiveEdit::CompareStrings(Handle<String> s1,
-                                         Handle<String> s2) {
+MUST_USE_RESULT MaybeObject/*<JSArray>*/* LiveEdit::CompareStrings(
+    Handle<String> s1, Handle<String> s2) {
+
+  Isolate* isolate = Isolate::Current();
   s1 = FlattenGetString(s1);
   s2 = FlattenGetString(s2);
 
   LineEndsWrapper line_ends1(s1);
   LineEndsWrapper line_ends2(s2);
 
   LineArrayCompareInput input(s1, s2, line_ends1, line_ends2);
-  TokenizingLineArrayCompareOutput output(line_ends1, line_ends2, s1, s2);
+  TokenizingLineArrayCompareOutput output(line_ends1, line_ends2, s1, s2,

[Søren Thygesen Gjesse, 2011/05/31 08:03:09]

All arguments on same line or each argument on separate lines.

+      isolate);
 
-  Comparator::CalculateDifference(&input, &output);
+  MaybeObject* result = Comparator::CalculateDifference(&input, &output,

[Søren Thygesen Gjesse, 2011/05/31 08:03:09]

All arguments on same line or each argument on separate lines.

+      isolate);
+  if (result->IsFailure()) {
+    return result;
+  }
 
-  return output.GetResult();
+  return *output.GetResult();
 }
 
 
 static void CompileScriptForTracker(Isolate* isolate, Handle<Script> script) {
   // TODO(635): support extensions.
   PostponeInterruptsScope postpone(isolate);
 
   // Build AST.
   CompilationInfo info(script);
   info.MarkAsGlobal();
@@ skipping 1173 matching lines @@
 
 bool LiveEditFunctionTracker::IsActive(Isolate* isolate) {
   return false;
 }
 
 #endif  // ENABLE_DEBUGGER_SUPPORT
 
 
 
 } }  // namespace v8::internal