SONAR-3060 Add new CPD algorithm based on suffix tree

11 files changed, 1046 insertions, 0 deletions

diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/AbstractText.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/AbstractText.java
new file mode 100644
index 00000000000..5a3ffa0c14c
--- /dev/null
+++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/AbstractText.java
@@ -0,0 +1,45 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.detector.suffixtree;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public abstract class AbstractText implements Text {
+
+  protected final List<Object> symbols;
+
+  public AbstractText(int size) {
+    this.symbols = new ArrayList<Object>(size);
+  }
+
+  public int length() {
+    return symbols.size();
+  }
+
+  public Object symbolAt(int index) {
+    return symbols.get(index);
+  }
+
+  public List<Object> sequence(int fromIndex, int toIndex) {
+    return symbols.subList(fromIndex, toIndex);
+  }
+
+}
diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/DuplicationsCollector.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/DuplicationsCollector.java
new file mode 100644
index 00000000000..745fb90a3b3
--- /dev/null
+++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/DuplicationsCollector.java
@@ -0,0 +1,200 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.detector.suffixtree;
+
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.List;
+
+import org.sonar.duplications.block.Block;
+import org.sonar.duplications.index.CloneGroup;
+import org.sonar.duplications.index.ClonePart;
+import org.sonar.duplications.utils.FastStringComparator;
+import org.sonar.duplications.utils.SortedListsUtils;
+
+import com.google.common.collect.Lists;
+
+/**
+ * Implementation of {@link Search.Collector}, which constructs {@link CloneGroup}s.
+ */
+public class DuplicationsCollector implements Search.Collector {
+
+  private final GeneralisedHashText text;
+  private final String originResourceId;
+
+  /**
+   * Note that LinkedList should provide better performance here, because of use of operation remove.
+   * 
+   * @see #filter(CloneGroup)
+   */
+  private final List<CloneGroup> filtered = Lists.newLinkedList();
+
+  private int length;
+  private ClonePart origin;
+  private final List<ClonePart> parts = Lists.newArrayList();
+
+  public DuplicationsCollector(GeneralisedHashText text) {
+    this.text = text;
+    this.originResourceId = text.getBlock(0).getResourceId();
+  }
+
+  /**
+   * @return current result
+   */
+  public List<CloneGroup> getResult() {
+    return filtered;
+  }
+
+  public void part(int start, int end, int len) {
+    length = len;
+    Block firstBlock = text.getBlock(start);
+    Block lastBlock = text.getBlock(end - 1);
+
+    ClonePart part = new ClonePart(
+        firstBlock.getResourceId(),
+        firstBlock.getIndexInFile(),
+        firstBlock.getFirstLineNumber(),
+        lastBlock.getLastLineNumber());
+
+    // TODO Godin: maybe use FastStringComparator here ?
+    if (originResourceId.equals(part.getResourceId())) { // part from origin
+      if (origin == null) {
+        origin = part;
+      } else if (part.getUnitStart() < origin.getUnitStart()) {
+        origin = part;
+      }
+    }
+
+    parts.add(part);
+  }
+
+  public void endOfGroup() {
+    Collections.sort(parts, CLONEPART_COMPARATOR);
+    CloneGroup group = new CloneGroup(length, origin, parts);
+    filter(group);
+
+    parts.clear();
+    origin = null;
+  }
+
+  private void filter(CloneGroup current) {
+    Iterator<CloneGroup> i = filtered.iterator();
+    while (i.hasNext()) {
+      CloneGroup earlier = i.next();
+      // Note that following two conditions cannot be true together - proof by contradiction:
+      // let C be the current clone and A and B were found earlier
+      // then since relation is transitive - (A in C) and (C in B) => (A in B)
+      // so A should be filtered earlier
+      if (containsIn(current, earlier)) {
+        // current clone fully covered by clone, which was found earlier
+        return;
+      }
+      // TODO Godin: must prove that this is unused
+      // if (containsIn(earlier, current)) {
+      // // current clone fully covers clone, which was found earlier
+      // i.remove();
+      // }
+    }
+    filtered.add(current);
+  }
+
+  private static final Comparator<ClonePart> CLONEPART_COMPARATOR = new Comparator<ClonePart>() {
+    public int compare(ClonePart o1, ClonePart o2) {
+      int c = RESOURCE_ID_COMPARATOR.compare(o1, o2);
+      if (c == 0) {
+        return o1.getUnitStart() - o2.getUnitStart();
+      }
+      return c;
+    }
+  };
+
+  private static final Comparator<ClonePart> RESOURCE_ID_COMPARATOR = new Comparator<ClonePart>() {
+    public int compare(ClonePart o1, ClonePart o2) {
+      return FastStringComparator.INSTANCE.compare(o1.getResourceId(), o2.getResourceId());
+    }
+  };
+
+  /**
+   * Checks that second clone contains first one.
+   * <p>
+   * Clone A is contained in another clone B, if every part pA from A has part pB in B,
+   * which satisfy the conditions:
+   * <pre>
+   * (pA.resourceId == pB.resourceId) and (pB.unitStart <= pA.unitStart) and (pA.unitEnd <= pB.unitEnd)
+   * </pre>
+   * And all resourcesId from B exactly the same as all resourceId from A, which means that also every part pB from B has part pA in A,
+   * which satisfy the condition:
+   * <pre>
+   * pB.resourceId == pA.resourceId
+   * </pre>
+   * So this relation is:
+   * <ul>
+   * <li>reflexive - A in A</li>
+   * <li>transitive - (A in B) and (B in C) => (A in C)</li>
+   * <li>antisymmetric - (A in B) and (B in A) <=> (A = B)</li>
+   * </ul>
+   * </p>
+   * <p>
+   * This method uses the fact that all parts already sorted by resourceId and unitStart (see {@link #CLONEPART_COMPARATOR}),
+   * so running time - O(|A|+|B|).
+   * </p>
+   */
+  private static boolean containsIn(CloneGroup first, CloneGroup second) {
+    // TODO Godin: must prove that this is unused
+    // if (!first.getOriginPart().getResourceId().equals(second.getOriginPart().getResourceId())) {
+    // return false;
+    // }
+    if (first.getCloneUnitLength() > second.getCloneUnitLength()) {
+      return false;
+    }
+    List<ClonePart> firstParts = first.getCloneParts();
+    List<ClonePart> secondParts = second.getCloneParts();
+    return SortedListsUtils.contains(secondParts, firstParts, new ContainsInComparator(first.getCloneUnitLength(), second.getCloneUnitLength()))
+        && SortedListsUtils.contains(firstParts, secondParts, RESOURCE_ID_COMPARATOR);
+  }
+
+  private static class ContainsInComparator implements Comparator<ClonePart> {
+    private final int l1, l2;
+
+    public ContainsInComparator(int l1, int l2) {
+      this.l1 = l1;
+      this.l2 = l2;
+    }
+
+    public int compare(ClonePart o1, ClonePart o2) {
+      int c = RESOURCE_ID_COMPARATOR.compare(o1, o2);
+      if (c == 0) {
+        if (o2.getUnitStart() <= o1.getUnitStart()) {
+          if (o1.getUnitStart() + l1 <= o2.getUnitStart() + l2) {
+            return 0; // match found - stop search
+          } else {
+            return 1; // continue search
+          }
+        } else {
+          return -1; // o1 < o2 by unitStart - stop search
+        }
+      } else {
+        return c;
+      }
+    }
+  }
+
+}
diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Edge.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Edge.java
new file mode 100644
index 00000000000..968fbd9e226
--- /dev/null
+++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Edge.java
@@ -0,0 +1,79 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.detector.suffixtree;
+
+public final class Edge {
+
+  private int beginIndex; // can't be changed
+  private int endIndex;
+  private Node startNode;
+  private Node endNode; // can't be changed, could be used as edge id
+
+  // each time edge is created, a new end node is created
+  public Edge(int beginIndex, int endIndex, Node startNode) {
+    this.beginIndex = beginIndex;
+    this.endIndex = endIndex;
+    this.startNode = startNode;
+    this.endNode = new Node(startNode, null);
+  }
+
+  public Node splitEdge(Suffix suffix) {
+    remove();
+    Edge newEdge = new Edge(beginIndex, beginIndex + suffix.getSpan(), suffix.getOriginNode());
+    newEdge.insert();
+    newEdge.endNode.setSuffixNode(suffix.getOriginNode());
+    beginIndex += suffix.getSpan() + 1;
+    startNode = newEdge.getEndNode();
+    insert();
+    return newEdge.getEndNode();
+  }
+
+  public void insert() {
+    startNode.addEdge(beginIndex, this);
+  }
+
+  public void remove() {
+    startNode.removeEdge(beginIndex);
+  }
+
+  /**
+   * @return length of this edge in symbols
+   */
+  public int getSpan() {
+    return endIndex - beginIndex;
+  }
+
+  public int getBeginIndex() {
+    return beginIndex;
+  }
+
+  public int getEndIndex() {
+    return endIndex;
+  }
+
+  public Node getStartNode() {
+    return startNode;
+  }
+
+  public Node getEndNode() {
+    return endNode;
+  }
+
+}
diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/GeneralisedHashText.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/GeneralisedHashText.java
new file mode 100644
index 00000000000..202cb85084c
--- /dev/null
+++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/GeneralisedHashText.java
@@ -0,0 +1,77 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.detector.suffixtree;
+
+import java.util.List;
+
+import org.sonar.duplications.block.Block;
+
+import com.google.common.collect.Lists;
+
+public class GeneralisedHashText extends TextSet {
+
+  public GeneralisedHashText(List<Block>... blocks) {
+    super(blocks.length);
+
+    for (int i = 0; i < blocks.length; i++) {
+      addAll(blocks[i]);
+      addTerminator();
+    }
+    finish();
+  }
+
+  private int count;
+  private List<Integer> sizes = Lists.newArrayList();
+
+  public void addBlock(Block block) {
+    symbols.add(block);
+  }
+
+  public void addAll(List<Block> list) {
+    symbols.addAll(list);
+  }
+
+  public void addTerminator() {
+    symbols.add(new Terminator(count));
+    sizes.add(symbols.size());
+    count++;
+  }
+
+  public void finish() {
+    super.lens = new int[sizes.size()];
+    for (int i = 0; i < sizes.size(); i++) {
+      super.lens[i] = sizes.get(i);
+    }
+  }
+
+  @Override
+  public Object symbolAt(int index) {
+    Object obj = super.symbolAt(index);
+    if (obj instanceof Block) {
+      return ((Block) obj).getBlockHash();
+    }
+    return obj;
+  }
+
+  public Block getBlock(int index) {
+    return (Block) super.symbolAt(index);
+  }
+
+}
diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Node.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Node.java
new file mode 100644
index 00000000000..8fa39ecc832
--- /dev/null
+++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Node.java
@@ -0,0 +1,88 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.detector.suffixtree;
+
+import java.util.Map;
+import java.util.HashMap;
+import java.util.Collection;
+
+public final class Node {
+
+  private final SuffixTree suffixTree;
+  private final Map<Object, Edge> edges;
+
+  /**
+   * Node represents string s[i],s[i+1],...,s[j],
+   * suffix-link is a link to node, which represents string s[i+1],...,s[j].
+   */
+  private Node suffixNode;
+
+  /**
+   * Number of symbols from the root to this node.
+   * <p>
+   * Note that this is not equal to number of nodes from root to this node,
+   * because in a compact suffix-tree edge can span multiple symbols - see {@link Edge#getSpan()}.
+   * </p><p>
+   * Depth of {@link #suffixNode} is always equal to this depth minus one.
+   * </p> 
+   */
+  int depth;
+
+  int startSize, endSize;
+
+  public Node(Node node, Node suffixNode) {
+    this(node.suffixTree, suffixNode);
+  }
+
+  public Node(SuffixTree suffixTree, Node suffixNode) {
+    this.suffixTree = suffixTree;
+    this.suffixNode = suffixNode;
+    edges = new HashMap<Object, Edge>();
+  }
+
+  public Object symbolAt(int index) {
+    return suffixTree.symbolAt(index);
+  }
+
+  public void addEdge(int charIndex, Edge edge) {
+    edges.put(symbolAt(charIndex), edge);
+  }
+
+  public void removeEdge(int charIndex) {
+    edges.remove(symbolAt(charIndex));
+  }
+
+  public Edge findEdge(Object ch) {
+    return edges.get(ch);
+  }
+
+  public Node getSuffixNode() {
+    return suffixNode;
+  }
+
+  public void setSuffixNode(Node suffixNode) {
+    this.suffixNode = suffixNode;
+  }
+
+  public Collection<Edge> getEdges() {
+    return edges.values();
+  }
+
+}
diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Search.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Search.java
new file mode 100644
index 00000000000..f13410e90d4
--- /dev/null
+++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Search.java
@@ -0,0 +1,137 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.detector.suffixtree;
+
+import java.util.*;
+
+public final class Search {
+
+  private final SuffixTree tree;
+  private final int[] lens;
+  private final Collector reporter;
+
+  private final List<Integer> list = new ArrayList<Integer>();
+  private final List<Node> innerNodes = new ArrayList<Node>();
+
+  public static void perform(TextSet text, Collector reporter) {
+    new Search(SuffixTree.create(text), text.lens, reporter).compute();
+  }
+
+  private Search(SuffixTree tree, int[] lens, Collector reporter) {
+    this.tree = tree;
+    this.lens = lens;
+    this.reporter = reporter;
+  }
+
+  private void compute() {
+    // O(N)
+    computeDepth();
+
+    // O(N * log(N))
+    Collections.sort(innerNodes, DEPTH_COMPARATOR);
+
+    // O(N), recursive
+    createListOfLeafs(tree.getRootNode());
+
+    // O(N)
+    visitInnerNodes();
+  }
+
+  private void computeDepth() {
+    Queue<Node> queue = new LinkedList<Node>();
+    queue.add(tree.getRootNode());
+    tree.getRootNode().depth = 0;
+    while (!queue.isEmpty()) {
+      Node node = queue.remove();
+      if (!node.getEdges().isEmpty()) {
+        if (node != tree.getRootNode()) { // inner node = not leaf and not root
+          innerNodes.add(node);
+        }
+        for (Edge edge : node.getEdges()) {
+          Node endNode = edge.getEndNode();
+          endNode.depth = node.depth + edge.getSpan() + 1;
+          queue.add(endNode);
+        }
+      }
+    }
+  }
+
+  private static final Comparator<Node> DEPTH_COMPARATOR = new Comparator<Node>() {
+    public int compare(Node o1, Node o2) {
+      return o2.depth - o1.depth;
+    }
+  };
+
+  private void createListOfLeafs(Node node) {
+    node.startSize = list.size();
+    if (node.getEdges().isEmpty()) { // leaf
+      list.add(node.depth);
+    } else {
+      for (Edge edge : node.getEdges()) {
+        createListOfLeafs(edge.getEndNode());
+      }
+      node.endSize = list.size();
+    }
+  }
+
+  /**
+   * Each inner-node represents prefix of some suffixes, thus substring of text.
+   */
+  private void visitInnerNodes() {
+    for (Node node : innerNodes) {
+      if (containsOrigin(node)) {
+        report(node);
+      }
+    }
+  }
+
+  private boolean containsOrigin(Node node) {
+    for (int i = node.startSize; i < node.endSize; i++) {
+      int start = tree.text.length() - list.get(i);
+      int end = start + node.depth;
+      if (end < lens[0]) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  private void report(Node node) {
+    for (int i = node.startSize; i < node.endSize; i++) {
+      int start = tree.text.length() - list.get(i);
+      int end = start + node.depth;
+      reporter.part(start, end, node.depth);
+    }
+    reporter.endOfGroup();
+  }
+
+  public interface Collector {
+
+    /**
+     * @param start start position in generalised text
+     * @param end end position in generalised text
+     */
+    void part(int start, int end, int len);
+
+    void endOfGroup();
+
+  }
+
+}
diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Suffix.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Suffix.java
new file mode 100644
index 00000000000..2f0165d7d41
--- /dev/null
+++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Suffix.java
@@ -0,0 +1,86 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.detector.suffixtree;
+
+public final class Suffix {
+
+  private Node originNode;
+  private int beginIndex;
+  private int endIndex;
+
+  public Suffix(Node originNode, int beginIndex, int endIndex) {
+    this.originNode = originNode;
+    this.beginIndex = beginIndex;
+    this.endIndex = endIndex;
+  }
+
+  public boolean isExplicit() {
+    return beginIndex > endIndex;
+  }
+
+  public boolean isImplicit() {
+    return !isExplicit();
+  }
+
+  public void canonize() {
+    if (isImplicit()) {
+      Edge edge = originNode.findEdge(originNode.symbolAt(beginIndex));
+
+      int edgeSpan = edge.getSpan();
+      while (edgeSpan <= getSpan()) {
+        beginIndex += edgeSpan + 1;
+        originNode = edge.getEndNode();
+        if (beginIndex <= endIndex) {
+          edge = edge.getEndNode().findEdge(originNode.symbolAt(beginIndex));
+          edgeSpan = edge.getSpan();
+        }
+      }
+    }
+  }
+
+  public int getSpan() {
+    return endIndex - beginIndex;
+  }
+
+  public Node getOriginNode() {
+    return originNode;
+  }
+
+  public int getBeginIndex() {
+    return beginIndex;
+  }
+
+  public void incBeginIndex() {
+    beginIndex++;
+  }
+
+  public void changeOriginNode() {
+    originNode = originNode.getSuffixNode();
+  }
+
+  public int getEndIndex() {
+    return endIndex;
+  }
+
+  public void incEndIndex() {
+    endIndex++;
+  }
+
+}
diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/SuffixTree.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/SuffixTree.java
new file mode 100644
index 00000000000..b6e21c940c7
--- /dev/null
+++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/SuffixTree.java
@@ -0,0 +1,109 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.detector.suffixtree;
+
+import com.google.common.base.Objects;
+
+/**
+ * The implementation of the algorithm for constructing suffix-tree based on
+ * <a href="http://illya-keeplearning.blogspot.com/search/label/suffix%20tree">Java-port</a> of
+ * <a href="http://marknelson.us/1996/08/01/suffix-trees/">Mark Nelson's C++ implementation of Ukkonen's algorithm</a>.
+ */
+public final class SuffixTree {
+
+  final Text text;
+
+  private final Node root;
+
+  public static SuffixTree create(Text text) {
+    SuffixTree tree = new SuffixTree(text);
+    Suffix active = new Suffix(tree.root, 0, -1);
+    for (int i = 0; i < text.length(); i++) {
+      tree.addPrefix(active, i);
+    }
+    return tree;
+  }
+
+  private SuffixTree(Text text) {
+    this.text = text;
+    root = new Node(this, null);
+  }
+
+  private void addPrefix(Suffix active, int endIndex) {
+    Node lastParentNode = null;
+    Node parentNode;
+
+    while (true) {
+      Edge edge;
+      parentNode = active.getOriginNode();
+
+      // Step 1 is to try and find a matching edge for the given node.
+      // If a matching edge exists, we are done adding edges, so we break out of this big loop.
+      if (active.isExplicit()) {
+        edge = active.getOriginNode().findEdge(symbolAt(endIndex));
+        if (edge != null) {
+          break;
+        }
+      } else {
+        // implicit node, a little more complicated
+        edge = active.getOriginNode().findEdge(symbolAt(active.getBeginIndex()));
+        int span = active.getSpan();
+        if (Objects.equal(symbolAt(edge.getBeginIndex() + span + 1), symbolAt(endIndex))) {
+          break;
+        }
+        parentNode = edge.splitEdge(active);
+      }
+
+      // We didn't find a matching edge, so we create a new one, add it to the tree at the parent node position,
+      // and insert it into the hash table. When we create a new node, it also means we need to create
+      // a suffix link to the new node from the last node we visited.
+      Edge newEdge = new Edge(endIndex, text.length() - 1, parentNode);
+      newEdge.insert();
+      updateSuffixNode(lastParentNode, parentNode);
+      lastParentNode = parentNode;
+
+      // This final step is where we move to the next smaller suffix
+      if (active.getOriginNode() == root) {
+        active.incBeginIndex();
+      } else {
+        active.changeOriginNode();
+      }
+      active.canonize();
+    }
+    updateSuffixNode(lastParentNode, parentNode);
+    active.incEndIndex(); // Now the endpoint is the next active point
+    active.canonize();
+  }
+
+  private void updateSuffixNode(Node node, Node suffixNode) {
+    if ((node != null) && (node != root)) {
+      node.setSuffixNode(suffixNode);
+    }
+  }
+
+  public Object symbolAt(int index) {
+    return text.symbolAt(index);
+  }
+
+  public Node getRootNode() {
+    return root;
+  }
+
+}
diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/SuffixTreeCloneDetectionAlgorithm.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/SuffixTreeCloneDetectionAlgorithm.java
new file mode 100644
index 00000000000..0bd13a88cbf
--- /dev/null
+++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/SuffixTreeCloneDetectionAlgorithm.java
@@ -0,0 +1,111 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.detector.suffixtree;
+
+import java.util.*;
+
+import org.sonar.duplications.block.Block;
+import org.sonar.duplications.block.ByteArray;
+import org.sonar.duplications.index.CloneGroup;
+import org.sonar.duplications.index.CloneIndex;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
+
+public final class SuffixTreeCloneDetectionAlgorithm {
+
+  public static List<CloneGroup> detect(CloneIndex cloneIndex, Collection<Block> fileBlocks) {
+    if (fileBlocks.isEmpty()) {
+      return Collections.EMPTY_LIST;
+    }
+    GeneralisedHashText text = retrieveFromIndex(cloneIndex, fileBlocks);
+    if (text == null) {
+      return Collections.EMPTY_LIST;
+    }
+    DuplicationsCollector reporter = new DuplicationsCollector(text);
+    Search.perform(text, reporter);
+    return reporter.getResult();
+  }
+
+  private SuffixTreeCloneDetectionAlgorithm() {
+  }
+
+  private static GeneralisedHashText retrieveFromIndex(CloneIndex index, Collection<Block> fileBlocks) {
+    String originResourceId = fileBlocks.iterator().next().getResourceId();
+
+    Set<ByteArray> hashes = Sets.newHashSet();
+    for (Block fileBlock : fileBlocks) {
+      hashes.add(fileBlock.getBlockHash());
+    }
+
+    Map<String, List<Block>> collection = Maps.newHashMap();
+    for (ByteArray hash : hashes) {
+      Collection<Block> blocks = index.getBySequenceHash(hash);
+      for (Block blockFromIndex : blocks) {
+        // Godin: skip blocks for this file if they come from index
+        String resourceId = blockFromIndex.getResourceId();
+        if (!originResourceId.equals(resourceId)) {
+          List<Block> list = collection.get(resourceId);
+          if (list == null) {
+            list = Lists.newArrayList();
+            collection.put(resourceId, list);
+          }
+          list.add(blockFromIndex);
+        }
+      }
+    }
+
+    if (collection.isEmpty() && hashes.size() == fileBlocks.size()) { // optimization for the case when there is no duplications
+      return null;
+    }
+
+    GeneralisedHashText text = new GeneralisedHashText();
+    List<Block> sortedFileBlocks = Lists.newArrayList(fileBlocks);
+    Collections.sort(sortedFileBlocks, BLOCK_COMPARATOR);
+    text.addAll(sortedFileBlocks);
+    text.addTerminator();
+
+    for (List<Block> list : collection.values()) {
+      Collections.sort(list, BLOCK_COMPARATOR);
+
+      int i = 0;
+      while (i < list.size()) {
+        int j = i + 1;
+        while ((j < list.size()) && (list.get(j).getIndexInFile() == list.get(j - 1).getIndexInFile() + 1)) {
+          j++;
+        }
+        text.addAll(list.subList(i, j));
+        text.addTerminator();
+        i = j;
+      }
+    }
+
+    text.finish();
+
+    return text;
+  }
+
+  private static final Comparator<Block> BLOCK_COMPARATOR = new Comparator<Block>() {
+    public int compare(Block o1, Block o2) {
+      return o1.getIndexInFile() - o2.getIndexInFile();
+    }
+  };
+
+}
diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Text.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Text.java
new file mode 100644
index 00000000000..19b644d494a
--- /dev/null
+++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/Text.java
@@ -0,0 +1,41 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.detector.suffixtree;
+
+import java.util.List;
+
+/**
+ * Represents text.
+ */
+public interface Text {
+
+  /**
+   * @return length of the sequence of symbols represented by this object
+   */
+  int length();
+
+  /**
+   * @return symbol at the specified index
+   */
+  Object symbolAt(int index);
+
+  List<Object> sequence(int fromIndex, int toIndex);
+
+}
diff --git a/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/TextSet.java b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/TextSet.java
new file mode 100644
index 00000000000..aa3628ed048
--- /dev/null
+++ b/sonar-duplications/src/main/java/org/sonar/duplications/detector/suffixtree/TextSet.java
@@ -0,0 +1,73 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2011 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.duplications.detector.suffixtree;
+
+/**
+ * Simplifies construction of <a href="http://en.wikipedia.org/wiki/Generalised_suffix_tree">generalised suffix-tree</a>.
+ */
+public class TextSet extends AbstractText {
+
+  int[] lens;
+
+  public TextSet(int size) {
+    super(100); // FIXME
+
+    lens = new int[size];
+  }
+
+  public TextSet(Text... text) {
+    this(text.length);
+    for (int i = 0; i < text.length; i++) {
+      symbols.addAll(text[i].sequence(0, text[i].length()));
+      symbols.add(new Terminator(i));
+      lens[i] = symbols.size();
+    }
+  }
+
+  public static class Terminator {
+
+    private final int stringNumber;
+
+    public Terminator(int i) {
+      this.stringNumber = i;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+      return (obj instanceof Terminator) && (((Terminator) obj).stringNumber == stringNumber);
+    }
+
+    @Override
+    public int hashCode() {
+      return stringNumber;
+    }
+
+    public int getStringNumber() {
+      return stringNumber;
+    }
+
+    @Override
+    public String toString() {
+      return "$" + stringNumber;
+    }
+
+  }
+
+}