Fix temp path calculation
[idea/community.git] / platform / platform-impl / src / com / intellij / openapi / diff / impl / processing / ByWord.java
1 /*
2  * Copyright 2000-2009 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.intellij.openapi.diff.impl.processing;
17
18 import com.intellij.openapi.diagnostic.Logger;
19 import com.intellij.openapi.diff.ex.DiffFragment;
20 import com.intellij.openapi.diff.impl.ComparisonPolicy;
21 import com.intellij.openapi.diff.impl.DiffUtil;
22 import com.intellij.openapi.diff.impl.highlighting.FragmentSide;
23 import com.intellij.openapi.diff.impl.highlighting.Util;
24 import com.intellij.openapi.util.TextRange;
25 import com.intellij.util.diff.Diff;
26
27 import java.util.ArrayList;
28
29 class ByWord implements DiffPolicy{
30   private static final Logger LOG = Logger.getInstance("#com.intellij.openapi.diff.impl.processing.ByWord");
31   private final ComparisonPolicy myComparisonPolicy;
32
33   public ByWord(ComparisonPolicy comparisonPolicy) {
34     myComparisonPolicy = comparisonPolicy;
35   }
36
37   public DiffFragment[] buildFragments(String text1, String text2) {
38     Word[] words1 = buildWords(text1, myComparisonPolicy);
39     Word[] words2 = buildWords(text2, myComparisonPolicy);
40     Diff.Change change = Diff.buildChanges(words1, words2);
41     change = Util.concatEquals(change, words1, words2);
42     if (Math.max(countNotWhitespaces(words1), countNotWhitespaces(words2)) > 0 && countEqual(change, words1, words2) == 0)
43       return new DiffFragment[]{myComparisonPolicy.createFragment(text1, text2)};
44     FragmentBuilder result = new FragmentBuilder(words1, words2, myComparisonPolicy, text1, text2);
45     FragmentBuilder.Version version1 = result.getVersion1();
46     FragmentBuilder.Version version2 = result.getVersion2();
47     while (change != null) {
48       if (change.line0 > version1.getCurrentWordIndex()) {
49         processEquals(change.line0, change.line1, result);
50       }
51       if (change.inserted == 0) {
52         processOneside(version1, change.deleted);
53       } else if (change.deleted == 0) {
54         processOneside(version2, change.inserted);
55       } else {
56         String prefix1 = version1.getCurrentWordPrefix();
57         String prefix2 = version2.getCurrentWordPrefix();
58         if (prefix1.length() > 0 || prefix2.length() > 0)
59           result.add(myComparisonPolicy.createFragment(prefix1, prefix2));
60         result.addChangedWords(change.deleted, change.inserted);
61       }
62       change = change.link;
63     }
64     processEquals(words1.length, words2.length, result);
65     result.addTails();
66     DiffFragment[] fragments = result.getFragments();
67     DiffFragment firstFragment = fragments[0];
68     if (DiffUtil.isEmpty(firstFragment)) {
69       DiffFragment[] newFragments = new DiffFragment[fragments.length - 1];
70       System.arraycopy(fragments, 1, newFragments, 0, newFragments.length);
71       fragments = newFragments;
72     }
73     return fragments;
74   }
75
76   private int countNotWhitespaces(Word[] words) {
77     int counter = 0;
78     for (int i = 0; i < words.length; i++) {
79       Word word = words[i];
80       if (!word.isWhitespace()) counter++;
81     }
82     return counter;
83   }
84
85   private int countEqual(Diff.Change change, Word[] words1, Word[] words2) {
86     int counter = 0;
87     int position1 = 0;
88     int position2 = 0;
89     while (change != null) {
90       if (change.line0 > position1) {
91         int same = change.line0 - position1;
92         LOG.assertTrue(same == change.line1 - position2);
93         for (int i = 0; i < same; i++) {
94           if (!words1[position1 + i].isWhitespace() && !words2[position2 + i].isWhitespace()) counter++;
95         }
96         position1 += same;
97         position2 += same;
98       }
99       position1 += change.deleted;
100       position2 += change.inserted;
101       change = change.link;
102     }
103     int tailCount = words1.length - position1;
104     LOG.assertTrue(tailCount == words2.length - position2);
105     while (tailCount > 0) {
106       if (!words1[words1.length - tailCount].isWhitespace() &&
107           !words2[words2.length - tailCount].isWhitespace()) counter++;
108       tailCount--;
109     }
110     return counter;
111   }
112
113   private void processOneside(FragmentBuilder.Version version, int wordCount) {
114     String prefix = version.getCurrentWordPrefix();
115     version.addOneSide(prefix, wordCount);
116   }
117
118   private void processEquals(int changed1, int changed2, FragmentBuilder result) {
119     while (result.getVersion1().getCurrentWordIndex() < changed1) {
120       result.processEqual();
121     }
122     LOG.assertTrue(changed2 == result.getVersion2().getCurrentWordIndex());
123   }
124
125   static Word[] buildWords(String text, ComparisonPolicy policy) {
126     ArrayList<Word> words = new ArrayList<Word>();
127     if (text.length() == 0 || !Character.isWhitespace(text.charAt(0)))
128       words.add(policy.createFormatting(text, new TextRange(0, 0)));
129     int start = 0;
130     boolean withinFormatting = true;
131     for (int i = 0; i < text.length(); i++) {
132       char nextChar = text.charAt(i);
133       boolean isWhitespace = Character.isWhitespace(nextChar);
134       if (withinFormatting) {
135         if (isWhitespace) continue;
136         if (start != -1 && start < i) words.add(policy.createFormatting(text, new TextRange(start, i)));
137         start = -1;
138         withinFormatting = false;
139       }
140       if (nextChar == '\n') {
141         if (start != -1) words.add(new Word(text, new TextRange(start, i)));
142         start = i;
143         withinFormatting = true;
144       } else if (Util.DELIMITERS_SET.contains(nextChar)) {
145         if (start != -1) {
146           words.add(new Word(text, new TextRange(start, i)));
147           start = -1;
148         }
149       } else {
150         if (start == -1) start = i;
151       }
152     }
153     if (start != -1) {
154       TextRange range = new TextRange(start, text.length());
155       Word lastWord = withinFormatting ? policy.createFormatting(text, range) : new Word(text, range);
156       words.add(lastWord);
157     }
158     return words.toArray(new Word[words.size()]);
159   }
160
161   private static class FragmentBuilder {
162     private final ArrayList<DiffFragment> myFragments = new ArrayList<DiffFragment>();
163     private final Version myVersion1;
164     private final Version myVersion2;
165     private final DiffPolicy.ByChar BY_CHAR;
166     private final DiffCorrection.ChangedSpace CORRECTION;
167     private final ComparisonPolicy myComparisonPolicy;
168
169     public FragmentBuilder(Word[] words1, Word[] words2, ComparisonPolicy comparisonPolicy, String text1, String text2) {
170       myVersion1 = new Version(words1, text1, this, true);
171       myVersion2 = new Version(words2, text2, this, false);
172       BY_CHAR = new ByChar(comparisonPolicy);
173       CORRECTION = new DiffCorrection.ChangedSpace(comparisonPolicy);
174       myComparisonPolicy = comparisonPolicy;
175     }
176
177     public DiffFragment[] getFragments() {
178       return myFragments.toArray(new DiffFragment[myFragments.size()]);
179     }
180
181     public Version getVersion1() { return myVersion1; }
182
183     public Version getVersion2() { return myVersion2; }
184
185     private void addAll(DiffFragment[] fragments) {
186       for (int i = 0; i < fragments.length; i++) {
187         DiffFragment fragment = fragments[i];
188         add(fragment);
189       }
190     }
191
192     private void add(DiffFragment fragment) {
193       String text1 = fragment.getText1();
194       String text2 = fragment.getText2();
195       if (text1 != null) myVersion1.addOffset(text1.length());
196       if (text2 != null) myVersion2.addOffset(text2.length());
197       if (fragment.isEqual() && myFragments.size() > 0) {
198         int lastIndex = myFragments.size() - 1;
199         DiffFragment prevFragment = myFragments.get(lastIndex);
200         if (prevFragment.isEqual()) {
201           myFragments.remove(lastIndex);
202           fragment = DiffFragment.unchanged(prevFragment.getText1() + fragment.getText1(),
203                                             prevFragment.getText2() + fragment.getText2());
204         }
205       }
206       myFragments.add(fragment);
207     }
208
209     private void addEqual(Word word1, Word word2) {
210       addAll(CORRECTION.correct(new DiffFragment[]{myComparisonPolicy.createFragment(word1, word2)}));
211     }
212
213     public void processEqual() {
214       Word word1 = myVersion1.getCurrentWord();
215       Word word2 = myVersion2.getCurrentWord();
216       addAll(fragmentsByChar(myVersion1.getCurrentWordPrefix(), myVersion2.getCurrentWordPrefix()));
217       addEqual(word1, word2);
218       addPostfixes();
219       myVersion1.incCurrentWord();
220       myVersion2.incCurrentWord();
221     }
222
223     private DiffFragment[] fragmentsByChar(String text1, String text2) {
224       DiffFragment[] fragments = BY_CHAR.buildFragments(myVersion1.getPrevChar() + text1,
225                                                         myVersion2.getPrevChar() + text2);
226       return Util.cutFirst(fragments);
227     }
228
229     private void addPostfixes() {
230       String postfix1 = myVersion1.getCurrentWordPostfixAndOneMore();
231       String postfix2 = myVersion2.getCurrentWordPostfixAndOneMore();
232       int length1 = postfix1.length();
233       int length2 = postfix2.length();
234       DiffFragment wholePostfix = myComparisonPolicy.createFragment(postfix1, postfix2);
235       if (wholePostfix.isEqual()) {
236         add(DiffFragment.unchanged(cutLast(postfix1, length1), cutLast(postfix2, length2)));
237         return;
238       }
239       if (length1 > 0 || length2 > 0) {
240         DiffFragment[] fragments = BY_CHAR.buildFragments(postfix1, postfix2);
241         DiffFragment firstFragment = fragments[0];
242         if (firstFragment.isEqual()) {
243           add(myComparisonPolicy.createFragment(cutLast(firstFragment.getText1(), length1),
244                                                 cutLast(firstFragment.getText2(), length2)));
245           //add(firstFragment);
246         }
247       }
248     }
249
250     private String cutLast(String text, int length) {
251       if (text.length() < length) return text;
252       else return text.substring(0, text.length() - 1);
253     }
254
255     private void addOneSide(String text, FragmentSide side) {
256       DiffFragment fragment = side.createFragment(text, null, false);
257       add(myComparisonPolicy.createFragment(fragment.getText1(), fragment.getText2()));
258     }
259
260     public void addChangedWords(int wordCount1, int wordCount2) {
261       add(new DiffFragment(myVersion1.getWordSequence(wordCount1), myVersion2.getWordSequence(wordCount2)));
262       myVersion1.incCurrentWord(wordCount1);
263       myVersion2.incCurrentWord(wordCount2);
264     }
265
266     public void addTails() {
267       String tail1 = myVersion1.getNotProcessedTail();
268       String tail2 = myVersion2.getNotProcessedTail();
269       if (tail1.length() == 0 && tail2.length() == 0) return;
270       DiffFragment[] fragments = fragmentsByChar(tail1, tail2);
271       if (myFragments.size() > 0) {
272         DiffFragment lastFragment = myFragments.get(myFragments.size() - 1);
273         if (lastFragment.isChange()) {
274           int oneSideCount = 0;
275           while (oneSideCount < fragments.length && fragments[oneSideCount].isOneSide()) oneSideCount++;
276           if (oneSideCount > 0) {
277             myFragments.remove(myFragments.size() - 1);
278             DiffFragment[] onesideFragments = new DiffFragment[oneSideCount];
279             DiffFragment[] otherFragments = new DiffFragment[fragments.length - oneSideCount];
280             System.arraycopy(fragments, 0, onesideFragments, 0, oneSideCount);
281             System.arraycopy(fragments, oneSideCount, otherFragments, 0, otherFragments.length);
282             DiffFragment startingOneSides = UniteSameType.uniteAll(onesideFragments);
283             if (startingOneSides.isOneSide()) {
284               myFragments.add(lastFragment);
285               add(startingOneSides);
286             } else {
287               lastFragment = Util.unite(lastFragment, startingOneSides);
288               myFragments.add(lastFragment);
289             }
290             fragments = otherFragments;
291           }
292         }
293       }
294       addAll(fragments);
295     }
296
297     public static class Version {
298       private final Word[] myWords;
299       private int myCurrentWord = 0;
300       private int myOffset = 0;
301       private final String myText;
302       private final FragmentBuilder myBuilder;
303       private final FragmentSide mySide;
304
305       public Version(Word[] words, String text, FragmentBuilder builder, boolean delete) {
306         myWords = words;
307         myText = text;
308         myBuilder = builder;
309         mySide = delete ? FragmentSide.SIDE1 : FragmentSide.SIDE2;
310       }
311
312       public int getProcessedOffset() {
313         return myOffset;
314       }
315
316       public int getCurrentWordIndex() {
317         return myCurrentWord;
318       }
319
320       public void addOffset(int offset) {
321         myOffset += offset;
322       }
323
324       public void incCurrentWord() {
325         incCurrentWord(1);
326       }
327
328       public String getWordSequence(int wordCount) {
329         int start = myWords[myCurrentWord].getStart();
330         int end = myWords[myCurrentWord+wordCount-1].getEnd();
331         return myText.substring(start, end);
332       }
333
334       public void incCurrentWord(int inserted) {
335         myCurrentWord += inserted;
336       }
337
338       public Word getCurrentWord() {
339         return myWords[myCurrentWord];
340       }
341
342       public String getCurrentWordPrefix() {
343         return getCurrentWord().getPrefix(getProcessedOffset());
344       }
345
346       public String getCurrentWordPostfixAndOneMore() {
347         int nextStart = myCurrentWord < myWords.length - 1 ? myWords[myCurrentWord + 1].getStart() : myText.length();
348         Word word = getCurrentWord();
349         String postfix = myText.substring(word.getEnd(), nextStart);
350         return postfix + (nextStart == myText.length() ? '\n' : myText.charAt(nextStart));
351       }
352
353       public String getNotProcessedTail() {
354         LOG.assertTrue(myCurrentWord == myWords.length);
355         return myText.substring(myOffset, myText.length());
356       }
357
358       public char getPrevChar() {
359         return myOffset == 0 ? '\n' : myText.charAt(myOffset - 1);
360       }
361
362       public void addOneSide(String prefix, int wordCount) {
363         if (prefix.length() > 0) myBuilder.addOneSide(prefix, mySide);
364         myBuilder.addOneSide(getWordSequence(wordCount), mySide);
365         incCurrentWord(wordCount);
366       }
367     }
368   }
369 }