Merge pull request #3211 from vespa-engine/geirst/sort-document-types-in-topological-order

Sort list of document types in topological order (according to docume…

4 files changed, 143 insertions, 1 deletions

diff --git a/config-model/src/main/java/com/yahoo/vespa/model/content/ContentSearchCluster.java b/config-model/src/main/java/com/yahoo/vespa/model/content/ContentSearchCluster.java
index 4481c53e248..b54978f52d3 100644
--- a/config-model/src/main/java/com/yahoo/vespa/model/content/ContentSearchCluster.java
+++ b/config-model/src/main/java/com/yahoo/vespa/model/content/ContentSearchCluster.java
@@ -276,7 +276,7 @@ public class ContentSearchCluster extends AbstractConfigProducer implements Prot
     @Override
     public void getConfig(ProtonConfig.Builder builder) {
         double visibilityDelay = hasIndexedCluster() ? getIndexed().getVisibilityDelay() : 0.0;
-        for (NewDocumentType type : documentDefinitions.values()) {
+        for (NewDocumentType type : TopologicalDocumentTypeSorter.sort(documentDefinitions.values())) {
             ProtonConfig.Documentdb.Builder ddbB = new ProtonConfig.Documentdb.Builder();
             String docTypeName = type.getFullName().getName();
             boolean globalDocType = isGloballyDistributed(type);
diff --git a/config-model/src/main/java/com/yahoo/vespa/model/content/TopologicalDocumentTypeSorter.java b/config-model/src/main/java/com/yahoo/vespa/model/content/TopologicalDocumentTypeSorter.java
new file mode 100644
index 00000000000..2f749a28f2d
--- /dev/null
+++ b/config-model/src/main/java/com/yahoo/vespa/model/content/TopologicalDocumentTypeSorter.java
@@ -0,0 +1,46 @@
+package com.yahoo.vespa.model.content;
+
+import com.yahoo.documentmodel.NewDocumentType;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * Class that sorts a list of document types in topological order
+ * according to the document references between the types.
+ *
+ * Document types without any outgoing document references are considered
+ * to be first in the topological order.
+ *
+ * @author geirst
+ */
+public class TopologicalDocumentTypeSorter {
+
+    private final Map<String, NewDocumentType> unsortedTypes = new LinkedHashMap<>();
+    private final Map<String, NewDocumentType> sortedTypes = new LinkedHashMap<>();
+
+    private TopologicalDocumentTypeSorter(Collection<NewDocumentType> documentTypes) {
+        documentTypes.forEach(docType -> unsortedTypes.put(docType.getName(), docType));
+        unsortedTypes.values().forEach(docType -> depthFirstTraverse(docType));
+    }
+
+    private void depthFirstTraverse(NewDocumentType docType) {
+        // Note that cycles are not allowed and detected earlier in DocumentGraphValidator.
+        if (sortedTypes.containsKey(docType.getName())) {
+            return;
+        }
+        for (NewDocumentType.Name referenceDocTypeName : docType.getDocumentReferences()) {
+            NewDocumentType referenceDocType = unsortedTypes.get(referenceDocTypeName.getName());
+            depthFirstTraverse(referenceDocType);
+        }
+        sortedTypes.put(docType.getName(), docType);
+    }
+
+    public static List<NewDocumentType> sort(Collection<NewDocumentType> documentTypes) {
+        TopologicalDocumentTypeSorter sorter = new TopologicalDocumentTypeSorter(documentTypes);
+        return new ArrayList<>(sorter.sortedTypes.values());
+    }
+}
diff --git a/config-model/src/test/java/com/yahoo/vespa/model/content/ContentSearchClusterTest.java b/config-model/src/test/java/com/yahoo/vespa/model/content/ContentSearchClusterTest.java
index d2166b170da..5f18b28d6ce 100644
--- a/config-model/src/test/java/com/yahoo/vespa/model/content/ContentSearchClusterTest.java
+++ b/config-model/src/test/java/com/yahoo/vespa/model/content/ContentSearchClusterTest.java
@@ -4,10 +4,14 @@ package com.yahoo.vespa.model.content;
 import com.yahoo.vespa.config.search.core.ProtonConfig;
 import com.yahoo.vespa.model.content.cluster.ContentCluster;
 import com.yahoo.vespa.model.content.utils.ContentClusterBuilder;
+import com.yahoo.vespa.model.content.utils.SearchDefinitionBuilder;
 import org.junit.Test;
 
+import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.List;
 
+import static com.yahoo.config.model.test.TestUtil.joinLines;
 import static com.yahoo.vespa.model.content.utils.ContentClusterUtils.createCluster;
 import static com.yahoo.vespa.model.content.utils.SearchDefinitionBuilder.createSearchDefinitions;
 import static junit.framework.TestCase.assertEquals;
@@ -86,4 +90,28 @@ public class ContentSearchClusterTest {
         assertEquals(expGlobal, db.global());
     }
 
+    @Test
+    public void require_that_document_types_with_references_are_topologically_sorted() throws Exception {
+        ProtonConfig cfg = getProtonConfig(createClusterWithThreeDocumentTypes());
+        assertEquals(3, cfg.documentdb().size());
+        assertDocumentDb("c", true, cfg.documentdb(0));
+        assertDocumentDb("b", true, cfg.documentdb(1));
+        assertDocumentDb("a", false, cfg.documentdb(2));
+    }
+
+    private static ContentCluster createClusterWithThreeDocumentTypes() throws Exception {
+        List<String> searchDefinitions = new ArrayList<>();
+        searchDefinitions.add(new SearchDefinitionBuilder().name("a")
+                .content(joinLines("field ref_to_b type reference<b> { indexing: attribute }",
+                                   "field ref_to_c type reference<c> { indexing: attribute }")).build());
+        searchDefinitions.add(new SearchDefinitionBuilder().name("b")
+                .content("field ref_to_c type reference<c> { indexing: attribute }").build());
+        searchDefinitions.add(new SearchDefinitionBuilder().name("c").build());
+        return createCluster(new ContentClusterBuilder().docTypes(Arrays.asList(
+                new ContentClusterBuilder.DocType("a"),
+                new ContentClusterBuilder.DocType("b", true),
+                new ContentClusterBuilder.DocType("c", true))).getXml(),
+                searchDefinitions);
+    }
+
 }
diff --git a/config-model/src/test/java/com/yahoo/vespa/model/content/TopologicalDocumentTypeSorterTest.java b/config-model/src/test/java/com/yahoo/vespa/model/content/TopologicalDocumentTypeSorterTest.java
new file mode 100644
index 00000000000..ddac6562612
--- /dev/null
+++ b/config-model/src/test/java/com/yahoo/vespa/model/content/TopologicalDocumentTypeSorterTest.java
@@ -0,0 +1,68 @@
+package com.yahoo.vespa.model.content;
+
+import com.yahoo.documentmodel.NewDocumentType;
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author geirst
+ */
+public class TopologicalDocumentTypeSorterTest {
+
+    @Test
+    public void require_that_types_without_references_are_returned_in_input_order() {
+        assertOrder(Arrays.asList("a"), new DocumentTypesBuilder().add("a"));
+        assertOrder(Arrays.asList("a", "c", "b"),
+                new DocumentTypesBuilder().add("a").add("c").add("b"));
+    }
+
+    @Test
+    public void require_that_types_with_references_are_sorted_in_topological_order() {
+        assertOrder(Arrays.asList("b", "a"), new DocumentTypesBuilder()
+                .add("a", Arrays.asList("b"))
+                .add("b"));
+        assertOrder(Arrays.asList("c", "b", "a"), new DocumentTypesBuilder()
+                .add("a", Arrays.asList("b", "c"))
+                .add("b", Arrays.asList("c"))
+                .add("c"));
+        assertOrder(Arrays.asList("b", "a", "d", "c"), new DocumentTypesBuilder()
+                .add("a", Arrays.asList("b"))
+                .add("b")
+                .add("c", Arrays.asList("d"))
+                .add("d"));
+    }
+
+    private void assertOrder(List<String> expOrder, DocumentTypesBuilder builder) {
+        List<NewDocumentType> sortedDocTypes = TopologicalDocumentTypeSorter.sort(builder.build());
+        List<String> actOrder = sortedDocTypes.stream().map(NewDocumentType::getName).collect(Collectors.toList());
+        assertEquals(expOrder, actOrder);
+    }
+
+    private static class DocumentTypesBuilder {
+
+        private final List<NewDocumentType> result = new ArrayList<>();
+
+        public DocumentTypesBuilder add(String docTypeName) {
+            return add(docTypeName, Collections.emptyList());
+        }
+
+        public DocumentTypesBuilder add(String docTypeName, List<String> docTypeNameReferences) {
+            Set<NewDocumentType.Name> documentReferences =
+                    docTypeNameReferences.stream().map(NewDocumentType.Name::new).collect(Collectors.toSet());
+            result.add(new NewDocumentType(new NewDocumentType.Name(docTypeName), documentReferences));
+            return this;
+        }
+
+        public List<NewDocumentType> build() {
+            return result;
+        }
+    }
+}