1// Copyright 2007-2008 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#ifdef ENABLE_DEBUGGER_SUPPORT
29
30#include <stdlib.h>
31
32#include "v8.h"
33
34#include "liveedit.h"
35#include "cctest.h"
36
37
38using namespace v8::internal;
39
40// Anonymous namespace.
41namespace {
42
43class StringCompareInput : public Comparator::Input {
44 public:
45  StringCompareInput(const char* s1, const char* s2) : s1_(s1), s2_(s2) {
46  }
47  int GetLength1() {
48    return StrLength(s1_);
49  }
50  int GetLength2() {
51    return StrLength(s2_);
52  }
53  bool Equals(int index1, int index2) {
54    return s1_[index1] == s2_[index2];
55  }
56
57 private:
58  const char* s1_;
59  const char* s2_;
60};
61
62
63class DiffChunkStruct : public ZoneObject {
64 public:
65  DiffChunkStruct(int pos1_param, int pos2_param,
66                  int len1_param, int len2_param)
67      : pos1(pos1_param), pos2(pos2_param),
68        len1(len1_param), len2(len2_param), next(NULL) {}
69  int pos1;
70  int pos2;
71  int len1;
72  int len2;
73  DiffChunkStruct* next;
74};
75
76
77class ListDiffOutputWriter : public Comparator::Output {
78 public:
79  explicit ListDiffOutputWriter(DiffChunkStruct** next_chunk_pointer,
80                                Zone* zone)
81      : next_chunk_pointer_(next_chunk_pointer), zone_(zone) {
82    (*next_chunk_pointer_) = NULL;
83  }
84  void AddChunk(int pos1, int pos2, int len1, int len2) {
85    current_chunk_ = new(zone_) DiffChunkStruct(pos1, pos2, len1, len2);
86    (*next_chunk_pointer_) = current_chunk_;
87    next_chunk_pointer_ = &current_chunk_->next;
88  }
89 private:
90  DiffChunkStruct** next_chunk_pointer_;
91  DiffChunkStruct* current_chunk_;
92  Zone* zone_;
93};
94
95
96void CompareStringsOneWay(const char* s1, const char* s2,
97                          int expected_diff_parameter = -1) {
98  StringCompareInput input(s1, s2);
99
100  Zone zone(Isolate::Current());
101
102  DiffChunkStruct* first_chunk;
103  ListDiffOutputWriter writer(&first_chunk, &zone);
104
105  Comparator::CalculateDifference(&input, &writer);
106
107  int len1 = StrLength(s1);
108  int len2 = StrLength(s2);
109
110  int pos1 = 0;
111  int pos2 = 0;
112
113  int diff_parameter = 0;
114
115  for (DiffChunkStruct* chunk = first_chunk;
116      chunk != NULL;
117      chunk = chunk->next) {
118    int diff_pos1 = chunk->pos1;
119    int similar_part_length = diff_pos1 - pos1;
120    int diff_pos2 = pos2 + similar_part_length;
121
122    ASSERT_EQ(diff_pos2, chunk->pos2);
123
124    for (int j = 0; j < similar_part_length; j++) {
125      ASSERT(pos1 + j < len1);
126      ASSERT(pos2 + j < len2);
127      ASSERT_EQ(s1[pos1 + j], s2[pos2 + j]);
128    }
129    diff_parameter += chunk->len1 + chunk->len2;
130    pos1 = diff_pos1 + chunk->len1;
131    pos2 = diff_pos2 + chunk->len2;
132  }
133  {
134    // After last chunk.
135    int similar_part_length = len1 - pos1;
136    ASSERT_EQ(similar_part_length, len2 - pos2);
137    USE(len2);
138    for (int j = 0; j < similar_part_length; j++) {
139      ASSERT(pos1 + j < len1);
140      ASSERT(pos2 + j < len2);
141      ASSERT_EQ(s1[pos1 + j], s2[pos2 + j]);
142    }
143  }
144
145  if (expected_diff_parameter != -1) {
146    ASSERT_EQ(expected_diff_parameter, diff_parameter);
147  }
148}
149
150
151void CompareStrings(const char* s1, const char* s2,
152                    int expected_diff_parameter = -1) {
153  CompareStringsOneWay(s1, s2, expected_diff_parameter);
154  CompareStringsOneWay(s2, s1, expected_diff_parameter);
155}
156
157}  // Anonymous namespace.
158
159
160// --- T h e   A c t u a l   T e s t s
161
162TEST(LiveEditDiffer) {
163  v8::internal::V8::Initialize(NULL);
164  CompareStrings("zz1zzz12zz123zzz", "zzzzzzzzzz", 6);
165  CompareStrings("zz1zzz12zz123zzz", "zz0zzz0zz0zzz", 9);
166  CompareStrings("123456789", "987654321", 16);
167  CompareStrings("zzz", "yyy", 6);
168  CompareStrings("zzz", "zzz12", 2);
169  CompareStrings("zzz", "21zzz", 2);
170  CompareStrings("cat", "cut", 2);
171  CompareStrings("ct", "cut", 1);
172  CompareStrings("cat", "ct", 1);
173  CompareStrings("cat", "cat", 0);
174  CompareStrings("", "", 0);
175  CompareStrings("cat", "", 3);
176  CompareStrings("a cat", "a capybara", 7);
177  CompareStrings("abbabababababaaabbabababababbabbbbbbbababa",
178                 "bbbbabababbbabababbbabababababbabbababa");
179}
180
181#endif  // ENABLE_DEBUGGER_SUPPORT
182