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

96.08

/algorithms/active/dhc/src/main/java/de/learnlib/algorithm/dhc/mealy/MealyDHC.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.algorithm.dhc.mealy;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

import com.github.misberner.buildergen.annotations.GenerateBuilder;
import com.google.common.collect.Interner;
import com.google.common.collect.Interners;
import com.google.common.collect.Sets;
import de.learnlib.api.AccessSequenceTransformer;
import de.learnlib.api.Resumable;
import de.learnlib.api.algorithm.LearningAlgorithm.MealyLearner;
import de.learnlib.api.algorithm.feature.GlobalSuffixLearner.GlobalSuffixLearnerMealy;
import de.learnlib.api.oracle.MembershipOracle;
import de.learnlib.api.query.DefaultQuery;
import de.learnlib.counterexample.GlobalSuffixFinder;
import de.learnlib.counterexample.GlobalSuffixFinders;
import net.automatalib.SupportsGrowingAlphabet;
import net.automatalib.alphabet.Alphabet;
import net.automatalib.alphabet.impl.Alphabets;
import net.automatalib.automaton.transducer.impl.compact.CompactMealy;
import net.automatalib.common.util.mapping.MapMapping;
import net.automatalib.common.util.mapping.MutableMapping;
import net.automatalib.word.Word;
import org.checkerframework.checker.nullness.qual.NonNull;
import org.checkerframework.checker.nullness.qual.Nullable;

public class MealyDHC<I, O> implements MealyLearner<I, O>,
                                       AccessSequenceTransformer<I>,
                                       GlobalSuffixLearnerMealy<I, O>,
                                       SupportsGrowingAlphabet<I>,
                                       Resumable<MealyDHCState<I, O>> {

    private final MembershipOracle<I, Word<O>> oracle;
    private final Alphabet<I> alphabet;
    private Set<Word<I>> splitters = new LinkedHashSet<>();
    private CompactMealy<I, O> hypothesis;
    private MutableMapping<Integer, QueueElement<I, O>> accessSequences;
    private final GlobalSuffixFinder<? super I, ? super Word<O>> suffixFinder;

    /**
     * Constructor, provided for backwards compatibility reasons.
     *
     * @param alphabet
     *         the learning alphabet
     * @param oracle
     *         the learning membership oracle
     */
    public MealyDHC(Alphabet<I> alphabet, MembershipOracle<I, Word<O>> oracle) {
        this(alphabet, oracle, GlobalSuffixFinders.RIVEST_SCHAPIRE, Collections.emptyList());
    }

    /**
     * Constructor.
     *
     * @param alphabet
     *         the learning alphabet
     * @param oracle
     *         the learning membership oracle
     * @param suffixFinder
     *         the {@link GlobalSuffixFinder suffix finder} to use for analyzing counterexamples
     * @param initialSplitters
     *         the initial set of splitters, {@code null} or an empty collection will result in the set of splitters
     *         being initialized as the set of alphabet symbols (interpreted as {@link Word}s)
     */
    @GenerateBuilder(defaults = BuilderDefaults.class, builderFinal = false)
    public MealyDHC(Alphabet<I> alphabet,
                    MembershipOracle<I, Word<O>> oracle,
                    GlobalSuffixFinder<? super I, ? super Word<O>> suffixFinder,
                    Collection<? extends Word<I>> initialSplitters) {
        this.alphabet = alphabet;
        this.oracle = oracle;
        this.suffixFinder = suffixFinder;
        // ensure that the first k splitters are the k alphabet symbols,
        // in correct order (this is required by scheduleSuccessors)
        for (I symbol : alphabet) {
            splitters.add(Word.fromLetter(symbol));
        }
        if (initialSplitters != null) {
            splitters.addAll(initialSplitters);
        }
    }

    @Override
    public Collection<Word<I>> getGlobalSuffixes() {
        return Collections.unmodifiableCollection(splitters);
    }

    @Override
    public boolean addGlobalSuffixes(Collection<? extends Word<I>> newGlobalSuffixes) {
        checkInternalState();

        return addSuffixesUnchecked(newGlobalSuffixes);
    }

    private void checkInternalState() {
        if (hypothesis == null) {
            throw new IllegalStateException("No hypothesis learned yet");
        }
    }

    protected boolean addSuffixesUnchecked(Collection<? extends Word<I>> newSuffixes) {
        int oldSize = hypothesis.size();

        splitters.addAll(newSuffixes);

        startLearning();

        return hypothesis.size() != oldSize;
    }

    @Override
    public void startLearning() {
        // initialize structure to store state output signatures
        Map<List<Word<O>>, Integer> signatures = new HashMap<>();

        // set up new hypothesis machine
        hypothesis = new CompactMealy<>(alphabet);

        // initialize exploration queue
        Queue<QueueElement<I, O>> queue = new ArrayDeque<>();

        // initialize storage for access sequences
        accessSequences = hypothesis.createDynamicStateMapping();

        // first element to be explored represents the initial state with no predecessor
        queue.add(new QueueElement<>(null, null, null, null));

        Interner<Word<O>> deduplicator = Interners.newStrongInterner();

        while (!queue.isEmpty()) {
            // get element to be explored from queue
            @SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
            @NonNull QueueElement<I, O> elem = queue.poll();

            // determine access sequence for state
            Word<I> access = assembleAccessSequence(elem);

            // assemble queries
            ArrayList<DefaultQuery<I, Word<O>>> queries = new ArrayList<>(splitters.size());
            for (Word<I> suffix : splitters) {
                queries.add(new DefaultQuery<>(access, suffix));
            }

            // retrieve answers
            oracle.processQueries(queries);

            // assemble output signature
            List<Word<O>> sig = new ArrayList<>(splitters.size());
            for (DefaultQuery<I, Word<O>> query : queries) {
                sig.add(deduplicator.intern(query.getOutput()));
            }

            Integer sibling = signatures.get(sig);

            if (sibling != null) {
                // this element does not possess a new output signature
                // create a transition from parent state to sibling
                hypothesis.addTransition(elem.parentState, elem.transIn, sibling, elem.transOut);
            } else {
                // this is actually an observably distinct state! Progress!
                // Create state and connect via transition to parent
                Integer state = elem.parentElement == null ? hypothesis.addInitialState() : hypothesis.addState();
                if (elem.parentElement != null) {
                    hypothesis.addTransition(elem.parentState, elem.transIn, state, elem.transOut);
                }
                signatures.put(sig, state);
                accessSequences.put(state, elem);

                scheduleSuccessors(elem, state, queue, sig);
            }
        }
    }

    private Word<I> assembleAccessSequence(QueueElement<I, O> elem) {
        List<I> word = new ArrayList<>(elem.depth);

        QueueElement<I, O> pre = elem.parentElement;
        I sym = elem.transIn;
        while (pre != null && sym != null) {
            word.add(sym);
            sym = pre.transIn;
            pre = pre.parentElement;
        }

        Collections.reverse(word);
        return Word.fromList(word);
    }

    private void scheduleSuccessors(QueueElement<I, O> elem,
                                    Integer state,
                                    Queue<QueueElement<I, O>> queue,
                                    List<Word<O>> sig) {
        for (int i = 0; i < alphabet.size(); ++i) {
            // retrieve I/O for transition
            I input = alphabet.getSymbol(i);
            O output = sig.get(i).getSymbol(0);

            // create successor element and schedule for exploration
            queue.add(new QueueElement<>(state, elem, input, output));
        }
    }

    @Override
    public boolean refineHypothesis(DefaultQuery<I, Word<O>> ceQuery) {
        checkInternalState();

        Collection<Word<I>> ceSuffixes = suffixFinder.findSuffixes(ceQuery, this, hypothesis, oracle);

        return addSuffixesUnchecked(ceSuffixes);
    }

    @Override
    public CompactMealy<I, O> getHypothesisModel() {
        checkInternalState();
        return hypothesis;
    }

    @Override
    public void addAlphabetSymbol(I symbol) {

        if (!this.alphabet.containsSymbol(symbol)) {
            Alphabets.toGrowingAlphabetOrThrowException(this.alphabet).addSymbol(symbol);
        }

        if (!this.splitters.contains(Word.fromLetter(symbol))) {
            final Iterator<Word<I>> splitterIterator = this.splitters.iterator();
            final LinkedHashSet<Word<I>> newSplitters =
                    Sets.newLinkedHashSetWithExpectedSize(this.splitters.size() + 1);

            // see initial initialization of the splitters
            for (int i = 0; i < this.alphabet.size() - 1; i++) {
                newSplitters.add(splitterIterator.next());
            }

            newSplitters.add(Word.fromLetter(symbol));

            while (splitterIterator.hasNext()) {
                newSplitters.add(splitterIterator.next());
            }

            this.splitters = newSplitters;

            this.startLearning();
        }
    }

    @Override
    public MealyDHCState<I, O> suspend() {
        return new MealyDHCState<>(splitters, hypothesis, accessSequences);
    }

    @Override
    public void resume(MealyDHCState<I, O> state) {
        this.splitters = state.getSplitters();
        this.accessSequences = new MapMapping<>(state.getAccessSequences());
        this.hypothesis = state.getHypothesis();
    }

    @Override
    public Word<I> transformAccessSequence(Word<I> word) {
        checkInternalState();
        Integer state = hypothesis.getSuccessor(hypothesis.getInitialState(), word);
        return assembleAccessSequence(accessSequences.get(state));
    }

    public static final class BuilderDefaults {

        private BuilderDefaults() {
            // prevent instantiation
        }

        public static <I, O> GlobalSuffixFinder<? super I, ? super Word<O>> suffixFinder() {
            return GlobalSuffixFinders.RIVEST_SCHAPIRE;
        }

        public static <I> Collection<Word<I>> initialSplitters() {
            return Collections.emptyList();
        }
    }

    static final class QueueElement<I, O> {

        private final @Nullable Integer parentState;
        private final @Nullable QueueElement<I, O> parentElement;
        private final @Nullable I transIn;
        private final @Nullable O transOut;
        private final int depth;

        QueueElement(@Nullable Integer parentState,
                     @Nullable QueueElement<I, O> parentElement,
                     @Nullable I transIn,
                     @Nullable O transOut) {
            this.parentState = parentState;
            this.parentElement = parentElement;
            this.transIn = transIn;
            this.transOut = transOut;
            this.depth = (parentElement != null) ? parentElement.depth + 1 : 0;
        }
    }
}

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.algorithm.dhc.mealy;
17
18	import java.util.ArrayDeque;
19	import java.util.ArrayList;
20	import java.util.Collection;
21	import java.util.Collections;
22	import java.util.HashMap;
23	import java.util.Iterator;
24	import java.util.LinkedHashSet;
25	import java.util.List;
26	import java.util.Map;
27	import java.util.Queue;
28	import java.util.Set;
29
30	import com.github.misberner.buildergen.annotations.GenerateBuilder;
31	import com.google.common.collect.Interner;
32	import com.google.common.collect.Interners;
33	import com.google.common.collect.Sets;
34	import de.learnlib.api.AccessSequenceTransformer;
35	import de.learnlib.api.Resumable;
36	import de.learnlib.api.algorithm.LearningAlgorithm.MealyLearner;
37	import de.learnlib.api.algorithm.feature.GlobalSuffixLearner.GlobalSuffixLearnerMealy;
38	import de.learnlib.api.oracle.MembershipOracle;
39	import de.learnlib.api.query.DefaultQuery;
40	import de.learnlib.counterexample.GlobalSuffixFinder;
41	import de.learnlib.counterexample.GlobalSuffixFinders;
42	import net.automatalib.SupportsGrowingAlphabet;
43	import net.automatalib.alphabet.Alphabet;
44	import net.automatalib.alphabet.impl.Alphabets;
45	import net.automatalib.automaton.transducer.impl.compact.CompactMealy;
46	import net.automatalib.common.util.mapping.MapMapping;
47	import net.automatalib.common.util.mapping.MutableMapping;
48	import net.automatalib.word.Word;
49	import org.checkerframework.checker.nullness.qual.NonNull;
50	import org.checkerframework.checker.nullness.qual.Nullable;
51
52	public class MealyDHC<I, O> implements MealyLearner<I, O>,
53	AccessSequenceTransformer<I>,
54	GlobalSuffixLearnerMealy<I, O>,
55	SupportsGrowingAlphabet<I>,
56	Resumable<MealyDHCState<I, O>> {
57
58	private final MembershipOracle<I, Word<O>> oracle;
59	private final Alphabet<I> alphabet;
60	private Set<Word<I>> splitters = new LinkedHashSet<>();	2✔
61	private CompactMealy<I, O> hypothesis;
62	private MutableMapping<Integer, QueueElement<I, O>> accessSequences;
63	private final GlobalSuffixFinder<? super I, ? super Word<O>> suffixFinder;
64
65	/**
66	* Constructor, provided for backwards compatibility reasons.
67	*
68	* @param alphabet
69	* the learning alphabet
70	* @param oracle
71	* the learning membership oracle
72	*/
73	public MealyDHC(Alphabet<I> alphabet, MembershipOracle<I, Word<O>> oracle) {
74	this(alphabet, oracle, GlobalSuffixFinders.RIVEST_SCHAPIRE, Collections.emptyList());	2✔
75	}	2✔
76
77	/**
78	* Constructor.
79	*
80	* @param alphabet
81	* the learning alphabet
82	* @param oracle
83	* the learning membership oracle
84	* @param suffixFinder
85	* the {@link GlobalSuffixFinder suffix finder} to use for analyzing counterexamples
86	* @param initialSplitters
87	* the initial set of splitters, {@code null} or an empty collection will result in the set of splitters
88	* being initialized as the set of alphabet symbols (interpreted as {@link Word}s)
89	*/
90	@GenerateBuilder(defaults = BuilderDefaults.class, builderFinal = false)
91	public MealyDHC(Alphabet<I> alphabet,
92	MembershipOracle<I, Word<O>> oracle,
93	GlobalSuffixFinder<? super I, ? super Word<O>> suffixFinder,
94	Collection<? extends Word<I>> initialSplitters) {	2✔
95	this.alphabet = alphabet;	2✔
96	this.oracle = oracle;	2✔
97	this.suffixFinder = suffixFinder;	2✔
98	// ensure that the first k splitters are the k alphabet symbols,
99	// in correct order (this is required by scheduleSuccessors)
100	for (I symbol : alphabet) {	2✔
101	splitters.add(Word.fromLetter(symbol));	2✔
102	}	2✔
103	if (initialSplitters != null) {	2✔
104	splitters.addAll(initialSplitters);	2✔
105	}
106	}	2✔
107
108	@Override
109	public Collection<Word<I>> getGlobalSuffixes() {
110	return Collections.unmodifiableCollection(splitters);	×
111	}
112
113	@Override
114	public boolean addGlobalSuffixes(Collection<? extends Word<I>> newGlobalSuffixes) {
115	checkInternalState();	×
116
117	return addSuffixesUnchecked(newGlobalSuffixes);	×
118	}
119
120	private void checkInternalState() {
121	if (hypothesis == null) {	2✔
122	throw new IllegalStateException("No hypothesis learned yet");	2✔
123	}
124	}	2✔
125
126	protected boolean addSuffixesUnchecked(Collection<? extends Word<I>> newSuffixes) {
127	int oldSize = hypothesis.size();	2✔
128
129	splitters.addAll(newSuffixes);	2✔
130
131	startLearning();	2✔
132
133	return hypothesis.size() != oldSize;	2✔
134	}
135
136	@Override
137	public void startLearning() {
138	// initialize structure to store state output signatures
139	Map<List<Word<O>>, Integer> signatures = new HashMap<>();	2✔
140
141	// set up new hypothesis machine
142	hypothesis = new CompactMealy<>(alphabet);	2✔
143
144	// initialize exploration queue
145	Queue<QueueElement<I, O>> queue = new ArrayDeque<>();	2✔
146
147	// initialize storage for access sequences
148	accessSequences = hypothesis.createDynamicStateMapping();	2✔
149
150	// first element to be explored represents the initial state with no predecessor
151	queue.add(new QueueElement<>(null, null, null, null));	2✔
152
153	Interner<Word<O>> deduplicator = Interners.newStrongInterner();	2✔
154
155	while (!queue.isEmpty()) {	2✔
156	// get element to be explored from queue
157	@SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
158	@NonNull QueueElement<I, O> elem = queue.poll();	2✔
159
160	// determine access sequence for state
161	Word<I> access = assembleAccessSequence(elem);	2✔
162
163	// assemble queries
164	ArrayList<DefaultQuery<I, Word<O>>> queries = new ArrayList<>(splitters.size());	2✔
165	for (Word<I> suffix : splitters) {	2✔
166	queries.add(new DefaultQuery<>(access, suffix));	2✔
167	}	2✔
168
169	// retrieve answers
170	oracle.processQueries(queries);	2✔
171
172	// assemble output signature
173	List<Word<O>> sig = new ArrayList<>(splitters.size());	2✔
174	for (DefaultQuery<I, Word<O>> query : queries) {	2✔
175	sig.add(deduplicator.intern(query.getOutput()));	2✔
176	}	2✔
177
178	Integer sibling = signatures.get(sig);	2✔
179
180	if (sibling != null) {	2✔
181	// this element does not possess a new output signature
182	// create a transition from parent state to sibling
183	hypothesis.addTransition(elem.parentState, elem.transIn, sibling, elem.transOut);	2✔
184	} else {
185	// this is actually an observably distinct state! Progress!
186	// Create state and connect via transition to parent
187	Integer state = elem.parentElement == null ? hypothesis.addInitialState() : hypothesis.addState();	2✔
188	if (elem.parentElement != null) {	2✔
189	hypothesis.addTransition(elem.parentState, elem.transIn, state, elem.transOut);	2✔
190	}
191	signatures.put(sig, state);	2✔
192	accessSequences.put(state, elem);	2✔
193
194	scheduleSuccessors(elem, state, queue, sig);	2✔
195	}
196	}	2✔
197	}	2✔
198
199	private Word<I> assembleAccessSequence(QueueElement<I, O> elem) {
200	List<I> word = new ArrayList<>(elem.depth);	2✔
201
202	QueueElement<I, O> pre = elem.parentElement;	2✔
203	I sym = elem.transIn;	2✔
204	while (pre != null && sym != null) {	2✔
205	word.add(sym);	2✔
206	sym = pre.transIn;	2✔
207	pre = pre.parentElement;	2✔
208	}
209
210	Collections.reverse(word);	2✔
211	return Word.fromList(word);	2✔
212	}
213
214	private void scheduleSuccessors(QueueElement<I, O> elem,
215	Integer state,
216	Queue<QueueElement<I, O>> queue,
217	List<Word<O>> sig) {
218	for (int i = 0; i < alphabet.size(); ++i) {	2✔
219	// retrieve I/O for transition
220	I input = alphabet.getSymbol(i);	2✔
221	O output = sig.get(i).getSymbol(0);	2✔
222
223	// create successor element and schedule for exploration
224	queue.add(new QueueElement<>(state, elem, input, output));	2✔
225	}
226	}	2✔
227
228	@Override
229	public boolean refineHypothesis(DefaultQuery<I, Word<O>> ceQuery) {
230	checkInternalState();	2✔
231
232	Collection<Word<I>> ceSuffixes = suffixFinder.findSuffixes(ceQuery, this, hypothesis, oracle);	2✔
233
234	return addSuffixesUnchecked(ceSuffixes);	2✔
235	}
236
237	@Override
238	public CompactMealy<I, O> getHypothesisModel() {
239	checkInternalState();	2✔
240	return hypothesis;	2✔
241	}
242
243	@Override
244	public void addAlphabetSymbol(I symbol) {
245
246	if (!this.alphabet.containsSymbol(symbol)) {	2✔
247	Alphabets.toGrowingAlphabetOrThrowException(this.alphabet).addSymbol(symbol);	2✔
248	}
249
250	if (!this.splitters.contains(Word.fromLetter(symbol))) {	2✔
251	final Iterator<Word<I>> splitterIterator = this.splitters.iterator();	2✔
252	final LinkedHashSet<Word<I>> newSplitters =	2✔
253	Sets.newLinkedHashSetWithExpectedSize(this.splitters.size() + 1);	2✔
254
255	// see initial initialization of the splitters
256	for (int i = 0; i < this.alphabet.size() - 1; i++) {	2✔
257	newSplitters.add(splitterIterator.next());	2✔
258	}
259
260	newSplitters.add(Word.fromLetter(symbol));	2✔
261
262	while (splitterIterator.hasNext()) {	2✔
263	newSplitters.add(splitterIterator.next());	×
264	}
265
266	this.splitters = newSplitters;	2✔
267
268	this.startLearning();	2✔
269	}
270	}	2✔
271
272	@Override
273	public MealyDHCState<I, O> suspend() {
274	return new MealyDHCState<>(splitters, hypothesis, accessSequences);	2✔
275	}
276
277	@Override
278	public void resume(MealyDHCState<I, O> state) {
279	this.splitters = state.getSplitters();	2✔
280	this.accessSequences = new MapMapping<>(state.getAccessSequences());	2✔
281	this.hypothesis = state.getHypothesis();	2✔
282	}	2✔
283
284	@Override
285	public Word<I> transformAccessSequence(Word<I> word) {
286	checkInternalState();	2✔
287	Integer state = hypothesis.getSuccessor(hypothesis.getInitialState(), word);	2✔
288	return assembleAccessSequence(accessSequences.get(state));	2✔
289	}
290
291	public static final class BuilderDefaults {
292
293	private BuilderDefaults() {
294	// prevent instantiation
295	}
296
297	public static <I, O> GlobalSuffixFinder<? super I, ? super Word<O>> suffixFinder() {
298	return GlobalSuffixFinders.RIVEST_SCHAPIRE;	2✔
299	}
300
301	public static <I> Collection<Word<I>> initialSplitters() {
302	return Collections.emptyList();	2✔
303	}
304	}
305
306	static final class QueueElement<I, O> {
307
308	private final @Nullable Integer parentState;
309	private final @Nullable QueueElement<I, O> parentElement;
310	private final @Nullable I transIn;
311	private final @Nullable O transOut;
312	private final int depth;
313
314	QueueElement(@Nullable Integer parentState,
315	@Nullable QueueElement<I, O> parentElement,
316	@Nullable I transIn,
317	@Nullable O transOut) {	2✔
318	this.parentState = parentState;	2✔
319	this.parentElement = parentElement;	2✔
320	this.transIn = transIn;	2✔
321	this.transOut = transOut;	2✔
322	this.depth = (parentElement != null) ? parentElement.depth + 1 : 0;	2✔
323	}	2✔
324	}
325	}

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