Line data Source code
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 : #include <stdlib.h>
29 :
30 : #include "src/v8.h"
31 :
32 : #include "src/debug/liveedit.h"
33 : #include "src/objects-inl.h"
34 : #include "test/cctest/cctest.h"
35 :
36 : namespace v8 {
37 : namespace internal {
38 :
39 : // Anonymous namespace.
40 : namespace {
41 :
42 0 : class StringCompareInput : public Comparator::Input {
43 : public:
44 168 : StringCompareInput(const char* s1, const char* s2) : s1_(s1), s2_(s2) {
45 : }
46 168 : int GetLength1() {
47 336 : return StrLength(s1_);
48 : }
49 168 : int GetLength2() {
50 336 : return StrLength(s2_);
51 : }
52 9720 : bool Equals(int index1, int index2) {
53 9720 : return s1_[index1] == s2_[index2];
54 : }
55 :
56 : private:
57 : const char* s1_;
58 : const char* s2_;
59 : };
60 :
61 :
62 : class DiffChunkStruct : public ZoneObject {
63 : public:
64 : DiffChunkStruct(int pos1_param, int pos2_param, int len1_param,
65 : int len2_param)
66 : : pos1(pos1_param),
67 : pos2(pos2_param),
68 : len1(len1_param),
69 : len2(len2_param),
70 282 : next(nullptr) {}
71 : int pos1;
72 : int pos2;
73 : int len1;
74 : int len2;
75 : DiffChunkStruct* next;
76 : };
77 :
78 :
79 168 : class ListDiffOutputWriter : public Comparator::Output {
80 : public:
81 : explicit ListDiffOutputWriter(DiffChunkStruct** next_chunk_pointer,
82 : Zone* zone)
83 168 : : next_chunk_pointer_(next_chunk_pointer), zone_(zone) {
84 168 : (*next_chunk_pointer_) = nullptr;
85 : }
86 282 : void AddChunk(int pos1, int pos2, int len1, int len2) {
87 564 : current_chunk_ = new(zone_) DiffChunkStruct(pos1, pos2, len1, len2);
88 282 : (*next_chunk_pointer_) = current_chunk_;
89 282 : next_chunk_pointer_ = ¤t_chunk_->next;
90 282 : }
91 : private:
92 : DiffChunkStruct** next_chunk_pointer_;
93 : DiffChunkStruct* current_chunk_;
94 : Zone* zone_;
95 : };
96 :
97 :
98 168 : void CompareStringsOneWay(const char* s1, const char* s2,
99 : int expected_diff_parameter = -1) {
100 : StringCompareInput input(s1, s2);
101 :
102 336 : v8::internal::AccountingAllocator allocator;
103 336 : Zone zone(&allocator, ZONE_NAME);
104 :
105 : DiffChunkStruct* first_chunk;
106 : ListDiffOutputWriter writer(&first_chunk, &zone);
107 :
108 168 : Comparator::CalculateDifference(&input, &writer);
109 :
110 : int len1 = StrLength(s1);
111 : int len2 = StrLength(s2);
112 :
113 : int pos1 = 0;
114 : int pos2 = 0;
115 :
116 : int diff_parameter = 0;
117 :
118 450 : for (DiffChunkStruct* chunk = first_chunk; chunk != nullptr;
119 : chunk = chunk->next) {
120 282 : int diff_pos1 = chunk->pos1;
121 282 : int similar_part_length = diff_pos1 - pos1;
122 282 : int diff_pos2 = pos2 + similar_part_length;
123 :
124 282 : CHECK_EQ(diff_pos2, chunk->pos2);
125 :
126 636 : for (int j = 0; j < similar_part_length; j++) {
127 636 : CHECK(pos1 + j < len1);
128 636 : CHECK(pos2 + j < len2);
129 636 : CHECK_EQ(s1[pos1 + j], s2[pos2 + j]);
130 : }
131 282 : diff_parameter += chunk->len1 + chunk->len2;
132 282 : pos1 = diff_pos1 + chunk->len1;
133 282 : pos2 = diff_pos2 + chunk->len2;
134 : }
135 : {
136 : // After last chunk.
137 168 : int similar_part_length = len1 - pos1;
138 168 : CHECK_EQ(similar_part_length, len2 - pos2);
139 : USE(len2);
140 252 : for (int j = 0; j < similar_part_length; j++) {
141 252 : CHECK(pos1 + j < len1);
142 252 : CHECK(pos2 + j < len2);
143 252 : CHECK_EQ(s1[pos1 + j], s2[pos2 + j]);
144 : }
145 : }
146 :
147 168 : if (expected_diff_parameter != -1) {
148 156 : CHECK_EQ(expected_diff_parameter, diff_parameter);
149 : }
150 168 : }
151 :
152 :
153 84 : void CompareStrings(const char* s1, const char* s2,
154 : int expected_diff_parameter = -1) {
155 84 : CompareStringsOneWay(s1, s2, expected_diff_parameter);
156 84 : CompareStringsOneWay(s2, s1, expected_diff_parameter);
157 84 : }
158 :
159 : } // Anonymous namespace.
160 :
161 :
162 : // --- T h e A c t u a l T e s t s
163 :
164 23724 : TEST(LiveEditDiffer) {
165 6 : CompareStrings("zz1zzz12zz123zzz", "zzzzzzzzzz", 6);
166 6 : CompareStrings("zz1zzz12zz123zzz", "zz0zzz0zz0zzz", 9);
167 6 : CompareStrings("123456789", "987654321", 16);
168 6 : CompareStrings("zzz", "yyy", 6);
169 6 : CompareStrings("zzz", "zzz12", 2);
170 6 : CompareStrings("zzz", "21zzz", 2);
171 6 : CompareStrings("cat", "cut", 2);
172 6 : CompareStrings("ct", "cut", 1);
173 6 : CompareStrings("cat", "ct", 1);
174 6 : CompareStrings("cat", "cat", 0);
175 6 : CompareStrings("", "", 0);
176 6 : CompareStrings("cat", "", 3);
177 6 : CompareStrings("a cat", "a capybara", 7);
178 : CompareStrings("abbabababababaaabbabababababbabbbbbbbababa",
179 6 : "bbbbabababbbabababbbabababababbabbababa");
180 6 : }
181 :
182 : } // namespace internal
183 71154 : } // namespace v8
|
