feat(langugage): detect ambiguous references

5 files changed, 439 insertions, 2 deletions

diff --git a/subprojects/language/src/main/java/tools/refinery/language/ProblemRuntimeModule.java b/subprojects/language/src/main/java/tools/refinery/language/ProblemRuntimeModule.java
index 2636a8ee..100f3781 100644
--- a/subprojects/language/src/main/java/tools/refinery/language/ProblemRuntimeModule.java
+++ b/subprojects/language/src/main/java/tools/refinery/language/ProblemRuntimeModule.java
@@ -12,6 +12,7 @@ package tools.refinery.language;
 import com.google.inject.Binder;
 import com.google.inject.name.Names;
 import org.eclipse.xtext.conversion.IValueConverterService;
+import org.eclipse.xtext.linking.ILinkingService;
 import org.eclipse.xtext.naming.IQualifiedNameConverter;
 import org.eclipse.xtext.parser.IParser;
 import org.eclipse.xtext.resource.*;
@@ -22,10 +23,12 @@ import org.eclipse.xtext.serializer.sequencer.ISemanticSequencer;
 import org.eclipse.xtext.validation.IResourceValidator;
 import org.eclipse.xtext.xbase.annotations.validation.DerivedStateAwareResourceValidator;
 import tools.refinery.language.conversion.ProblemValueConverterService;
+import tools.refinery.language.linking.ProblemLinkingService;
 import tools.refinery.language.naming.ProblemQualifiedNameConverter;
 import tools.refinery.language.parser.antlr.TokenSourceInjectingProblemParser;
 import tools.refinery.language.resource.ProblemDerivedStateComputer;
 import tools.refinery.language.resource.ProblemLocationInFileProvider;
+import tools.refinery.language.resource.ProblemResource;
 import tools.refinery.language.resource.ProblemResourceDescriptionStrategy;
 import tools.refinery.language.scoping.ProblemGlobalScopeProvider;
 import tools.refinery.language.scoping.ProblemLocalScopeProvider;
@@ -55,6 +58,11 @@ public class ProblemRuntimeModule extends AbstractProblemRuntimeModule {
         }
 
         @Override
+        public Class<? extends ILinkingService> bindILinkingService() {
+                return ProblemLinkingService.class;
+        }
+
+        @Override
         public Class<? extends IGlobalScopeProvider> bindIGlobalScopeProvider() {
                 return ProblemGlobalScopeProvider.class;
         }
@@ -67,7 +75,7 @@ public class ProblemRuntimeModule extends AbstractProblemRuntimeModule {
 
         @Override
         public Class<? extends XtextResource> bindXtextResource() {
-                return DerivedStateAwareResource.class;
+                return ProblemResource.class;
         }
 
         // Method name follows Xtext convention.
diff --git a/subprojects/language/src/main/java/tools/refinery/language/linking/ProblemLinkingService.java b/subprojects/language/src/main/java/tools/refinery/language/linking/ProblemLinkingService.java
new file mode 100644
index 00000000..511ed420
--- /dev/null
+++ b/subprojects/language/src/main/java/tools/refinery/language/linking/ProblemLinkingService.java
@@ -0,0 +1,72 @@
+/*******************************************************************************
+ * Copyright (c) 2008, 2018 itemis AG (http://www.itemis.eu) and others.
+ * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-2.0.
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.language.linking;
+
+import com.google.inject.Inject;
+import org.apache.log4j.Logger;
+import org.eclipse.emf.ecore.EClass;
+import org.eclipse.emf.ecore.EObject;
+import org.eclipse.emf.ecore.EReference;
+import org.eclipse.xtext.linking.impl.DefaultLinkingService;
+import org.eclipse.xtext.linking.impl.IllegalNodeException;
+import org.eclipse.xtext.naming.IQualifiedNameConverter;
+import org.eclipse.xtext.naming.QualifiedName;
+import org.eclipse.xtext.nodemodel.INode;
+import org.eclipse.xtext.resource.IEObjectDescription;
+import org.eclipse.xtext.scoping.IScope;
+
+import java.util.*;
+
+public class ProblemLinkingService extends DefaultLinkingService {
+        @Inject
+        private IQualifiedNameConverter qualifiedNameConverter;
+
+        private static final Logger logger = Logger.getLogger(ProblemLinkingService.class);
+
+        @Override
+        public List<EObject> getLinkedObjects(EObject context, EReference ref, INode node) throws IllegalNodeException {
+                final EClass requiredType = ref.getEReferenceType();
+                if (requiredType == null) {
+                        return List.of();
+                }
+                final String crossRefString = getCrossRefNodeAsString(node);
+                if (crossRefString == null || crossRefString.isEmpty()) {
+                        return List.of();
+                }
+                if (logger.isDebugEnabled()) {
+                        logger.debug("before getLinkedObjects: node: '%s'".formatted(crossRefString));
+                }
+                final IScope scope = getScope(context, ref);
+                if (scope == null) {
+                        throw new AssertionError(("Scope provider must not return null for context %s, reference %s! Consider to" +
+                                        " return IScope.NULLSCOPE instead.").formatted(context, ref));
+                }
+                final QualifiedName qualifiedLinkName = qualifiedNameConverter.toQualifiedName(crossRefString);
+                final Iterator<IEObjectDescription> iterator = scope.getElements(qualifiedLinkName).iterator();
+                StringBuilder debug = null;
+                final Set<EObject> result = new LinkedHashSet<>();
+                if (logger.isDebugEnabled()) {
+                        debug = new StringBuilder()
+                                        .append("after getLinkedObjects: node: '")
+                                        .append(crossRefString)
+                                        .append("' result: ");
+                }
+                while (iterator.hasNext()) {
+                        var eObjectDescription = iterator.next();
+                        if (debug != null) {
+                                debug.append(eObjectDescription).append(", ");
+                        }
+                        result.add(eObjectDescription.getEObjectOrProxy());
+                }
+                if (debug != null) {
+                        logger.debug(debug);
+                }
+                return List.copyOf(result);
+        }
+}
diff --git a/subprojects/language/src/main/java/tools/refinery/language/resource/ProblemResource.java b/subprojects/language/src/main/java/tools/refinery/language/resource/ProblemResource.java
new file mode 100644
index 00000000..43239ffe
--- /dev/null
+++ b/subprojects/language/src/main/java/tools/refinery/language/resource/ProblemResource.java
@@ -0,0 +1,263 @@
+/*******************************************************************************
+ * Copyright (c) 2008, 2023 itemis AG (http://www.itemis.eu) and others.
+ * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/>
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-2.0.
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.language.resource;
+
+import com.google.inject.Inject;
+import org.apache.log4j.Logger;
+import org.eclipse.emf.ecore.EObject;
+import org.eclipse.emf.ecore.EReference;
+import org.eclipse.xtext.EcoreUtil2;
+import org.eclipse.xtext.diagnostics.DiagnosticMessage;
+import org.eclipse.xtext.diagnostics.Severity;
+import org.eclipse.xtext.linking.ILinkingDiagnosticMessageProvider;
+import org.eclipse.xtext.linking.impl.IllegalNodeException;
+import org.eclipse.xtext.linking.impl.XtextLinkingDiagnostic;
+import org.eclipse.xtext.linking.lazy.LazyLinkingResource;
+import org.eclipse.xtext.nodemodel.INode;
+import org.eclipse.xtext.resource.DerivedStateAwareResource;
+import org.eclipse.xtext.util.Triple;
+import org.jetbrains.annotations.Nullable;
+
+import java.util.Arrays;
+import java.util.List;
+import java.util.Objects;
+import java.util.Set;
+
+public class ProblemResource extends DerivedStateAwareResource {
+        private static final Logger log = Logger.getLogger(ProblemResource.class);
+
+        @Inject
+        private ILinkingDiagnosticMessageProvider.Extended linkingDiagnosticMessageProvider;
+
+        /**
+         * Our own version of this field, because the original is not accessible.
+         */
+        private int cyclicLinkingDetectionCounter = 0;
+
+        /**
+         * Tries to resolve a reference and emits a diagnostic if the reference is unresolvable or ambiguous.
+         * <p>
+         * This method was copied from {@link LazyLinkingResource#getEObject(String, Triple)}, but we modified it to also
+         * handle ambiguous references.
+         *
+         * @param uriFragment The URI fragment to resolve.
+         * @param triple      The linking triple.
+         * @return The resolved {@link EObject}.
+         * @throws AssertionError If the URI fragment is unresolvable.
+         */
+        @Override
+        protected EObject getEObject(String uriFragment, Triple<EObject, EReference, INode> triple) throws AssertionError {
+                cyclicLinkingDetectionCounter++;
+                if (cyclicLinkingDetectionCounter > cyclicLinkingDectectionCounterLimit && !resolving.add(triple)) {
+                        return handleCyclicResolution(triple);
+                }
+                try {
+                        Set<String> unresolvableProxies = getUnresolvableURIFragments();
+                        if (unresolvableProxies.contains(uriFragment)) {
+                                return null;
+                        }
+                        var result = doGetEObject(triple);
+                        if (result == null) {
+                                if (isUnresolveableProxyCacheable(triple)) {
+                                        unresolvableProxies.add(uriFragment);
+                                }
+                        } else {
+                                // remove previously added error markers, since everything should be fine now
+                                unresolvableProxies.remove(uriFragment);
+                        }
+                        return result;
+                } catch (IllegalNodeException e) {
+                        createAndAddDiagnostic(triple, e);
+                        return null;
+                } finally {
+                        if (cyclicLinkingDetectionCounter > cyclicLinkingDectectionCounterLimit) {
+                                resolving.remove(triple);
+                        }
+                        cyclicLinkingDetectionCounter--;
+                }
+        }
+
+        @Nullable
+        private EObject doGetEObject(Triple<EObject, EReference, INode> triple) {
+                EReference reference = triple.getSecond();
+                try {
+                        List<EObject> linkedObjects = getLinkingService().getLinkedObjects(triple.getFirst(), reference,
+                                        triple.getThird());
+                        if (linkedObjects.isEmpty()) {
+                                createAndAddDiagnostic(triple);
+                                return null;
+                        }
+                        if (linkedObjects.size() > 1) {
+                                createAndAddAmbiguousReferenceDiagnostic(triple);
+                                return null;
+                        }
+                        EObject result = linkedObjects.get(0);
+                        if (!EcoreUtil2.isAssignableFrom(reference.getEReferenceType(), result.eClass())) {
+                                log.error("An element of type %s is not assignable to the reference %s.%s".formatted(
+                                                result.getClass().getName(), reference.getEContainingClass().getName(), reference.getName()));
+                                createAndAddDiagnostic(triple);
+                                return null;
+                        }
+                        removeDiagnostic(triple);
+                        return result;
+                } catch (CyclicLinkingError e) {
+                        if (e.triple.equals(triple)) {
+                                log.error(e.getMessage(), e);
+                                createAndAddDiagnostic(triple);
+                                return null;
+                        } else {
+                                throw e;
+                        }
+                }
+        }
+
+        @Override
+        protected EObject handleCyclicResolution(Triple<EObject, EReference, INode> triple) throws AssertionError {
+                // Throw our own version of {@link LazyLinkingResource.CyclicLinkingException}.
+                throw new CyclicLinkingError("Cyclic resolution of lazy links : %s in resource '%s'.".formatted(
+                                getReferences(triple, resolving), getURI()), triple);
+        }
+
+        @Override
+        protected void createAndAddDiagnostic(Triple<EObject, EReference, INode> triple) {
+                if (isValidationDisabled()) {
+                        return;
+                }
+                DiagnosticMessage message = createDiagnosticMessage(triple);
+                addOrReplaceDiagnostic(triple, message);
+        }
+
+        @Override
+        protected void createAndAddDiagnostic(Triple<EObject, EReference, INode> triple, IllegalNodeException ex) {
+                if (isValidationDisabled()) {
+                        return;
+                }
+                ILinkingDiagnosticMessageProvider.ILinkingDiagnosticContext context = createDiagnosticMessageContext(triple);
+                DiagnosticMessage message = linkingDiagnosticMessageProvider.getIllegalNodeMessage(context, ex);
+                addOrReplaceDiagnostic(triple, message);
+        }
+
+        protected void createAndAddAmbiguousReferenceDiagnostic(Triple<EObject, EReference, INode> triple) {
+                if (isValidationDisabled()) {
+                        return;
+                }
+                var context = createDiagnosticMessageContext(triple);
+                var typeName = context.getReference().getEReferenceType().getName();
+                String linkText = "";
+                try {
+                        linkText = context.getLinkText();
+                } catch (IllegalNodeException e) {
+                        linkText = e.getNode().getText();
+                }
+                var messageString = "Ambiguous reference to %s '%s'.".formatted(typeName, linkText);
+                var message = new DiagnosticMessage(messageString, Severity.ERROR,
+                                org.eclipse.xtext.diagnostics.Diagnostic.LINKING_DIAGNOSTIC);
+                addOrReplaceDiagnostic(triple, message);
+        }
+
+        /**
+         * Adds a diagnostic message while maintaining the invariant that at most one
+         * {@link ProblemResourceLinkingDiagnostic} is added to the {@link #getErrors()} list.
+         *
+         * @param triple  The triple to add the diagnostic for.
+         * @param message The diagnostic message. Must have {@link Severity#ERROR}.
+         */
+        protected void addOrReplaceDiagnostic(Triple<EObject, EReference, INode> triple, DiagnosticMessage message) {
+                if (message == null) {
+                        return;
+                }
+                if (message.getSeverity() != Severity.ERROR) {
+                        throw new IllegalArgumentException("Only linking diagnostics of ERROR severity are supported");
+                }
+                var list = getDiagnosticList(message);
+                var iterator = list.iterator();
+                while (iterator.hasNext()) {
+                        var diagnostic = iterator.next();
+                        if (diagnostic instanceof ProblemResourceLinkingDiagnostic linkingDiagnostic &&
+                                        linkingDiagnostic.matchesNode(triple.getThird())) {
+                                if (linkingDiagnostic.matchesMessage(message)) {
+                                        return;
+                                }
+                                iterator.remove();
+                                break;
+                        }
+                }
+                var diagnostic = createDiagnostic(triple, message);
+                list.add(diagnostic);
+        }
+
+        /**
+         * Removes the {@link ProblemResourceLinkingDiagnostic} corresponding to the given node, if prevesent, from the
+         * {@link #getErrors()} list.
+         *
+         * @param triple The triple to add the diagnostic for.
+         */
+        @Override
+        protected void removeDiagnostic(Triple<EObject, EReference, INode> triple) {
+                if (getErrors().isEmpty()) {
+                        return;
+                }
+                var list = getErrors();
+                if (list.isEmpty()) {
+                        return;
+                }
+                var iterator = list.iterator();
+                while (iterator.hasNext()) {
+                        var diagnostic = iterator.next();
+                        if (diagnostic instanceof ProblemResourceLinkingDiagnostic linkingDiagnostic &&
+                                        linkingDiagnostic.matchesNode(triple.getThird())) {
+                                iterator.remove();
+                                return;
+                        }
+                }
+        }
+
+        @Override
+        protected Diagnostic createDiagnostic(Triple<EObject, EReference, INode> triple, DiagnosticMessage message) {
+                return new ProblemResourceLinkingDiagnostic(triple.getThird(), message.getMessage(),
+                                message.getIssueCode(), message.getIssueData());
+        }
+
+        /**
+         * Our own version of {@link LazyLinkingResource.CyclicLinkingException}, because the {@code tripe} field in the
+         * original one is not accessible.
+         * <p>
+         * Renamed from {@code CyclicLinkingException} to satisfy naming conventions enforced by Sonar.
+         */
+        public static final class CyclicLinkingError extends AssertionError {
+                private final transient Triple<EObject, EReference, INode> triple;
+
+                private CyclicLinkingError(Object detailMessage, Triple<EObject, EReference, INode> triple) {
+                        super(detailMessage);
+                        this.triple = triple;
+                }
+        }
+
+        /**
+         * Marks all diagnostics inserted by {@link ProblemResource} with a common superclass so that they can
+         * later be removed.
+         * <p>
+         * We have to inherit from {@link XtextLinkingDiagnostic} to access the protected function {@link #getNode()}.
+         */
+        protected static class ProblemResourceLinkingDiagnostic extends XtextLinkingDiagnostic {
+                public ProblemResourceLinkingDiagnostic(INode node, String message, String code, String... data) {
+                        super(node, message, code, data);
+                }
+
+                public boolean matchesNode(INode node) {
+                        return Objects.equals(getNode(), node);
+                }
+
+                public boolean matchesMessage(DiagnosticMessage message) {
+                        return Objects.equals(getMessage(), message.getMessage()) &&
+                                        Objects.equals(getCode(), message.getIssueCode()) &&
+                                        Arrays.equals(getData(), message.getIssueData());
+                }
+        }
+}
diff --git a/subprojects/language/src/main/java/tools/refinery/language/validation/ProblemValidator.java b/subprojects/language/src/main/java/tools/refinery/language/validation/ProblemValidator.java
index 88d50c5b..56a934cf 100644
--- a/subprojects/language/src/main/java/tools/refinery/language/validation/ProblemValidator.java
+++ b/subprojects/language/src/main/java/tools/refinery/language/validation/ProblemValidator.java
@@ -55,7 +55,7 @@ public class ProblemValidator extends AbstractProblemValidator {
                 var variableOrNode = expr.getVariableOrNode();
                 if (variableOrNode instanceof Node node && !ProblemUtil.isIndividualNode(node)) {
                         var name = node.getName();
-                        var message = ("Only individual nodes can be referenced in predicates. " +
+                        var message = ("Only individuals can be referenced in predicates. " +
                                         "Mark '%s' as individual with the declaration 'indiv %s.'").formatted(name, name);
                         error(message, expr, ProblemPackage.Literals.VARIABLE_OR_NODE_EXPR__VARIABLE_OR_NODE,
                                         INSIGNIFICANT_INDEX, NON_INDIVIDUAL_NODE_ISSUE);
diff --git a/subprojects/language/src/test/java/tools/refinery/language/tests/linking/AmbiguousReferenceTest.java b/subprojects/language/src/test/java/tools/refinery/language/tests/linking/AmbiguousReferenceTest.java
new file mode 100644
index 00000000..b1b24ef3
--- /dev/null
+++ b/subprojects/language/src/test/java/tools/refinery/language/tests/linking/AmbiguousReferenceTest.java
@@ -0,0 +1,94 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.language.tests.linking;
+
+
+import com.google.inject.Inject;
+import org.eclipse.xtext.testing.InjectWith;
+import org.eclipse.xtext.testing.extensions.InjectionExtension;
+import org.junit.jupiter.api.extension.ExtendWith;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
+import tools.refinery.language.model.tests.utils.ProblemParseHelper;
+import tools.refinery.language.tests.ProblemInjectorProvider;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.*;
+
+@ExtendWith(InjectionExtension.class)
+@InjectWith(ProblemInjectorProvider.class)
+class AmbiguousReferenceTest {
+        @Inject
+        private ProblemParseHelper parseHelper;
+
+        @ParameterizedTest
+        @ValueSource(strings = {"""
+                        class Foo {
+                                contains Quux quux
+                        }
+
+                        class Quux.
+
+                        quux(f, q).
+                        """, """
+                        class Foo {
+                                contains Quux quux
+                        }
+
+                        class Quux.
+
+                        pred example(Foo f, Quux q) <-> quux(f, q).
+                        """, """
+                        class Foo {
+                                contains Quux quux opposite foo
+                        }
+
+                        class Bar {
+                                contains Quux quux opposite bar
+                        }
+
+                        class Quux {
+                                container Foo foo opposite quux
+                                container Bar bar opposite quux
+                        }
+                        """})
+        void unambiguousReferenceTest(String text) {
+                var problem = parseHelper.parse(text);
+                assertThat(problem.errors(), empty());
+        }
+
+        @ParameterizedTest
+        @ValueSource(strings = {"""
+                        class Foo {
+                                contains Quux quux
+                        }
+
+                        class Bar {
+                                contains Quux quux
+                        }
+
+                        class Quux.
+
+                        quux(f, q).
+                        """, """
+                        class Foo {
+                                contains Quux quux
+                        }
+
+                        class Bar {
+                                contains Quux quux
+                        }
+
+                        class Quux.
+
+                        pred example(Foo f, Quuq q) <-> quux(f, q).
+                        """})
+        void ambiguousReferenceTest(String text) {
+                var problem = parseHelper.parse(text);
+                assertThat(problem.errors(), hasItem(hasProperty("message", stringContainsInOrder(
+                                "Ambiguous reference", "'quux'"))));
+        }
+}