6605620268

Committed 22 Oct 2023 06:53PM UTC coverage: 93.218% (+0.9%) from 92.296%

Build # 6605620268

Build Type

push

github

Committed by

mtf90

Commit Message

cleanup passive integration tests

Run Details

11546 of 12386 relevant lines covered (93.22%)

1.68 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.85

/filters/cache/src/main/java/de/learnlib/filter/cache/mealy/MealyCacheOracle.java

/* Copyright (C) 2013-2023 TU Dortmund
 * This file is part of LearnLib, http://www.learnlib.de/.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package de.learnlib.filter.cache.mealy;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

import de.learnlib.api.Resumable;
import de.learnlib.api.logging.Category;
import de.learnlib.api.oracle.EquivalenceOracle.MealyEquivalenceOracle;
import de.learnlib.api.oracle.MembershipOracle;
import de.learnlib.api.query.Query;
import de.learnlib.filter.cache.LearningCacheOracle.MealyLearningCacheOracle;
import de.learnlib.filter.cache.mealy.MealyCacheOracle.MealyCacheOracleState;
import net.automatalib.SupportsGrowingAlphabet;
import net.automatalib.alphabet.impl.GrowingMapAlphabet;
import net.automatalib.common.util.comparison.CmpUtil;
import net.automatalib.common.util.mapping.Mapping;
import net.automatalib.incremental.mealy.IncrementalMealyBuilder;
import net.automatalib.word.Word;
import net.automatalib.word.WordBuilder;
import org.checkerframework.checker.nullness.qual.Nullable;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * Mealy cache. This cache is implemented as a membership oracle: upon construction, it is provided with a delegate
 * oracle. Queries that can be answered from the cache are answered directly, others are forwarded to the delegate
 * oracle. When the delegate oracle has finished processing these remaining queries, the results are incorporated into
 * the cache.
 * <p>
 * This oracle additionally enables the user to define a Mealy-style prefix-closure filter: a {@link Mapping} from
 * output symbols to output symbols may be provided, with the following semantics: If in an output word a symbol for
 * which the given mapping has a non-null value is encountered, all symbols <i>after</i> this symbol are replaced by the
 * respective value. The rationale behind this is that the concrete error message (key in the mapping) is still
 * reflected in the learned model, it is forced to result in a sink state with only a single repeating output symbol
 * (value in the mapping).
 * <p>
 * <b>Note:</b> this implementation is <b>not</b> thread-safe. If you require a cache that is usable in a parallel
 * environment. use the {@code ThreadSafeMealyCacheOracle} (or rather the {@code ThreadSafeMealyCaches} factory) from
 * the {@code learnlib-parallelism} artifact.
 *
 * @param <I>
 *         input symbol class
 * @param <O>
 *         output symbol class
 */
public class MealyCacheOracle<I, O>
        implements MealyLearningCacheOracle<I, O>, SupportsGrowingAlphabet<I>, Resumable<MealyCacheOracleState<I, O>> {

    private static final Logger LOGGER = LoggerFactory.getLogger(MealyCacheOracle.class);

    private final MembershipOracle<I, Word<O>> delegate;
    private IncrementalMealyBuilder<I, O> incMealy;
    private final Comparator<? super Query<I, ?>> queryCmp;
    private final @Nullable Mapping<? super O, ? extends O> errorSyms;

    MealyCacheOracle(IncrementalMealyBuilder<I, O> incrementalBuilder,
                     @Nullable Mapping<? super O, ? extends O> errorSyms,
                     MembershipOracle<I, Word<O>> delegate) {
        this(incrementalBuilder, errorSyms, delegate, new DynamicSymbolComparator<>());
    }

    MealyCacheOracle(IncrementalMealyBuilder<I, O> incrementalBuilder,
                     @Nullable Mapping<? super O, ? extends O> errorSyms,
                     MembershipOracle<I, Word<O>> delegate,
                     Comparator<I> comparator) {
        this.incMealy = incrementalBuilder;
        this.queryCmp = new ReverseLexCmp<>(comparator);
        this.errorSyms = errorSyms;
        this.delegate = delegate;
    }

    @Override
    public MealyEquivalenceOracle<I, O> createCacheConsistencyTest() {
        return new MealyCacheConsistencyTest<>(incMealy);
    }

    @Override
    public void processQueries(Collection<? extends Query<I, Word<O>>> queries) {
        if (queries.isEmpty()) {
            return;
        }

        List<? extends Query<I, Word<O>>> qrys = new ArrayList<>(queries);
        qrys.sort(queryCmp);

        List<MasterQuery<I, O>> masterQueries = queryCache(qrys);

        delegate.processQueries(masterQueries);

        updateCache(masterQueries);
    }

    @Override
    public void addAlphabetSymbol(I symbol) {
        incMealy.addAlphabetSymbol(symbol);
    }

    @Override
    public MealyCacheOracleState<I, O> suspend() {
        return new MealyCacheOracleState<>(incMealy);
    }

    @Override
    public void resume(MealyCacheOracleState<I, O> state) {
        final Class<?> thisClass = this.incMealy.getClass();
        final Class<?> stateClass = state.getBuilder().getClass();

        if (!thisClass.equals(stateClass)) {
            LOGGER.warn(Category.DATASTRUCTURE,
                        "You currently plan to use a '{}', but the state contained a '{}'. This may yield unexpected behavior.",
                        thisClass,
                        stateClass);
        }

        this.incMealy = state.getBuilder();
    }

    protected List<MasterQuery<I, O>> queryCache(Collection<? extends Query<I, Word<O>>> queries) {
        List<MasterQuery<I, O>> masterQueries = new ArrayList<>();

        Iterator<? extends Query<I, Word<O>>> it = queries.iterator();
        Query<I, Word<O>> q = it.next();
        Word<I> ref = q.getInput();

        MasterQuery<I, O> master = createMasterQuery(ref);
        if (!master.isAnswered()) {
            masterQueries.add(master);
        }
        master.addSlave(q);

        while (it.hasNext()) {
            q = it.next();
            Word<I> curr = q.getInput();
            if (!curr.isPrefixOf(ref)) {
                master = createMasterQuery(curr);
                if (!master.isAnswered()) {
                    masterQueries.add(master);
                }
            }

            master.addSlave(q);
            // Update ref to increase the effectiveness of the length check in
            // isPrefixOf
            ref = curr;
        }

        return masterQueries;
    }

    private MasterQuery<I, O> createMasterQuery(Word<I> word) {
        WordBuilder<O> wb = new WordBuilder<>(word.size());
        if (incMealy.lookup(word, wb)) {
            return new MasterQuery<>(word, wb.toWord());
        }

        if (errorSyms == null) {
            return new MasterQuery<>(word);
        }

        int wbSize = wb.size();

        if (wbSize == 0) {
            return new MasterQuery<>(word, errorSyms);
        }

        O repSym = errorSyms.get(wb.getSymbol(wbSize - 1));
        if (repSym == null) {
            return new MasterQuery<>(word, errorSyms);
        }

        wb.repeatAppend(word.length() - wbSize, repSym);
        return new MasterQuery<>(word, wb.toWord());
    }

    protected void updateCache(Collection<? extends MasterQuery<I, O>> queries) {
        for (MasterQuery<I, O> m : queries) {
            postProcess(m);
        }
    }

    private void postProcess(MasterQuery<I, O> master) {
        Word<I> word = master.getSuffix();
        Word<O> answer = master.getAnswer();

        if (errorSyms == null) {
            incMealy.insert(word, answer);
            return;
        }

        int answLen = answer.length();
        int i = 0;
        while (i < answLen) {
            O sym = answer.getSymbol(i++);
            if (errorSyms.get(sym) != null) {
                break;
            }
        }

        if (i == answLen) {
            incMealy.insert(word, answer);
        } else {
            incMealy.insert(word.prefix(i), answer.prefix(i));
        }
    }

    private static final class ReverseLexCmp<I> implements Comparator<Query<I, ?>> {

        private final Comparator<I> comparator;

        ReverseLexCmp(Comparator<I> comparator) {
            this.comparator = comparator;
        }

        @Override
        public int compare(Query<I, ?> o1, Query<I, ?> o2) {
            return -CmpUtil.lexCompare(o1.getInput(), o2.getInput(), comparator);
        }
    }

    private static final class DynamicSymbolComparator<I> implements Comparator<I> {

        private final GrowingMapAlphabet<I> alphabet;

        DynamicSymbolComparator() {
            this.alphabet = new GrowingMapAlphabet<>();
        }

        @Override
        public int compare(I i1, I i2) {
            alphabet.addSymbol(i1);
            alphabet.addSymbol(i2);
            return alphabet.compare(i1, i2);
        }
    }

    public static class MealyCacheOracleState<I, O> {

        private final IncrementalMealyBuilder<I, O> builder;

        MealyCacheOracleState(IncrementalMealyBuilder<I, O> builder) {
            this.builder = builder;
        }

        IncrementalMealyBuilder<I, O> getBuilder() {
            return builder;
        }
    }

}

1	/* Copyright (C) 2013-2023 TU Dortmund
2	* This file is part of LearnLib, http://www.learnlib.de/.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package de.learnlib.filter.cache.mealy;
17
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.Comparator;
21	import java.util.Iterator;
22	import java.util.List;
23
24	import de.learnlib.api.Resumable;
25	import de.learnlib.api.logging.Category;
26	import de.learnlib.api.oracle.EquivalenceOracle.MealyEquivalenceOracle;
27	import de.learnlib.api.oracle.MembershipOracle;
28	import de.learnlib.api.query.Query;
29	import de.learnlib.filter.cache.LearningCacheOracle.MealyLearningCacheOracle;
30	import de.learnlib.filter.cache.mealy.MealyCacheOracle.MealyCacheOracleState;
31	import net.automatalib.SupportsGrowingAlphabet;
32	import net.automatalib.alphabet.impl.GrowingMapAlphabet;
33	import net.automatalib.common.util.comparison.CmpUtil;
34	import net.automatalib.common.util.mapping.Mapping;
35	import net.automatalib.incremental.mealy.IncrementalMealyBuilder;
36	import net.automatalib.word.Word;
37	import net.automatalib.word.WordBuilder;
38	import org.checkerframework.checker.nullness.qual.Nullable;
39	import org.slf4j.Logger;
40	import org.slf4j.LoggerFactory;
41
42	/**
43	* Mealy cache. This cache is implemented as a membership oracle: upon construction, it is provided with a delegate
44	* oracle. Queries that can be answered from the cache are answered directly, others are forwarded to the delegate
45	* oracle. When the delegate oracle has finished processing these remaining queries, the results are incorporated into
46	* the cache.
47	* <p>
48	* This oracle additionally enables the user to define a Mealy-style prefix-closure filter: a {@link Mapping} from
49	* output symbols to output symbols may be provided, with the following semantics: If in an output word a symbol for
50	* which the given mapping has a non-null value is encountered, all symbols <i>after</i> this symbol are replaced by the
51	* respective value. The rationale behind this is that the concrete error message (key in the mapping) is still
52	* reflected in the learned model, it is forced to result in a sink state with only a single repeating output symbol
53	* (value in the mapping).
54	* <p>
55	* <b>Note:</b> this implementation is <b>not</b> thread-safe. If you require a cache that is usable in a parallel
56	* environment. use the {@code ThreadSafeMealyCacheOracle} (or rather the {@code ThreadSafeMealyCaches} factory) from
57	* the {@code learnlib-parallelism} artifact.
58	*
59	* @param <I>
60	* input symbol class
61	* @param <O>
62	* output symbol class
63	*/
64	public class MealyCacheOracle<I, O>
65	implements MealyLearningCacheOracle<I, O>, SupportsGrowingAlphabet<I>, Resumable<MealyCacheOracleState<I, O>> {
66
67	private static final Logger LOGGER = LoggerFactory.getLogger(MealyCacheOracle.class);	2✔
68
69	private final MembershipOracle<I, Word<O>> delegate;
70	private IncrementalMealyBuilder<I, O> incMealy;
71	private final Comparator<? super Query<I, ?>> queryCmp;
72	private final @Nullable Mapping<? super O, ? extends O> errorSyms;
73
74	MealyCacheOracle(IncrementalMealyBuilder<I, O> incrementalBuilder,
75	@Nullable Mapping<? super O, ? extends O> errorSyms,
76	MembershipOracle<I, Word<O>> delegate) {
77	this(incrementalBuilder, errorSyms, delegate, new DynamicSymbolComparator<>());	2✔
78	}	2✔
79
80	MealyCacheOracle(IncrementalMealyBuilder<I, O> incrementalBuilder,
81	@Nullable Mapping<? super O, ? extends O> errorSyms,
82	MembershipOracle<I, Word<O>> delegate,
83	Comparator<I> comparator) {	2✔
84	this.incMealy = incrementalBuilder;	2✔
85	this.queryCmp = new ReverseLexCmp<>(comparator);	2✔
86	this.errorSyms = errorSyms;	2✔
87	this.delegate = delegate;	2✔
88	}	2✔
89
90	@Override
91	public MealyEquivalenceOracle<I, O> createCacheConsistencyTest() {
92	return new MealyCacheConsistencyTest<>(incMealy);	2✔
93	}
94
95	@Override
96	public void processQueries(Collection<? extends Query<I, Word<O>>> queries) {
97	if (queries.isEmpty()) {	2✔
98	return;	2✔
99	}
100
101	List<? extends Query<I, Word<O>>> qrys = new ArrayList<>(queries);	2✔
102	qrys.sort(queryCmp);	2✔
103
104	List<MasterQuery<I, O>> masterQueries = queryCache(qrys);	2✔
105
106	delegate.processQueries(masterQueries);	2✔
107
108	updateCache(masterQueries);	2✔
109	}	2✔
110
111	@Override
112	public void addAlphabetSymbol(I symbol) {
113	incMealy.addAlphabetSymbol(symbol);	1✔
114	}	1✔
115
116	@Override
117	public MealyCacheOracleState<I, O> suspend() {
118	return new MealyCacheOracleState<>(incMealy);	2✔
119	}
120
121	@Override
122	public void resume(MealyCacheOracleState<I, O> state) {
123	final Class<?> thisClass = this.incMealy.getClass();	2✔
124	final Class<?> stateClass = state.getBuilder().getClass();	2✔
125
126	if (!thisClass.equals(stateClass)) {	2✔
127	LOGGER.warn(Category.DATASTRUCTURE,	×
128	"You currently plan to use a '{}', but the state contained a '{}'. This may yield unexpected behavior.",
129	thisClass,
130	stateClass);
131	}
132
133	this.incMealy = state.getBuilder();	2✔
134	}	2✔
135
136	protected List<MasterQuery<I, O>> queryCache(Collection<? extends Query<I, Word<O>>> queries) {
137	List<MasterQuery<I, O>> masterQueries = new ArrayList<>();	2✔
138
139	Iterator<? extends Query<I, Word<O>>> it = queries.iterator();	2✔
140	Query<I, Word<O>> q = it.next();	2✔
141	Word<I> ref = q.getInput();	2✔
142
143	MasterQuery<I, O> master = createMasterQuery(ref);	2✔
144	if (!master.isAnswered()) {	2✔
145	masterQueries.add(master);	2✔
146	}
147	master.addSlave(q);	2✔
148
149	while (it.hasNext()) {	2✔
150	q = it.next();	2✔
151	Word<I> curr = q.getInput();	2✔
152	if (!curr.isPrefixOf(ref)) {	2✔
153	master = createMasterQuery(curr);	2✔
154	if (!master.isAnswered()) {	2✔
155	masterQueries.add(master);	2✔
156	}
157	}
158
159	master.addSlave(q);	2✔
160	// Update ref to increase the effectiveness of the length check in
161	// isPrefixOf
162	ref = curr;	2✔
163	}	2✔
164
165	return masterQueries;	2✔
166	}
167
168	private MasterQuery<I, O> createMasterQuery(Word<I> word) {
169	WordBuilder<O> wb = new WordBuilder<>(word.size());	2✔
170	if (incMealy.lookup(word, wb)) {	2✔
171	return new MasterQuery<>(word, wb.toWord());	2✔
172	}
173
174	if (errorSyms == null) {	2✔
175	return new MasterQuery<>(word);	2✔
176	}
177
178	int wbSize = wb.size();	2✔
179
180	if (wbSize == 0) {	2✔
181	return new MasterQuery<>(word, errorSyms);	2✔
182	}
183
184	O repSym = errorSyms.get(wb.getSymbol(wbSize - 1));	2✔
185	if (repSym == null) {	2✔
186	return new MasterQuery<>(word, errorSyms);	2✔
187	}
188
189	wb.repeatAppend(word.length() - wbSize, repSym);	2✔
190	return new MasterQuery<>(word, wb.toWord());	2✔
191	}
192
193	protected void updateCache(Collection<? extends MasterQuery<I, O>> queries) {
194	for (MasterQuery<I, O> m : queries) {	2✔
195	postProcess(m);	2✔
196	}	2✔
197	}	2✔
198
199	private void postProcess(MasterQuery<I, O> master) {
200	Word<I> word = master.getSuffix();	2✔
201	Word<O> answer = master.getAnswer();	2✔
202
203	if (errorSyms == null) {	2✔
204	incMealy.insert(word, answer);	2✔
205	return;	2✔
206	}
207
208	int answLen = answer.length();	2✔
209	int i = 0;	2✔
210	while (i < answLen) {	2✔
211	O sym = answer.getSymbol(i++);	2✔
212	if (errorSyms.get(sym) != null) {	2✔
213	break;	2✔
214	}
215	}	2✔
216
217	if (i == answLen) {	2✔
218	incMealy.insert(word, answer);	×
219	} else {
220	incMealy.insert(word.prefix(i), answer.prefix(i));	2✔
221	}
222	}	2✔
223
224	private static final class ReverseLexCmp<I> implements Comparator<Query<I, ?>> {
225
226	private final Comparator<I> comparator;
227
228	ReverseLexCmp(Comparator<I> comparator) {	2✔
229	this.comparator = comparator;	2✔
230	}	2✔
231
232	@Override
233	public int compare(Query<I, ?> o1, Query<I, ?> o2) {
234	return -CmpUtil.lexCompare(o1.getInput(), o2.getInput(), comparator);	2✔
235	}
236	}
237
238	private static final class DynamicSymbolComparator<I> implements Comparator<I> {
239
240	private final GrowingMapAlphabet<I> alphabet;
241
242	DynamicSymbolComparator() {	2✔
243	this.alphabet = new GrowingMapAlphabet<>();	2✔
244	}	2✔
245
246	@Override
247	public int compare(I i1, I i2) {
248	alphabet.addSymbol(i1);	2✔
249	alphabet.addSymbol(i2);	2✔
250	return alphabet.compare(i1, i2);	2✔
251	}
252	}
253
254	public static class MealyCacheOracleState<I, O> {
255
256	private final IncrementalMealyBuilder<I, O> builder;
257
258	MealyCacheOracleState(IncrementalMealyBuilder<I, O> builder) {	2✔
259	this.builder = builder;	2✔
260	}	2✔
261
262	IncrementalMealyBuilder<I, O> getBuilder() {
263	return builder;	2✔
264	}
265	}
266
267	}

LearnLib / learnlib / 6605620268

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous