#98 org.webcat.diff.Differ runs into infinite loop

open
5
2012-12-09
2012-11-05
Garmann
No

The Method org.webcat.diff.Differ.getDifferences hangs up when runing the following code:

String[] a= new String[] { "1","2","3","1","2","4","1" };
String[] b= new String[] { "0","2","3","0","2","4","0" };
Differ<String> differ= new Differ<String>(a, b);

Suggested fix in class Differ:

private List<T>[] halfMatchI(List<T> longtext, List<T> shorttext, int i)
{
// Start with a 1/4 length subList at position i as a seed.
List<T> seed = longtext.subList(i, i + longtext.size() / 4);
int j = -1;
List<T> best_common = new ArrayList<T>();
List<T> best_longtext_a = new ArrayList<T>();
List<T> best_longtext_b = new ArrayList<T>();
List<T> best_shorttext_a = new ArrayList<T>();
List<T> best_shorttext_b = new ArrayList<T>();
int oldj= j;
while ((j = listIndexOf(shorttext, seed, j + 1)) != -1)
{
if (oldj != -1) j+=oldj+1;
int prefixLength = findCommonPrefix(longtext.subList(i, longtext.size()),
shorttext.subList(j, shorttext.size()));
int suffixLength = findCommonSuffix(longtext.subList(0, i),
shorttext.subList(0, j));
if (best_common.size() < suffixLength + prefixLength)
{
best_common = addLists(shorttext.subList(j - suffixLength, j),
shorttext.subList(j, j + prefixLength));
best_longtext_a = longtext.subList(0, i - suffixLength);
best_longtext_b = longtext.subList(i + prefixLength, longtext.size());
best_shorttext_a = shorttext.subList(0, j - suffixLength);
best_shorttext_b = shorttext.subList(j + prefixLength, shorttext.size());
}
oldj= j;
}
if (best_common.size() * 2 >= longtext.size())
{
return new List[] { best_longtext_a, best_longtext_b,
best_shorttext_a, best_shorttext_b, best_common };
}
else
{
return null;
}
}

Discussion