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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
/*******************************************************************************
* Copyright (c) 2010-2013, Zoltan Ujhelyi, 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.localsearch.operations.extend;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.function.Function;
import tools.refinery.viatra.runtime.localsearch.MatchingFrame;
import tools.refinery.viatra.runtime.localsearch.matcher.ISearchContext;
import tools.refinery.viatra.runtime.localsearch.operations.IPatternMatcherOperation;
import tools.refinery.viatra.runtime.localsearch.operations.ISearchOperation;
import tools.refinery.viatra.runtime.localsearch.operations.util.CallInformation;
import tools.refinery.viatra.runtime.matchers.backend.IQueryResultProvider;
import tools.refinery.viatra.runtime.matchers.tuple.Tuple;
/**
* Checking for a transitive closure expressed as a local search pattern matcher. The matched pattern must have two
* parameters of the same model type.
*
* @author Zoltan Ujhelyi
* @since 1.7
*
*/
public abstract class ExtendBinaryTransitiveClosure implements ISearchOperation, IPatternMatcherOperation {
private class Executor extends SingleValueExtendOperationExecutor<Object> {
public Executor(int position) {
super(position);
}
@Override
public Iterator<?> getIterator(MatchingFrame frame, ISearchContext context) {
// Note: second parameter is NOT bound during execution, but the first is
IQueryResultProvider matcher = context.getMatcher(information.getCallWithAdornment());
Queue<Object> seedsToEvaluate = new LinkedList<>();
final Object seedValue = frame.get(seedPosition);
seedsToEvaluate.add(seedValue);
Set<Object> seedsEvaluated = new HashSet<>();
Set<Object> targetsFound = new HashSet<>();
if (reflexive) {
targetsFound.add(seedValue);
}
while(!seedsToEvaluate.isEmpty()) {
Object currentValue = seedsToEvaluate.poll();
seedsEvaluated.add(currentValue);
final Object[] mappedFrame = calculateCallFrame(currentValue);
matcher.getAllMatches(mappedFrame).forEach(match -> {
Object foundTarget = getTarget(match);
targetsFound.add(foundTarget);
if (!seedsEvaluated.contains(foundTarget)) {
seedsToEvaluate.add(foundTarget);
}
});
}
return targetsFound.iterator();
}
@Override
public ISearchOperation getOperation() {
return ExtendBinaryTransitiveClosure.this;
}
}
/**
* Calculates the transitive closure of a pattern match in a forward direction (first parameter bound, second
* unbound).
* </p>
* <strong>Note</strong>: In case the call is reflexive, it is expected that the bound parameter already matches the universe type of the call.
*
* @since 1.7
*/
public static class Forward extends ExtendBinaryTransitiveClosure {
private Object[] seedFrame = new Object[2];
/**
* @since 2.0
*/
public Forward(CallInformation information, int sourcePosition, int targetPosition, boolean reflexive) {
super(information, sourcePosition, targetPosition, reflexive);
}
protected Object[] calculateCallFrame(Object seed) {
seedFrame[0] = seed;
seedFrame[1] = null;
return seedFrame;
}
protected Object getTarget(Tuple frame) {
return frame.get(1);
}
}
/**
* Calculates the transitive closure of a pattern match in a backward direction (first parameter unbound, second
* bound)
* </p>
* <strong>Note</strong>: In case the call is reflexive, it is expected that the bound parameter already matches the universe type of the call.
*
* @since 2.0
*/
public static class Backward extends ExtendBinaryTransitiveClosure {
private Object[] seedFrame = new Object[2];
/**
* @since 2.0
*/
public Backward(CallInformation information, int sourcePosition, int targetPosition, boolean reflexive) {
super(information, targetPosition, sourcePosition, reflexive);
}
protected Object[] calculateCallFrame(Object seed) {
seedFrame[0] = null;
seedFrame[1] = seed;
return seedFrame;
}
protected Object getTarget(Tuple frame) {
return frame.get(0);
}
}
private final int seedPosition;
private final int targetPosition;
private final CallInformation information;
private final boolean reflexive;
/**
* The source position will be matched in the called pattern to the first parameter; while target to the second.
* @since 2.0
*/
protected ExtendBinaryTransitiveClosure(CallInformation information, int seedPosition, int targetPosition, boolean reflexive) {
this.information = information;
this.seedPosition = seedPosition;
this.targetPosition = targetPosition;
this.reflexive = reflexive;
}
protected abstract Object[] calculateCallFrame(Object seed);
protected abstract Object getTarget(Tuple frame);
@Override
public ISearchOperationExecutor createExecutor() {
return new Executor(targetPosition);
}
@Override
public String toString() {
return toString(Object::toString);
}
@Override
public String toString(Function<Integer, String> variableMapping) {
String c = information.toString(variableMapping);
int p = c.indexOf('(');
return "extend find " + c.substring(0, p) + "+" + c.substring(p);
}
@Override
public List<Integer> getVariablePositions() {
return Arrays.asList(seedPosition, targetPosition);
}
@Override
public CallInformation getCallInformation() {
return information;
}
}
|
