001package gudusoft.gsqlparser.lineage.v2.validation;
002
003import gudusoft.gsqlparser.lineage.v2.Finding;
004
005import java.util.ArrayList;
006import java.util.Arrays;
007import java.util.Collections;
008import java.util.HashMap;
009import java.util.List;
010import java.util.Map;
011import java.util.TreeMap;
012
013import static gudusoft.gsqlparser.lineage.v2.validation.DocumentIndex.intRef;
014import static gudusoft.gsqlparser.lineage.v2.validation.DocumentIndex.items;
015
016/**
017 * Validation stage {@code REFERENCE} (specification Section 14.2) as the reference runner implements it
018 * ({@code conformance/run.py}, {@code stage_reference}): one reference space for every object that carries a
019 * {@code ref} ({@code REF_DUPLICATE}), every reference names an object ({@code REF_DANGLING}) of an allowed
020 * kind ({@code REF_WRONG_TARGET}), and owner and parent chains do not return to themselves
021 * ({@code REF_OWNER_CYCLE}).
022 *
023 * @since 4.2.17
024 */
025public final class ReferenceStage {
026
027    private final Map<Long, String> kindOf = new HashMap<Long, String>();
028    private final List<Finding> findings = new ArrayList<Finding>();
029
030    private ReferenceStage() {
031    }
032
033    /** The findings of the stage. */
034    public static List<Finding> run(Map<?, ?> doc) {
035        return new ReferenceStage().check(doc);
036    }
037
038    private static final List<String> ANY = null;
039
040    private static List<String> kinds(String... names) {
041        return Arrays.asList(names);
042    }
043
044    private void register(String kind, Map<?, ?> obj, String where) {
045        Long ref = intRef(obj.get("ref"));
046        if (ref == null) {
047            return;
048        }
049        if (kindOf.containsKey(ref)) {
050            findings.add(new Finding("REF_DUPLICATE", where, "ref " + ref + " is already a " + kindOf.get(ref)));
051        } else {
052            kindOf.put(ref, kind);
053        }
054    }
055
056    private void check(Object value, List<String> allowed, String where) {
057        Long ref = intRef(value);
058        if (ref == null) {
059            return;
060        }
061        if (!kindOf.containsKey(ref)) {
062            findings.add(new Finding("REF_DANGLING", where, "ref " + ref + " names no object"));
063        } else if (allowed != ANY && !allowed.contains(kindOf.get(ref))) {
064            findings.add(new Finding("REF_WRONG_TARGET", where, "ref " + ref + " is a " + kindOf.get(ref) + ", not " + allowed));
065        }
066    }
067
068    private void checkMany(Object values, List<String> allowed, String where) {
069        if (values instanceof List<?>) {
070            for (Object value : (List<?>) values) {
071                check(value, allowed, where);
072            }
073        }
074    }
075
076    private void checkBinding(Object binding, String where) {
077        if (binding instanceof Map<?, ?>) {
078            Map<?, ?> b = (Map<?, ?>) binding;
079            check(b.get("scopeRef"), kinds("scope"), where + ".scopeRef");
080            check(b.get("declarationRef"), kinds("statement"), where + ".declarationRef");
081            check(b.get("candidateSetRef"), kinds("candidateSet"), where + ".candidateSetRef");
082        }
083    }
084
085    /** The references of a candidate set's decidedBy (fold-v1, Sections 4.3 and 7.1). */
086    private void checkDecision(Object decidedBy, List<String> members, String where) {
087        if (decidedBy instanceof Map<?, ?>) {
088            Map<?, ?> decided = (Map<?, ?>) decidedBy;
089            check(decided.get("candidateSetRef"), kinds("candidateSet"), where + ".candidateSetRef");
090            List<Map<?, ?>> pairs = items(decided.get("alignment"));
091            for (int j = 0; j < pairs.size(); j++) {
092                check(pairs.get(j).get("alternativeRef"), members, where + ".alignment[" + j + "].alternativeRef");
093                check(pairs.get(j).get("candidateRef"), members, where + ".alignment[" + j + "].candidateRef");
094            }
095        }
096    }
097
098    private void checkSpan(Object span, String where) {
099        if (span instanceof Map<?, ?>) {
100            check(((Map<?, ?>) span).get("sourceUnitRef"), kinds("sourceUnit"), where + ".sourceUnitRef");
101        }
102    }
103
104    private void checkFeatures(Object features, String where) {
105        List<Map<?, ?>> list = items(features);
106        for (int j = 0; j < list.size(); j++) {
107            checkMany(list.get(j).get("diagnosticRefs"), kinds("diagnostic"), where + "[" + j + "].diagnosticRefs");
108        }
109    }
110
111    private List<Finding> check(Map<?, ?> doc) {
112        Map<?, ?> graph = doc.get("explainGraph") instanceof Map<?, ?> ? (Map<?, ?>) doc.get("explainGraph")
113                : Collections.emptyMap();
114        Object[][] collections = {
115                {"analysisContext", "analysisContexts", doc.get("analysisContexts")},
116                {"sourceUnit", "sourceUnits", doc.get("sourceUnits")}, {"statement", "statements", doc.get("statements")},
117                {"scope", "scopes", doc.get("scopes")}, {"endpoint", "endpoints", doc.get("endpoints")},
118                {"fact", "facts", doc.get("facts")}, {"factCandidate", "factCandidates", doc.get("factCandidates")},
119                {"candidateSet", "candidateSets", doc.get("candidateSets")},
120                {"occurrence", "occurrences", doc.get("occurrences")},
121                {"tfo", "targetFieldOccurrences", doc.get("targetFieldOccurrences")},
122                {"diagnostic", "diagnostics", doc.get("diagnostics")},
123                {"node", "explainGraph.nodes", graph.get("nodes")},
124                {"microEdge", "explainGraph.microEdges", graph.get("microEdges")},
125                {"candidateSet", "explainGraph.candidateSets", graph.get("candidateSets")},
126                {"supportPath", "explainGraph.supportPaths", graph.get("supportPaths")}};
127        for (Object[] collection : collections) {
128            List<Map<?, ?>> list = items(collection[2]);
129            for (int i = 0; i < list.size(); i++) {
130                register((String) collection[0], list.get(i), collection[1] + "[" + i + "]");
131            }
132        }
133        List<Map<?, ?>> candidates = items(doc.get("factCandidates"));
134        for (int i = 0; i < candidates.size(); i++) {
135            for (String side : new String[] {"source", "target"}) {
136                Object end = candidates.get(i).get(side);
137                if (end instanceof Map<?, ?> && ((Map<?, ?>) end).get("candidateSet") instanceof Map<?, ?>) {
138                    register("candidateSet", (Map<?, ?>) ((Map<?, ?>) end).get("candidateSet"),
139                            "factCandidates[" + i + "]." + side + ".candidateSet");
140                }
141            }
142        }
143        for (String member : DocumentIndex.MODULE_MEMBERS) {
144            List<Map<?, ?>> list = items(doc.get(member));
145            for (int i = 0; i < list.size(); i++) {
146                register("module:" + member, list.get(i), member + "[" + i + "]");
147            }
148        }
149
150        List<Map<?, ?>> list = items(doc.get("sourceUnits"));
151        for (int i = 0; i < list.size(); i++) {
152            Map<?, ?> o = list.get(i);
153            String w = "sourceUnits[" + i + "]";
154            check(o.get("analysisContextRef"), kinds("analysisContext"), w + ".analysisContextRef");
155            check(o.get("parentUnitRef"), kinds("sourceUnit"), w + ".parentUnitRef");
156            check(o.get("siteStatementRef"), kinds("statement"), w + ".siteStatementRef");
157            checkSpan(o.get("siteSpan"), w + ".siteSpan");
158            checkMany(o.get("diagnosticRefs"), kinds("diagnostic"), w + ".diagnosticRefs");
159            checkFeatures(o.get("featureCompleteness"), w + ".featureCompleteness");
160        }
161        list = items(doc.get("statements"));
162        for (int i = 0; i < list.size(); i++) {
163            Map<?, ?> o = list.get(i);
164            String w = "statements[" + i + "]";
165            check(o.get("sourceUnitRef"), kinds("sourceUnit"), w + ".sourceUnitRef");
166            checkMany(o.get("diagnosticRefs"), kinds("diagnostic"), w + ".diagnosticRefs");
167            checkFeatures(o.get("featureCompleteness"), w + ".featureCompleteness");
168        }
169        list = items(doc.get("scopes"));
170        for (int i = 0; i < list.size(); i++) {
171            Map<?, ?> o = list.get(i);
172            String w = "scopes[" + i + "]";
173            check(o.get("parentRef"), kinds("scope"), w + ".parentRef");
174            check(o.get("statementRef"), kinds("statement"), w + ".statementRef");
175            check(o.get("sourceUnitRef"), kinds("sourceUnit"), w + ".sourceUnitRef");
176        }
177        list = items(doc.get("endpoints"));
178        for (int i = 0; i < list.size(); i++) {
179            Map<?, ?> o = list.get(i);
180            String w = "endpoints[" + i + "]";
181            check(o.get("ownerRef"), kinds("endpoint"), w + ".ownerRef");
182            check(o.get("statementRef"), kinds("statement"), w + ".statementRef");
183            check(o.get("scopeRef"), kinds("scope"), w + ".scopeRef");
184            check(o.get("resolvesToRef"), kinds("endpoint"), w + ".resolvesToRef");
185        }
186        list = items(doc.get("facts"));
187        for (int i = 0; i < list.size(); i++) {
188            Map<?, ?> o = list.get(i);
189            String w = "facts[" + i + "]";
190            check(o.get("sourceRef"), kinds("endpoint"), w + ".sourceRef");
191            check(o.get("targetRef"), kinds("endpoint"), w + ".targetRef");
192            if (o.get("datasetDependency") instanceof Map<?, ?>) {
193                checkMany(((Map<?, ?>) o.get("datasetDependency")).get("supportingFactRefs"), kinds("fact"),
194                        w + ".datasetDependency.supportingFactRefs");
195            }
196        }
197        List<Map<?, ?>> rootSets = items(doc.get("candidateSets"));
198        for (int i = 0; i < rootSets.size(); i++) {
199            checkMany(rootSets.get(i).get("candidateRefs"), kinds("endpoint"), "candidateSets[" + i + "].candidateRefs");
200        }
201        for (int i = 0; i < candidates.size(); i++) {
202            Map<?, ?> o = candidates.get(i);
203            for (String side : new String[] {"source", "target"}) {
204                Object end = o.get(side);
205                String w = "factCandidates[" + i + "]." + side;
206                if (end instanceof Map<?, ?>) {
207                    Map<?, ?> e = (Map<?, ?>) end;
208                    check(e.get("endpointRef"), kinds("endpoint"), w + ".endpointRef");
209                    if (e.get("candidateSet") instanceof Map<?, ?>) {
210                        checkMany(((Map<?, ?>) e.get("candidateSet")).get("candidateRefs"), kinds("endpoint"),
211                                w + ".candidateSet.candidateRefs");
212                        checkDecision(((Map<?, ?>) e.get("candidateSet")).get("decidedBy"), kinds("endpoint"),
213                                w + ".candidateSet.decidedBy");
214                    }
215                }
216            }
217            List<Map<?, ?>> outcomes = items(o.get("outcomes"));
218            for (int j = 0; j < outcomes.size(); j++) {
219                List<Map<?, ?>> pairs = items(outcomes.get(j).get("pairs"));
220                for (int k = 0; k < pairs.size(); k++) {
221                    String w = "factCandidates[" + i + "].outcomes[" + j + "].pairs[" + k + "]";
222                    check(pairs.get(k).get("sourceRef"), kinds("endpoint"), w + ".sourceRef");
223                    check(pairs.get(k).get("targetRef"), kinds("endpoint"), w + ".targetRef");
224                }
225            }
226        }
227        list = items(doc.get("occurrences"));
228        for (int i = 0; i < list.size(); i++) {
229            Map<?, ?> o = list.get(i);
230            String w = "occurrences[" + i + "]";
231            check(o.get("factRef"), kinds("fact"), w + ".factRef");
232            check(o.get("factCandidateRef"), kinds("factCandidate"), w + ".factCandidateRef");
233            check(o.get("statementRef"), kinds("statement"), w + ".statementRef");
234            checkBinding(o.get("sourceBinding"), w + ".sourceBinding");
235            checkBinding(o.get("targetBinding"), w + ".targetBinding");
236            checkMany(o.get("supportPathRefs"), kinds("supportPath"), w + ".supportPathRefs");
237            checkMany(o.get("evidenceRefs"), kinds("module:evidence"), w + ".evidenceRefs");
238            checkMany(o.get("diagnosticRefs"), kinds("diagnostic"), w + ".diagnosticRefs");
239        }
240        list = items(doc.get("targetFieldOccurrences"));
241        for (int i = 0; i < list.size(); i++) {
242            Map<?, ?> o = list.get(i);
243            String w = "targetFieldOccurrences[" + i + "]";
244            check(o.get("statementRef"), kinds("statement"), w + ".statementRef");
245            check(o.get("targetRef"), kinds("endpoint"), w + ".targetRef");
246            checkMany(o.get("diagnosticRefs"), kinds("diagnostic"), w + ".diagnosticRefs");
247            List<Map<?, ?>> inputs = items(o.get("inputs"));
248            for (int j = 0; j < inputs.size(); j++) {
249                Map<?, ?> input = inputs.get(j);
250                String wi = w + ".inputs[" + j + "]";
251                check(input.get("factRef"), kinds("fact"), wi + ".factRef");
252                check(input.get("factCandidateRef"), kinds("factCandidate"), wi + ".factCandidateRef");
253                check(input.get("parameterRef"), kinds("endpoint"), wi + ".parameterRef");
254                check(input.get("sequenceRef"), kinds("endpoint"), wi + ".sequenceRef");
255            }
256        }
257        list = items(doc.get("diagnostics"));
258        for (int i = 0; i < list.size(); i++) {
259            Map<?, ?> o = list.get(i);
260            String w = "diagnostics[" + i + "]";
261            checkMany(o.get("subjectRefs"), ANY, w + ".subjectRefs");
262            checkSpan(o.get("span"), w + ".span");
263        }
264        checkFeatures(doc.get("featureCompleteness"), "featureCompleteness");
265        list = items(graph.get("nodes"));
266        for (int i = 0; i < list.size(); i++) {
267            Map<?, ?> o = list.get(i);
268            String w = "explainGraph.nodes[" + i + "]";
269            check(o.get("statementRef"), kinds("statement"), w + ".statementRef");
270            check(o.get("parentRef"), kinds("node"), w + ".parentRef");
271            check(o.get("ownerRef"), kinds("node"), w + ".ownerRef");
272            checkSpan(o.get("span"), w + ".span");
273            checkMany(o.get("diagnosticRefs"), kinds("diagnostic"), w + ".diagnosticRefs");
274        }
275        list = items(graph.get("microEdges"));
276        for (int i = 0; i < list.size(); i++) {
277            Map<?, ?> o = list.get(i);
278            String w = "explainGraph.microEdges[" + i + "]";
279            check(o.get("statementRef"), kinds("statement"), w + ".statementRef");
280            check(o.get("sourceRef"), kinds("endpoint", "node", "candidateSet"), w + ".sourceRef");
281            check(o.get("targetRef"), kinds("endpoint", "node"), w + ".targetRef");
282            checkBinding(o.get("sourceBinding"), w + ".sourceBinding");
283            checkBinding(o.get("targetBinding"), w + ".targetBinding");
284            checkMany(o.get("diagnosticRefs"), kinds("diagnostic"), w + ".diagnosticRefs");
285        }
286        list = items(graph.get("candidateSets"));
287        for (int i = 0; i < list.size(); i++) {
288            checkMany(list.get(i).get("candidateRefs"), kinds("endpoint", "node"),
289                    "explainGraph.candidateSets[" + i + "].candidateRefs");
290            checkDecision(list.get(i).get("decidedBy"), kinds("endpoint", "node"),
291                    "explainGraph.candidateSets[" + i + "].decidedBy");
292        }
293        list = items(graph.get("supportPaths"));
294        for (int i = 0; i < list.size(); i++) {
295            checkMany(list.get(i).get("microEdgeRefs"), kinds("microEdge"),
296                    "explainGraph.supportPaths[" + i + "].microEdgeRefs");
297        }
298        list = items(graph.get("statementCompleteness"));
299        for (int i = 0; i < list.size(); i++) {
300            Map<?, ?> o = list.get(i);
301            String w = "explainGraph.statementCompleteness[" + i + "]";
302            check(o.get("statementRef"), kinds("statement"), w + ".statementRef");
303            checkMany(o.get("diagnosticRefs"), kinds("diagnostic"), w + ".diagnosticRefs");
304        }
305
306        cycles(doc.get("endpoints"), "ownerRef", "endpoints");
307        cycles(doc.get("scopes"), "parentRef", "scopes");
308        cycles(graph.get("nodes"), "parentRef", "explainGraph.nodes");
309        cycles(graph.get("nodes"), "ownerRef", "explainGraph.nodes");
310        return findings;
311    }
312
313    /**
314     * {@code REF_OWNER_CYCLE} for every object whose chain of {@code member} returns to it. Each object has at
315     * most one successor, so the objects on cycles are found in one pass (the reference walks the chain from
316     * every object, which is quadratic on long chains).
317     */
318    private void cycles(Object objects, String member, String label) {
319        Map<Long, Map<?, ?>> byRef = new TreeMap<Long, Map<?, ?>>();
320        for (Map<?, ?> obj : items(objects)) {
321            Long ref = intRef(obj.get("ref"));
322            if (ref != null) {
323                byRef.put(ref, obj); // the last object with a reference wins, as in the reference's dict
324            }
325        }
326        Map<Long, Integer> state = new HashMap<Long, Integer>(); // 1 on the current walk, 2 done
327        java.util.Set<Long> onCycle = new java.util.HashSet<Long>();
328        for (Long start : byRef.keySet()) {
329            if (state.containsKey(start)) {
330                continue;
331            }
332            List<Long> walk = new ArrayList<Long>();
333            Long current = start;
334            while (current != null && byRef.containsKey(current) && !state.containsKey(current)) {
335                state.put(current, 1);
336                walk.add(current);
337                current = intRef(byRef.get(current).get(member));
338            }
339            if (current != null && Integer.valueOf(1).equals(state.get(current))) {
340                for (int i = walk.indexOf(current); i < walk.size(); i++) {
341                    onCycle.add(walk.get(i));
342                }
343            }
344            for (Long ref : walk) {
345                state.put(ref, 2);
346            }
347        }
348        for (Long ref : byRef.keySet()) {
349            if (onCycle.contains(ref)) {
350                findings.add(new Finding("REF_OWNER_CYCLE", label + " ref " + ref, member + " chain returns to it"));
351            }
352        }
353    }
354}