3 files changed, 399 insertions, 0 deletions

diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/timeless/RecursiveCommunicationGroup.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/timeless/RecursiveCommunicationGroup.java
new file mode 100644
index 00000000..d8260384
--- /dev/null
+++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/timeless/RecursiveCommunicationGroup.java
@@ -0,0 +1,164 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2019, Tamas Szabo, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.rete.network.communication.timeless;
+
+import java.util.Collection;
+import java.util.Collections;
+import java.util.EnumMap;
+import java.util.LinkedHashSet;
+import java.util.Map;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
+import tools.refinery.viatra.runtime.rete.network.Node;
+import tools.refinery.viatra.runtime.rete.network.RederivableNode;
+import tools.refinery.viatra.runtime.rete.network.communication.CommunicationGroup;
+import tools.refinery.viatra.runtime.rete.network.communication.CommunicationTracker;
+import tools.refinery.viatra.runtime.rete.network.communication.MessageSelector;
+import tools.refinery.viatra.runtime.rete.network.communication.PhasedSelector;
+import tools.refinery.viatra.runtime.rete.network.mailbox.Mailbox;
+
+/**
+ * A communication group representing either a single node where the
+ * node is a monotonicity aware one or a set of nodes that form an SCC. 
+ * 
+ * @author Tamas Szabo
+ * @since 2.4
+ */
+public class RecursiveCommunicationGroup extends CommunicationGroup {
+
+    private final Set<Mailbox> antiMonotoneMailboxes;
+    private final Set<Mailbox> monotoneMailboxes;
+    private final Set<Mailbox> defaultMailboxes;
+    private final Set<RederivableNode> rederivables;
+    private boolean currentlyDelivering;
+
+    /**
+     * @since 1.7
+     */
+    public RecursiveCommunicationGroup(final CommunicationTracker tracker, final Node representative, final int identifier) {
+        super(tracker, representative, identifier);
+        this.antiMonotoneMailboxes = CollectionsFactory.createSet();
+        this.monotoneMailboxes = CollectionsFactory.createSet();
+        this.defaultMailboxes = CollectionsFactory.createSet();
+        this.rederivables = new LinkedHashSet<RederivableNode>();
+        this.currentlyDelivering = false;
+    }
+
+    @Override
+    public void deliverMessages() {
+        this.currentlyDelivering = true;
+        
+        // ANTI-MONOTONE PHASE
+        while (!this.antiMonotoneMailboxes.isEmpty() || !this.defaultMailboxes.isEmpty()) {
+            while (!this.antiMonotoneMailboxes.isEmpty()) {
+                final Mailbox mailbox = this.antiMonotoneMailboxes.iterator().next();
+                this.antiMonotoneMailboxes.remove(mailbox);
+                mailbox.deliverAll(PhasedSelector.ANTI_MONOTONE);
+            }
+            while (!this.defaultMailboxes.isEmpty()) {
+                final Mailbox mailbox = this.defaultMailboxes.iterator().next();
+                this.defaultMailboxes.remove(mailbox);
+                mailbox.deliverAll(PhasedSelector.DEFAULT);
+            }
+        }
+
+        // REDERIVE PHASE
+        while (!this.rederivables.isEmpty()) {
+            // re-derivable nodes take care of their unregistration!!
+            final RederivableNode node = this.rederivables.iterator().next();
+            node.rederiveOne();
+        }
+
+        // MONOTONE PHASE
+        while (!this.monotoneMailboxes.isEmpty() || !this.defaultMailboxes.isEmpty()) {
+            while (!this.monotoneMailboxes.isEmpty()) {
+                final Mailbox mailbox = this.monotoneMailboxes.iterator().next();
+                this.monotoneMailboxes.remove(mailbox);
+                mailbox.deliverAll(PhasedSelector.MONOTONE);
+            }
+            while (!this.defaultMailboxes.isEmpty()) {
+                final Mailbox mailbox = this.defaultMailboxes.iterator().next();
+                this.defaultMailboxes.remove(mailbox);
+                mailbox.deliverAll(PhasedSelector.DEFAULT);
+            }
+        }
+        
+        this.currentlyDelivering = false;
+    }
+
+    @Override
+    public boolean isEmpty() {
+        return this.rederivables.isEmpty() && this.antiMonotoneMailboxes.isEmpty()
+                && this.monotoneMailboxes.isEmpty() && this.defaultMailboxes.isEmpty();
+    }
+
+    @Override
+    public void notifyHasMessage(final Mailbox mailbox, final MessageSelector kind) {
+        final Collection<Mailbox> mailboxes = getMailboxContainer(kind);
+        mailboxes.add(mailbox);
+        if (!this.isEnqueued && !this.currentlyDelivering) {
+            this.tracker.activateUnenqueued(this);
+        }
+    }
+
+    @Override
+    public void notifyLostAllMessages(final Mailbox mailbox, final MessageSelector kind) {
+        final Collection<Mailbox> mailboxes = getMailboxContainer(kind);
+        mailboxes.remove(mailbox);
+        if (isEmpty()) {
+            this.tracker.deactivate(this);
+        }
+    }
+
+    private Collection<Mailbox> getMailboxContainer(final MessageSelector kind) {
+        if (kind == PhasedSelector.ANTI_MONOTONE) {
+            return this.antiMonotoneMailboxes;
+        } else if (kind == PhasedSelector.MONOTONE) {
+            return this.monotoneMailboxes;
+        } else if (kind == PhasedSelector.DEFAULT) {
+            return this.defaultMailboxes;
+        } else {
+            throw new IllegalArgumentException(UNSUPPORTED_MESSAGE_KIND + kind);
+        }
+    }
+
+    public void addRederivable(final RederivableNode node) {
+        this.rederivables.add(node);
+        if (!this.isEnqueued) {
+            this.tracker.activateUnenqueued(this);
+        }
+    }
+
+    public void removeRederivable(final RederivableNode node) {
+        this.rederivables.remove(node);
+        if (isEmpty()) {
+            this.tracker.deactivate(this);
+        }
+    }
+
+    public Collection<RederivableNode> getRederivables() {
+        return this.rederivables;
+    }
+
+    @Override
+    public Map<MessageSelector, Collection<Mailbox>> getMailboxes() {
+        Map<PhasedSelector, Collection<Mailbox>> map = new EnumMap<>(PhasedSelector.class);
+        map.put(PhasedSelector.ANTI_MONOTONE, antiMonotoneMailboxes);
+        map.put(PhasedSelector.MONOTONE, monotoneMailboxes);
+        map.put(PhasedSelector.DEFAULT, defaultMailboxes);
+        return Collections.unmodifiableMap(map);
+    }
+    
+    @Override
+    public boolean isRecursive() {
+        return true;
+    }
+    
+}
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/timeless/SingletonCommunicationGroup.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/timeless/SingletonCommunicationGroup.java
new file mode 100644
index 00000000..c51c7dbf
--- /dev/null
+++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/timeless/SingletonCommunicationGroup.java
@@ -0,0 +1,86 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2019, Tamas Szabo, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.rete.network.communication.timeless;
+
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Map;
+
+import tools.refinery.viatra.runtime.rete.network.Node;
+import tools.refinery.viatra.runtime.rete.network.communication.CommunicationGroup;
+import tools.refinery.viatra.runtime.rete.network.communication.CommunicationTracker;
+import tools.refinery.viatra.runtime.rete.network.communication.MessageSelector;
+import tools.refinery.viatra.runtime.rete.network.communication.PhasedSelector;
+import tools.refinery.viatra.runtime.rete.network.mailbox.Mailbox;
+
+/**
+ * A communication group containing only a single node with a single default
+ * mailbox.
+ * 
+ * @author Tamas Szabo
+ * @since 1.6
+ */
+public class SingletonCommunicationGroup extends CommunicationGroup {
+    
+    private Mailbox mailbox;
+
+    /**
+     * @since 1.7
+     */
+    public SingletonCommunicationGroup(final CommunicationTracker tracker, final Node representative, final int identifier) {
+        super(tracker, representative, identifier);
+    }
+
+    @Override
+    public void deliverMessages() {
+        this.mailbox.deliverAll(PhasedSelector.DEFAULT);
+    }
+
+    @Override
+    public boolean isEmpty() {
+        return this.mailbox == null;
+    }
+
+    @Override
+    public void notifyHasMessage(final Mailbox mailbox, final MessageSelector kind) {
+        if (kind == PhasedSelector.DEFAULT) {
+            this.mailbox = mailbox;
+            if (!this.isEnqueued) {
+                this.tracker.activateUnenqueued(this);
+            }
+        } else {
+            throw new IllegalArgumentException(UNSUPPORTED_MESSAGE_KIND + kind);
+        }
+    }
+
+    @Override
+    public void notifyLostAllMessages(final Mailbox mailbox, final MessageSelector kind) {
+        if (kind == PhasedSelector.DEFAULT) {
+            this.mailbox = null;
+            this.tracker.deactivate(this);
+        } else {
+            throw new IllegalArgumentException(UNSUPPORTED_MESSAGE_KIND + kind);
+        }
+    }
+
+    @Override
+    public Map<MessageSelector, Collection<Mailbox>> getMailboxes() {
+        if (mailbox != null) {
+            return Collections.singletonMap(PhasedSelector.DEFAULT, Collections.singleton(mailbox));
+        } else {
+            return Collections.emptyMap();
+        }
+    }
+
+    @Override
+    public boolean isRecursive() {
+        return false;
+    }
+    
+}
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/timeless/TimelessCommunicationTracker.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/timeless/TimelessCommunicationTracker.java
new file mode 100644
index 00000000..1c18c1cd
--- /dev/null
+++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/network/communication/timeless/TimelessCommunicationTracker.java
@@ -0,0 +1,149 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2019, Tamas Szabo, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+package tools.refinery.viatra.runtime.rete.network.communication.timeless;
+
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Set;
+import java.util.Map.Entry;
+
+import tools.refinery.viatra.runtime.rete.index.DualInputNode;
+import tools.refinery.viatra.runtime.rete.index.Indexer;
+import tools.refinery.viatra.runtime.rete.index.IndexerListener;
+import tools.refinery.viatra.runtime.rete.index.IterableIndexer;
+import tools.refinery.viatra.runtime.rete.network.Node;
+import tools.refinery.viatra.runtime.rete.network.Receiver;
+import tools.refinery.viatra.runtime.rete.network.RederivableNode;
+import tools.refinery.viatra.runtime.rete.network.communication.CommunicationGroup;
+import tools.refinery.viatra.runtime.rete.network.communication.CommunicationTracker;
+import tools.refinery.viatra.runtime.rete.network.communication.MessageSelector;
+import tools.refinery.viatra.runtime.rete.network.mailbox.Mailbox;
+import tools.refinery.viatra.runtime.rete.network.mailbox.timeless.BehaviorChangingMailbox;
+
+/**
+ * Timeless implementation of the communication tracker.
+ * 
+ * @author Tamas Szabo
+ * @since 2.2
+ */
+public class TimelessCommunicationTracker extends CommunicationTracker {
+
+    @Override
+    protected CommunicationGroup createGroup(Node representative, int index) {
+        final boolean isSingleton = this.sccInformationProvider.sccs.getPartition(representative).size() == 1;
+        final boolean isReceiver = representative instanceof Receiver;
+        final boolean isPosetIndifferent = isReceiver
+                && ((Receiver) representative).getMailbox() instanceof BehaviorChangingMailbox;
+        final boolean isSingletonInDRedMode = isSingleton && (representative instanceof RederivableNode)
+                && ((RederivableNode) representative).isInDRedMode();
+
+        CommunicationGroup group = null;
+        // we can only use a singleton group iff
+        // (1) the SCC has one node AND
+        // (2) either we have a poset-indifferent mailbox OR the node is not even a receiver AND
+        // (3) the node does not run in DRed mode in a singleton group
+        if (isSingleton && (isPosetIndifferent || !isReceiver) && !isSingletonInDRedMode) {
+            group = new SingletonCommunicationGroup(this, representative, index);
+        } else {
+            group = new RecursiveCommunicationGroup(this, representative, index);
+        }
+
+        return group;
+    }
+
+    @Override
+    protected void reconstructQueueContents(final Set<CommunicationGroup> oldActiveGroups) {
+        for (final CommunicationGroup oldGroup : oldActiveGroups) {
+            for (final Entry<MessageSelector, Collection<Mailbox>> entry : oldGroup.getMailboxes().entrySet()) {
+                for (final Mailbox mailbox : entry.getValue()) {
+                    final CommunicationGroup newGroup = this.groupMap.get(mailbox.getReceiver());
+                    newGroup.notifyHasMessage(mailbox, entry.getKey());
+                }
+            }
+
+            if (oldGroup instanceof RecursiveCommunicationGroup) {
+                for (final RederivableNode node : ((RecursiveCommunicationGroup) oldGroup).getRederivables()) {
+                    final CommunicationGroup newGroup = this.groupMap.get(node);
+                    if (!(newGroup instanceof RecursiveCommunicationGroup)) {
+                        throw new IllegalStateException("The new group must also be recursive! " + newGroup);
+                    }
+                    ((RecursiveCommunicationGroup) newGroup).addRederivable(node);
+                }
+            }
+        }
+    }
+
+    @Override
+    public Mailbox proxifyMailbox(final Node requester, final Mailbox original) {
+        return original;
+    }
+
+    @Override
+    public IndexerListener proxifyIndexerListener(final Node requester, final IndexerListener original) {
+        return original;
+    }
+
+    @Override
+    protected void postProcessNode(final Node node) {
+        if (node instanceof Receiver) {
+            final Mailbox mailbox = ((Receiver) node).getMailbox();
+            if (mailbox instanceof BehaviorChangingMailbox) {
+                final CommunicationGroup group = this.groupMap.get(node);
+                final Set<Node> sccNodes = this.sccInformationProvider.sccs.getPartition(node);
+                // a default mailbox must split its messages iff
+                // (1) its receiver is in a recursive group and
+                final boolean c1 = group.isRecursive();
+                // (2) its receiver is at the SCC boundary of that group
+                final boolean c2 = isAtSCCBoundary(node);
+                // (3) its group consists of more than one node
+                final boolean c3 = sccNodes.size() > 1;
+                ((BehaviorChangingMailbox) mailbox).setSplitFlag(c1 && c2 && c3);
+            }
+        }
+    }
+    
+    @Override
+    protected void postProcessGroup(final CommunicationGroup group) {
+        
+    }
+
+    /**
+     * @since 2.0
+     */
+    private boolean isAtSCCBoundary(final Node node) {
+        final CommunicationGroup ownGroup = this.groupMap.get(node);
+        assert ownGroup != null;
+        for (final Node source : this.dependencyGraph.getSourceNodes(node).distinctValues()) {
+            final Set<Node> sourcesToCheck = new HashSet<Node>();
+            sourcesToCheck.add(source);
+            // DualInputNodes must be checked additionally because they do not use a mailbox directly.
+            // It can happen that their indexers actually belong to other SCCs.
+            if (source instanceof DualInputNode) {
+                final DualInputNode dualInput = (DualInputNode) source;
+                final IterableIndexer primarySlot = dualInput.getPrimarySlot();
+                if (primarySlot != null) {
+                    sourcesToCheck.add(primarySlot.getActiveNode());
+                }
+                final Indexer secondarySlot = dualInput.getSecondarySlot();
+                if (secondarySlot != null) {
+                    sourcesToCheck.add(secondarySlot.getActiveNode());
+                }
+            }
+            for (final Node current : sourcesToCheck) {
+                final CommunicationGroup otherGroup = this.groupMap.get(current);
+                assert otherGroup != null;
+                if (!ownGroup.equals(otherGroup)) {
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+}