6433387082

Committed 06 Oct 2023 03:10PM UTC coverage: 92.296% (-0.007%) from 92.303%

Build # 6433387082

Build Type

push

github

Committed by

mtf90

Commit Message

update Falk's developer id

Run Details

11573 of 12539 relevant lines covered (92.3%)

1.67 hits per line

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

97.85

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

LearnLib / learnlib / 6433387082

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