1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
package com.yahoo.schema.derived;
import com.yahoo.document.DataTypeName;
import com.yahoo.schema.DocumentReference;
import com.yahoo.schema.DocumentReferences;
import com.yahoo.schema.Schema;
import com.yahoo.schema.document.SDDocumentType;
import java.util.*;
/**
* <p>A class which can reorder a list of search definitions such that any supertype
* always preceed any subtype. Subject to this condition the given order
* is preserved (the minimal reordering is done).</p>
*
* <p>This class is <b>not</b> multithread safe. Only one ordering must be done
* at the time in any instance.</p>
*
* @author bratseth
* @author bjorncs
*/
public class SearchOrderer {
/** A map from DataTypeName to the Search defining them */
private final Map<DataTypeName, Schema> documentNameToSearch = new HashMap<>();
/**
* Reorders the given list of search definitions such that any supertype
* always preceed any subtype. Subject to this condition the given order
* is preserved (the minimal reordering is done).
*
* @return a new list containing the same search instances in the right order
*/
public List<Schema> order(List<Schema> unordered) {
// No, this is not a fast algorithm...
indexOnDocumentName(unordered);
List<Schema> ordered = new ArrayList<>(unordered.size());
List<Schema> moveOutwards = new ArrayList<>();
for (Schema schema : unordered) {
if (allDependenciesAlreadyEmitted(ordered, schema)) {
addOrdered(ordered, schema, moveOutwards);
}
else {
moveOutwards.add(schema);
}
}
// Any leftovers means we have search definitions with undefined inheritants.
// This is warned about elsewhere.
ordered.addAll(moveOutwards);
documentNameToSearch.clear();
return ordered;
}
private void addOrdered(List<Schema> ordered, Schema schema, List<Schema> moveOutwards) {
ordered.add(schema);
Schema eligibleMove;
do {
eligibleMove = removeFirstEntryWithFullyEmittedDependencies(moveOutwards, ordered);
if (eligibleMove != null) {
ordered.add(eligibleMove);
}
} while (eligibleMove != null);
}
/** Removes and returns the first search from the move list which can now be added, or null if none */
private Schema removeFirstEntryWithFullyEmittedDependencies(List<Schema> moveOutwards, List<Schema> ordered) {
for (Schema move : moveOutwards) {
if (allDependenciesAlreadyEmitted(ordered, move)) {
moveOutwards.remove(move);
return move;
}
}
return null;
}
private boolean allDependenciesAlreadyEmitted(List<Schema> alreadyOrdered, Schema schema) {
if (schema.getDocument() == null) {
return true;
}
SDDocumentType document = schema.getDocument();
return allInheritedDependenciesEmitted(alreadyOrdered, document) && allReferenceDependenciesEmitted(alreadyOrdered, document);
}
private boolean allInheritedDependenciesEmitted(List<Schema> alreadyOrdered, SDDocumentType document) {
for (SDDocumentType sdoc : document.getInheritedTypes() ) {
DataTypeName inheritedName = sdoc.getDocumentName();
if ("document".equals(inheritedName.getName())) {
continue;
}
Schema inheritedSchema = documentNameToSearch.get(inheritedName);
if (!alreadyOrdered.contains(inheritedSchema)) {
return false;
}
}
return true;
}
private static boolean allReferenceDependenciesEmitted(List<Schema> alreadyOrdered, SDDocumentType document) {
DocumentReferences documentReferences = document.getDocumentReferences()
.orElseThrow(() -> new IllegalStateException("Missing document references. Should have been processed by now."));
return documentReferences.stream()
.map(Map.Entry::getValue)
.map(DocumentReference::targetSearch)
.allMatch(alreadyOrdered::contains);
}
private void indexOnDocumentName(List<Schema> schemas) {
documentNameToSearch.clear();
for (Schema schema : schemas) {
if (schema.getDocument() != null) {
documentNameToSearch.put(schema.getDocument().getDocumentName(), schema);
}
}
}
}
|
