diff options
author | 2023-08-19 03:29:34 +0200 | |
---|---|---|
committer | 2023-08-19 03:29:34 +0200 | |
commit | 22b3b72ff9b978de50a2823739940b34f9fe8dfa (patch) | |
tree | 74695bdae60181e47303031ad91e1e707a98a287 /subprojects/viatra-runtime-localsearch | |
parent | chore: mark modified VIATRA files (diff) | |
download | refinery-22b3b72ff9b978de50a2823739940b34f9fe8dfa.tar.gz refinery-22b3b72ff9b978de50a2823739940b34f9fe8dfa.tar.zst refinery-22b3b72ff9b978de50a2823739940b34f9fe8dfa.zip |
refactor: apply local search fixes to VIATRA
Diffstat (limited to 'subprojects/viatra-runtime-localsearch')
2 files changed, 37 insertions, 33 deletions
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/operations/ExtendOperationExecutor.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/operations/ExtendOperationExecutor.java index 01179118..a72c30dd 100644 --- a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/operations/ExtendOperationExecutor.java +++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/operations/ExtendOperationExecutor.java | |||
@@ -1,19 +1,20 @@ | |||
1 | /******************************************************************************* | 1 | /******************************************************************************* |
2 | * Copyright (c) 2010-2013, Zoltan Ujhelyi, Akos Horvath, Istvan Rath and Daniel Varro | 2 | * Copyright (c) 2010-2013, Zoltan Ujhelyi, Akos Horvath, Istvan Rath and Daniel Varro |
3 | * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * This program and the accompanying materials are made available under the | 4 | * This program and the accompanying materials are made available under the |
4 | * terms of the Eclipse Public License v. 2.0 which is available at | 5 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 6 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 7 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 8 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 9 | *******************************************************************************/ |
9 | package tools.refinery.viatra.runtime.localsearch.operations; | 10 | package tools.refinery.viatra.runtime.localsearch.operations; |
10 | 11 | ||
11 | import java.util.Iterator; | ||
12 | |||
13 | import tools.refinery.viatra.runtime.localsearch.MatchingFrame; | 12 | import tools.refinery.viatra.runtime.localsearch.MatchingFrame; |
14 | import tools.refinery.viatra.runtime.localsearch.matcher.ISearchContext; | 13 | import tools.refinery.viatra.runtime.localsearch.matcher.ISearchContext; |
15 | import tools.refinery.viatra.runtime.localsearch.operations.ISearchOperation.ISearchOperationExecutor; | 14 | import tools.refinery.viatra.runtime.localsearch.operations.ISearchOperation.ISearchOperationExecutor; |
16 | 15 | ||
16 | import java.util.Iterator; | ||
17 | |||
17 | /** | 18 | /** |
18 | * An operation that can be used to enumerate all possible values for a single position based on a constraint | 19 | * An operation that can be used to enumerate all possible values for a single position based on a constraint |
19 | * @author Zoltan Ujhelyi, Akos Horvath | 20 | * @author Zoltan Ujhelyi, Akos Horvath |
@@ -31,42 +32,46 @@ public abstract class ExtendOperationExecutor<T> implements ISearchOperationExec | |||
31 | protected abstract Iterator<? extends T> getIterator(MatchingFrame frame, ISearchContext context); | 32 | protected abstract Iterator<? extends T> getIterator(MatchingFrame frame, ISearchContext context); |
32 | /** | 33 | /** |
33 | * Updates the frame with the next element of the iterator. Called during {@link #execute(MatchingFrame, ISearchContext)}. | 34 | * Updates the frame with the next element of the iterator. Called during {@link #execute(MatchingFrame, ISearchContext)}. |
34 | * | 35 | * |
35 | * @return true if the update is successful or false otherwise; in case of false is returned, the next element should be taken from the iterator. | 36 | * @return true if the update is successful or false otherwise; in case of false is returned, the next element should be taken from the iterator. |
36 | * @since 2.0 | 37 | * @since 2.0 |
37 | */ | 38 | */ |
38 | protected abstract boolean fillInValue(T newValue, MatchingFrame frame, ISearchContext context); | 39 | protected abstract boolean fillInValue(T newValue, MatchingFrame frame, ISearchContext context); |
39 | 40 | ||
40 | /** | 41 | /** |
41 | * Restores the frame to the state before {@link #fillInValue(Object, MatchingFrame, ISearchContext)}. Called during | 42 | * Restores the frame to the state before {@link #fillInValue(Object, MatchingFrame, ISearchContext)}. Called during |
42 | * {@link #onBacktrack(MatchingFrame, ISearchContext)}. | 43 | * {@link #onBacktrack(MatchingFrame, ISearchContext)}. |
43 | * | 44 | * |
44 | * @since 2.0 | 45 | * @since 2.0 |
45 | */ | 46 | */ |
46 | protected abstract void cleanup(MatchingFrame frame, ISearchContext context); | 47 | protected abstract void cleanup(MatchingFrame frame, ISearchContext context); |
47 | 48 | ||
48 | @Override | 49 | @Override |
49 | public void onInitialize(MatchingFrame frame, ISearchContext context) { | 50 | public void onInitialize(MatchingFrame frame, ISearchContext context) { |
50 | it = getIterator(frame, context); | 51 | it = getIterator(frame, context); |
51 | } | 52 | } |
52 | 53 | ||
53 | @Override | 54 | @Override |
54 | public void onBacktrack(MatchingFrame frame, ISearchContext context) { | 55 | public void onBacktrack(MatchingFrame frame, ISearchContext context) { |
55 | it = null; | 56 | it = null; |
56 | 57 | ||
57 | } | 58 | } |
58 | 59 | ||
59 | @Override | 60 | /** |
60 | public boolean execute(MatchingFrame frame, ISearchContext context) { | 61 | * Fixed version that handles failed unification of variables correctly. |
61 | if (it.hasNext()){ | 62 | * @param frame The matching frame to extend. |
62 | T newValue = it.next(); | 63 | * @param context The search context. |
63 | while(!fillInValue(newValue, frame, context) && it.hasNext()){ | 64 | * @return {@code true} if an extension was found, {@code false} otherwise. |
64 | newValue = it.next(); | 65 | */ |
65 | } | 66 | @Override |
66 | return true; | 67 | public boolean execute(MatchingFrame frame, ISearchContext context) { |
67 | } else { | 68 | while (it.hasNext()) { |
68 | return false; | 69 | var newValue = it.next(); |
69 | } | 70 | if (fillInValue(newValue, frame, context)) { |
70 | } | 71 | return true; |
71 | 72 | } | |
73 | } | ||
74 | return false; | ||
75 | } | ||
76 | |||
72 | } | 77 | } |
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/compiler/GenericOperationCompiler.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/compiler/GenericOperationCompiler.java index 606048b7..d86982e9 100644 --- a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/compiler/GenericOperationCompiler.java +++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/compiler/GenericOperationCompiler.java | |||
@@ -1,19 +1,14 @@ | |||
1 | /******************************************************************************* | 1 | /******************************************************************************* |
2 | * Copyright (c) 2010-2017, Zoltan Ujhelyi, IncQuery Labs Ltd. | 2 | * Copyright (c) 2010-2017, Zoltan Ujhelyi, IncQuery Labs Ltd. |
3 | * Copyright (c) 2023 The Refinery Authors <https://refinery.tools/> | ||
3 | * This program and the accompanying materials are made available under the | 4 | * This program and the accompanying materials are made available under the |
4 | * terms of the Eclipse Public License v. 2.0 which is available at | 5 | * terms of the Eclipse Public License v. 2.0 which is available at |
5 | * http://www.eclipse.org/legal/epl-v20.html. | 6 | * http://www.eclipse.org/legal/epl-v20.html. |
6 | * | 7 | * |
7 | * SPDX-License-Identifier: EPL-2.0 | 8 | * SPDX-License-Identifier: EPL-2.0 |
8 | *******************************************************************************/ | 9 | *******************************************************************************/ |
9 | package tools.refinery.viatra.runtime.localsearch.planner.compiler; | 10 | package tools.refinery.viatra.runtime.localsearch.planner.compiler; |
10 | 11 | ||
11 | import java.util.ArrayList; | ||
12 | import java.util.HashSet; | ||
13 | import java.util.List; | ||
14 | import java.util.Map; | ||
15 | import java.util.Set; | ||
16 | |||
17 | import tools.refinery.viatra.runtime.localsearch.operations.generic.GenericTypeCheck; | 12 | import tools.refinery.viatra.runtime.localsearch.operations.generic.GenericTypeCheck; |
18 | import tools.refinery.viatra.runtime.localsearch.operations.generic.GenericTypeExtend; | 13 | import tools.refinery.viatra.runtime.localsearch.operations.generic.GenericTypeExtend; |
19 | import tools.refinery.viatra.runtime.localsearch.operations.generic.GenericTypeExtendSingleValue; | 14 | import tools.refinery.viatra.runtime.localsearch.operations.generic.GenericTypeExtendSingleValue; |
@@ -25,6 +20,8 @@ import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.TypeConst | |||
25 | import tools.refinery.viatra.runtime.matchers.tuple.Tuple; | 20 | import tools.refinery.viatra.runtime.matchers.tuple.Tuple; |
26 | import tools.refinery.viatra.runtime.matchers.tuple.TupleMask; | 21 | import tools.refinery.viatra.runtime.matchers.tuple.TupleMask; |
27 | 22 | ||
23 | import java.util.*; | ||
24 | |||
28 | /** | 25 | /** |
29 | * @author Zoltan Ujhelyi | 26 | * @author Zoltan Ujhelyi |
30 | * @since 1.7 | 27 | * @since 1.7 |
@@ -46,9 +43,9 @@ public class GenericOperationCompiler extends AbstractOperationCompiler { | |||
46 | positions[i] = variableMapping.get(variable); | 43 | positions[i] = variableMapping.get(variable); |
47 | } | 44 | } |
48 | operations.add(new GenericTypeCheck(inputKey, positions, TupleMask.fromSelectedIndices(variableMapping.size(), positions))); | 45 | operations.add(new GenericTypeCheck(inputKey, positions, TupleMask.fromSelectedIndices(variableMapping.size(), positions))); |
49 | 46 | ||
50 | } | 47 | } |
51 | 48 | ||
52 | @Override | 49 | @Override |
53 | protected void createCheck(TypeConstraint typeConstraint, Map<PVariable, Integer> variableMapping) { | 50 | protected void createCheck(TypeConstraint typeConstraint, Map<PVariable, Integer> variableMapping) { |
54 | IInputKey inputKey = typeConstraint.getSupplierKey(); | 51 | IInputKey inputKey = typeConstraint.getSupplierKey(); |
@@ -60,7 +57,7 @@ public class GenericOperationCompiler extends AbstractOperationCompiler { | |||
60 | } | 57 | } |
61 | operations.add(new GenericTypeCheck(inputKey, positions, TupleMask.fromSelectedIndices(variableMapping.size(), positions))); | 58 | operations.add(new GenericTypeCheck(inputKey, positions, TupleMask.fromSelectedIndices(variableMapping.size(), positions))); |
62 | } | 59 | } |
63 | 60 | ||
64 | @Override | 61 | @Override |
65 | protected void createUnaryTypeCheck(IInputKey inputKey, int position) { | 62 | protected void createUnaryTypeCheck(IInputKey inputKey, int position) { |
66 | int[] positions = new int[] {position}; | 63 | int[] positions = new int[] {position}; |
@@ -71,7 +68,7 @@ public class GenericOperationCompiler extends AbstractOperationCompiler { | |||
71 | protected void createExtend(TypeConstraint typeConstraint, Map<PVariable, Integer> variableMapping) { | 68 | protected void createExtend(TypeConstraint typeConstraint, Map<PVariable, Integer> variableMapping) { |
72 | IInputKey inputKey = typeConstraint.getSupplierKey(); | 69 | IInputKey inputKey = typeConstraint.getSupplierKey(); |
73 | Tuple tuple = typeConstraint.getVariablesTuple(); | 70 | Tuple tuple = typeConstraint.getVariablesTuple(); |
74 | 71 | ||
75 | int[] positions = new int[tuple.getSize()]; | 72 | int[] positions = new int[tuple.getSize()]; |
76 | List<Integer> boundVariableIndices = new ArrayList<>(); | 73 | List<Integer> boundVariableIndices = new ArrayList<>(); |
77 | List<Integer> boundVariables = new ArrayList<>(); | 74 | List<Integer> boundVariables = new ArrayList<>(); |
@@ -89,7 +86,9 @@ public class GenericOperationCompiler extends AbstractOperationCompiler { | |||
89 | } | 86 | } |
90 | TupleMask indexerMask = TupleMask.fromSelectedIndices(inputKey.getArity(), boundVariableIndices); | 87 | TupleMask indexerMask = TupleMask.fromSelectedIndices(inputKey.getArity(), boundVariableIndices); |
91 | TupleMask callMask = TupleMask.fromSelectedIndices(variableMapping.size(), boundVariables); | 88 | TupleMask callMask = TupleMask.fromSelectedIndices(variableMapping.size(), boundVariables); |
92 | if (unboundVariables.size() == 1) { | 89 | // If multiple tuple elements from the indexer should be bound to the same variable, we must use a |
90 | // {@link GenericTypeExtend} check whether the tuple elements have the same value. | ||
91 | if (unboundVariables.size() == 1 && indexerMask.getSize() + 1 == indexerMask.getSourceWidth()) { | ||
93 | operations.add(new GenericTypeExtendSingleValue(inputKey, positions, callMask, indexerMask, unboundVariables.iterator().next())); | 92 | operations.add(new GenericTypeExtendSingleValue(inputKey, positions, callMask, indexerMask, unboundVariables.iterator().next())); |
94 | } else { | 93 | } else { |
95 | operations.add(new GenericTypeExtend(inputKey, positions, callMask, indexerMask, unboundVariables)); | 94 | operations.add(new GenericTypeExtend(inputKey, positions, callMask, indexerMask, unboundVariables)); |