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

98.86

/examples/src/main/java/de/learnlib/examples/Example3.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.examples;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.function.Supplier;

import de.learnlib.algorithms.lstar.mealy.ExtensibleLStarMealyBuilder;
import de.learnlib.api.algorithm.LearningAlgorithm.MealyLearner;
import de.learnlib.api.oracle.MembershipOracle.MealyMembershipOracle;
import de.learnlib.api.query.Query;
import de.learnlib.examples.Example2.BoundedStringQueue;
import de.learnlib.filter.reuse.ReuseCapableOracle;
import de.learnlib.filter.reuse.ReuseOracle;
import de.learnlib.filter.reuse.ReuseOracle.ReuseOracleBuilder;
import de.learnlib.filter.reuse.tree.SystemStateHandler;
import net.automatalib.automata.transducers.MealyMachine;
import net.automatalib.util.automata.Automata;
import net.automatalib.words.Alphabet;
import net.automatalib.words.Word;
import net.automatalib.words.WordBuilder;
import net.automatalib.words.impl.GrowingMapAlphabet;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * This example shows how to use the reuse filter on the {@link BoundedStringQueue} of {@link Example2}.
 * <p>
 * Please note that there is no equivalence oracle used in this example so the resulting mealy machines are only first
 * "guesses".
 */
@SuppressWarnings("PMD.SystemPrintln")
public class Example3 {

    private static final String OFFER_1 = "offer_1";
    private static final String OFFER_2 = "offer_2";
    private static final String POLL = "poll";
    private final Alphabet<String> sigma;
    private final List<Word<String>> initialSuffixes;

    public Example3() {
        sigma = new GrowingMapAlphabet<>();
        sigma.add(OFFER_1);
        sigma.add(OFFER_2);
        sigma.add(POLL);

        initialSuffixes = new ArrayList<>();
        for (String symbol : sigma) {
            initialSuffixes.add(Word.fromLetter(symbol));
        }
    }

    public static void main(String[] args) {
        Example3 example = new Example3();
        System.out.println("--");
        System.out.println("Run experiment 1 (ReuseOracle):");
        MealyMachine<?, String, ?, @Nullable String> result1 = example.runExperiment1();
        System.out.println("--");
        System.out.println("Run experiment 2:");
        MealyMachine<?, String, ?, @Nullable String> result2 = example.runExperiment2();
        System.out.println("--");
        System.out.println("Model 1: " + result1.size() + " states");
        System.out.println("Model 2: " + result2.size() + " states");

        Word<String> sepWord;
        sepWord = Automata.findSeparatingWord(result1, result2, example.sigma);

        System.out.println("Difference (separating word)? " + sepWord);

        /*
         * Background knowledge: L^* creates an observation table with
         * |S|=3,|SA|=7,|E|=3 so 30 MQs should be sufficient. The reuse filter
         * should sink system states from S*E to SA*E so the upper part is the
         * number of saved resets (=9).
         *
         * If the numbers don't match:
         * https://github.com/LearnLib/learnlib/issues/5 (9 queries will be
         * pumped by the reuse filter)
         */
    }

    /*
     * A "normal" scenario without reuse filter technique.
     */
    public MealyMachine<?, String, ?, @Nullable String> runExperiment1() {
        // For each membership query a new instance of BoundedStringQueue will
        // be created (normal learning scenario without filters)
        FullMembershipQueryOracle oracle = new FullMembershipQueryOracle();

        // construct L* instance (almost classic Mealy version)
        // almost: we use words (Word<String>) in cells of the table
        // instead of single outputs.
        MealyLearner<String, @Nullable String> lstar;
        lstar = new ExtensibleLStarMealyBuilder<String, @Nullable String>().withAlphabet(sigma)
                                                                           .withInitialSuffixes(initialSuffixes)
                                                                           .withOracle(oracle)
                                                                           .create();

        lstar.startLearning();
        MealyMachine<?, String, ?, @Nullable String> result;
        result = lstar.getHypothesisModel();

        System.out.println("Resets:  " + oracle.resets);
        System.out.println("Symbols: " + oracle.symbols);

        return result;
    }

    /*
     * Scenario with reuse filter technique.
     */
    public MealyMachine<?, String, ?, @Nullable String> runExperiment2() {
        MySystemStateHandler ssh = new MySystemStateHandler();

        // This time we use the reuse filter to avoid some resets and
        // save execution of symbols
        Supplier<ReuseCapableOracle<BoundedStringQueue, String, @Nullable String>> supplier = ReuseCapableImpl::new;
        ReuseOracle<BoundedStringQueue, String, @Nullable String> reuseOracle =
                new ReuseOracleBuilder<>(sigma, supplier).withSystemStateHandler(ssh).build();

        // construct L* instance (almost classic Mealy version)
        // almost: we use words (Word<String>) in cells of the table
        // instead of single outputs.

        MealyLearner<String, @Nullable String> lstar;
        lstar = new ExtensibleLStarMealyBuilder<String, @Nullable String>().withAlphabet(sigma)
                                                                           .withInitialSuffixes(initialSuffixes)
                                                                           .withOracle(reuseOracle)
                                                                           .create();

        lstar.startLearning();

        // get learned model
        MealyMachine<?, String, ?, @Nullable String> result = lstar.getHypothesisModel();

        // now invalidate all system states and count the number of disposed
        // queues (equals number of resets)
        reuseOracle.getReuseTree().disposeSystemStates();
        ReuseCapableImpl reuseCapableOracle = (ReuseCapableImpl) reuseOracle.getReuseCapableOracle();
        System.out.println("Resets:   " + reuseCapableOracle.fullQueries);
        System.out.println("Reused:   " + reuseCapableOracle.reused);
        System.out.println("Symbols:  " + reuseCapableOracle.symbols);
        // disposed = resets
        System.out.println("Disposed: " + ssh.disposed);

        return result;
    }

    private @Nullable String exec(BoundedStringQueue s, String input) {
        switch (input) {
            case OFFER_1:
            case OFFER_2:
                s.offer(input);
                return "void";
            case POLL:
                return s.poll();
            default:
                throw new IllegalArgumentException("unknown input symbol");
        }
    }

    /**
     * For running the example this class could also be removed/ignored. It is only here for documentation purposes.
     */
    static class MySystemStateHandler implements SystemStateHandler<BoundedStringQueue> {

        private int disposed;

        @Override
        public void dispose(BoundedStringQueue state) {
            /*
             * When learning e.g. examples that involve databases, here would be
             * a good point to remove database entities. In this example we just
             * count the number of disposed (garbage collection inside the reuse
             * tree) objects.
             */
            disposed++;
        }
    }

    /**
     * An oracle that also does the reset by creating a new instance of the {@link BoundedStringQueue}.
     */
    class FullMembershipQueryOracle implements MealyMembershipOracle<String, @Nullable String> {

        private int resets;
        private int symbols;

        @Override
        public void processQueries(Collection<? extends Query<String, Word<@Nullable String>>> queries) {
            for (Query<String, Word<@Nullable String>> query : queries) {
                resets++;
                symbols += query.getInput().size();

                BoundedStringQueue s = new BoundedStringQueue();

                WordBuilder<@Nullable String> output = new WordBuilder<>();
                for (String input : query.getInput()) {
                    output.add(exec(s, input));
                }

                query.answer(output.toWord().suffix(query.getSuffix().size()));
            }
        }
    }

    /**
     * An implementation of the {@link ReuseCapableOracle} needed for the {@link ReuseOracle}. It only does reset by
     * means of creating a new {@link BoundedStringQueue} instance in {@link ReuseCapableOracle#processQuery(Word)}.
     */
    class ReuseCapableImpl implements ReuseCapableOracle<BoundedStringQueue, String, @Nullable String> {

        private int reused;
        private int fullQueries;
        private int symbols;

        @Override
        public QueryResult<BoundedStringQueue, @Nullable String> continueQuery(Word<String> trace,
                                                                               BoundedStringQueue s) {

            reused++;
            symbols += trace.size();

            WordBuilder<@Nullable String> output = new WordBuilder<>();

            for (String input : trace) {
                output.add(exec(s, input));
            }

            QueryResult<BoundedStringQueue, @Nullable String> result;
            result = new QueryResult<>(output.toWord(), s);

            return result;
        }

        @Override
        public QueryResult<BoundedStringQueue, @Nullable String> processQuery(Word<String> trace) {
            fullQueries++;
            symbols += trace.size();

            // Suppose the reset would be a time-consuming operation
            BoundedStringQueue s = new BoundedStringQueue();

            WordBuilder<@Nullable String> output = new WordBuilder<>();

            for (String input : trace) {
                output.add(exec(s, input));
            }

            QueryResult<BoundedStringQueue, @Nullable String> result;
            result = new QueryResult<>(output.toWord(), s);

            return result;
        }
    }
}

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.examples;
17
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.List;
21	import java.util.function.Supplier;
22
23	import de.learnlib.algorithms.lstar.mealy.ExtensibleLStarMealyBuilder;
24	import de.learnlib.api.algorithm.LearningAlgorithm.MealyLearner;
25	import de.learnlib.api.oracle.MembershipOracle.MealyMembershipOracle;
26	import de.learnlib.api.query.Query;
27	import de.learnlib.examples.Example2.BoundedStringQueue;
28	import de.learnlib.filter.reuse.ReuseCapableOracle;
29	import de.learnlib.filter.reuse.ReuseOracle;
30	import de.learnlib.filter.reuse.ReuseOracle.ReuseOracleBuilder;
31	import de.learnlib.filter.reuse.tree.SystemStateHandler;
32	import net.automatalib.automata.transducers.MealyMachine;
33	import net.automatalib.util.automata.Automata;
34	import net.automatalib.words.Alphabet;
35	import net.automatalib.words.Word;
36	import net.automatalib.words.WordBuilder;
37	import net.automatalib.words.impl.GrowingMapAlphabet;
38	import org.checkerframework.checker.nullness.qual.Nullable;
39
40	/**
41	* This example shows how to use the reuse filter on the {@link BoundedStringQueue} of {@link Example2}.
42	* <p>
43	* Please note that there is no equivalence oracle used in this example so the resulting mealy machines are only first
44	* "guesses".
45	*/
46	@SuppressWarnings("PMD.SystemPrintln")
47	public class Example3 {
48
49	private static final String OFFER_1 = "offer_1";
50	private static final String OFFER_2 = "offer_2";
51	private static final String POLL = "poll";
52	private final Alphabet<String> sigma;
53	private final List<Word<String>> initialSuffixes;
54
55	public Example3() {	1✔
56	sigma = new GrowingMapAlphabet<>();	1✔
57	sigma.add(OFFER_1);	1✔
58	sigma.add(OFFER_2);	1✔
59	sigma.add(POLL);	1✔
60
61	initialSuffixes = new ArrayList<>();	1✔
62	for (String symbol : sigma) {	1✔
63	initialSuffixes.add(Word.fromLetter(symbol));	1✔
64	}	1✔
65	}	1✔
66
67	public static void main(String[] args) {
68	Example3 example = new Example3();	1✔
69	System.out.println("--");	1✔
70	System.out.println("Run experiment 1 (ReuseOracle):");	1✔
71	MealyMachine<?, String, ?, @Nullable String> result1 = example.runExperiment1();	1✔
72	System.out.println("--");	1✔
73	System.out.println("Run experiment 2:");	1✔
74	MealyMachine<?, String, ?, @Nullable String> result2 = example.runExperiment2();	1✔
75	System.out.println("--");	1✔
76	System.out.println("Model 1: " + result1.size() + " states");	1✔
77	System.out.println("Model 2: " + result2.size() + " states");	1✔
78
79	Word<String> sepWord;
80	sepWord = Automata.findSeparatingWord(result1, result2, example.sigma);	1✔
81
82	System.out.println("Difference (separating word)? " + sepWord);	1✔
83
84	/*
85	* Background knowledge: L^* creates an observation table with
86	* \|S\|=3,\|SA\|=7,\|E\|=3 so 30 MQs should be sufficient. The reuse filter
87	* should sink system states from SE to SAE so the upper part is the
88	* number of saved resets (=9).
89	*
90	* If the numbers don't match:
91	* https://github.com/LearnLib/learnlib/issues/5 (9 queries will be
92	* pumped by the reuse filter)
93	*/
94	}	1✔
95
96	/*
97	* A "normal" scenario without reuse filter technique.
98	*/
99	public MealyMachine<?, String, ?, @Nullable String> runExperiment1() {
100	// For each membership query a new instance of BoundedStringQueue will
101	// be created (normal learning scenario without filters)
102	FullMembershipQueryOracle oracle = new FullMembershipQueryOracle();	1✔
103
104	// construct L* instance (almost classic Mealy version)
105	// almost: we use words (Word<String>) in cells of the table
106	// instead of single outputs.
107	MealyLearner<String, @Nullable String> lstar;
108	lstar = new ExtensibleLStarMealyBuilder<String, @Nullable String>().withAlphabet(sigma)	1✔
109	.withInitialSuffixes(initialSuffixes)	1✔
110	.withOracle(oracle)	1✔
111	.create();	1✔
112
113	lstar.startLearning();	1✔
114	MealyMachine<?, String, ?, @Nullable String> result;
115	result = lstar.getHypothesisModel();	1✔
116
117	System.out.println("Resets: " + oracle.resets);	1✔
118	System.out.println("Symbols: " + oracle.symbols);	1✔
119
120	return result;	1✔
121	}
122
123	/*
124	* Scenario with reuse filter technique.
125	*/
126	public MealyMachine<?, String, ?, @Nullable String> runExperiment2() {
127	MySystemStateHandler ssh = new MySystemStateHandler();	1✔
128
129	// This time we use the reuse filter to avoid some resets and
130	// save execution of symbols
131	Supplier<ReuseCapableOracle<BoundedStringQueue, String, @Nullable String>> supplier = ReuseCapableImpl::new;	1✔
132	ReuseOracle<BoundedStringQueue, String, @Nullable String> reuseOracle =	1✔
133	new ReuseOracleBuilder<>(sigma, supplier).withSystemStateHandler(ssh).build();	1✔
134
135	// construct L* instance (almost classic Mealy version)
136	// almost: we use words (Word<String>) in cells of the table
137	// instead of single outputs.
138
139	MealyLearner<String, @Nullable String> lstar;
140	lstar = new ExtensibleLStarMealyBuilder<String, @Nullable String>().withAlphabet(sigma)	1✔
141	.withInitialSuffixes(initialSuffixes)	1✔
142	.withOracle(reuseOracle)	1✔
143	.create();	1✔
144
145	lstar.startLearning();	1✔
146
147	// get learned model
148	MealyMachine<?, String, ?, @Nullable String> result = lstar.getHypothesisModel();	1✔
149
150	// now invalidate all system states and count the number of disposed
151	// queues (equals number of resets)
152	reuseOracle.getReuseTree().disposeSystemStates();	1✔
153	ReuseCapableImpl reuseCapableOracle = (ReuseCapableImpl) reuseOracle.getReuseCapableOracle();	1✔
154	System.out.println("Resets: " + reuseCapableOracle.fullQueries);	1✔
155	System.out.println("Reused: " + reuseCapableOracle.reused);	1✔
156	System.out.println("Symbols: " + reuseCapableOracle.symbols);	1✔
157	// disposed = resets
158	System.out.println("Disposed: " + ssh.disposed);	1✔
159
160	return result;	1✔
161	}
162
163	private @Nullable String exec(BoundedStringQueue s, String input) {
164	switch (input) {	1✔
165	case OFFER_1:
166	case OFFER_2:
167	s.offer(input);	1✔
168	return "void";	1✔
169	case POLL:
170	return s.poll();	1✔
171	default:
172	throw new IllegalArgumentException("unknown input symbol");	×
173	}
174	}
175
176	/**
177	* For running the example this class could also be removed/ignored. It is only here for documentation purposes.
178	*/
179	static class MySystemStateHandler implements SystemStateHandler<BoundedStringQueue> {	1✔
180
181	private int disposed;
182
183	@Override
184	public void dispose(BoundedStringQueue state) {
185	/*
186	* When learning e.g. examples that involve databases, here would be
187	* a good point to remove database entities. In this example we just
188	* count the number of disposed (garbage collection inside the reuse
189	* tree) objects.
190	*/
191	disposed++;	1✔
192	}	1✔
193	}
194
195	/**
196	* An oracle that also does the reset by creating a new instance of the {@link BoundedStringQueue}.
197	*/
198	class FullMembershipQueryOracle implements MealyMembershipOracle<String, @Nullable String> {	1✔
199
200	private int resets;
201	private int symbols;
202
203	@Override
204	public void processQueries(Collection<? extends Query<String, Word<@Nullable String>>> queries) {
205	for (Query<String, Word<@Nullable String>> query : queries) {	1✔
206	resets++;	1✔
207	symbols += query.getInput().size();	1✔
208
209	BoundedStringQueue s = new BoundedStringQueue();	1✔
210
211	WordBuilder<@Nullable String> output = new WordBuilder<>();	1✔
212	for (String input : query.getInput()) {	1✔
213	output.add(exec(s, input));	1✔
214	}	1✔
215
216	query.answer(output.toWord().suffix(query.getSuffix().size()));	1✔
217	}	1✔
218	}	1✔
219	}
220
221	/**
222	* An implementation of the {@link ReuseCapableOracle} needed for the {@link ReuseOracle}. It only does reset by
223	* means of creating a new {@link BoundedStringQueue} instance in {@link ReuseCapableOracle#processQuery(Word)}.
224	*/
225	class ReuseCapableImpl implements ReuseCapableOracle<BoundedStringQueue, String, @Nullable String> {	1✔
226
227	private int reused;
228	private int fullQueries;
229	private int symbols;
230
231	@Override
232	public QueryResult<BoundedStringQueue, @Nullable String> continueQuery(Word<String> trace,
233	BoundedStringQueue s) {
234
235	reused++;	1✔
236	symbols += trace.size();	1✔
237
238	WordBuilder<@Nullable String> output = new WordBuilder<>();	1✔
239
240	for (String input : trace) {	1✔
241	output.add(exec(s, input));	1✔
242	}	1✔
243
244	QueryResult<BoundedStringQueue, @Nullable String> result;
245	result = new QueryResult<>(output.toWord(), s);	1✔
246
247	return result;	1✔
248	}
249
250	@Override
251	public QueryResult<BoundedStringQueue, @Nullable String> processQuery(Word<String> trace) {
252	fullQueries++;	1✔
253	symbols += trace.size();	1✔
254
255	// Suppose the reset would be a time-consuming operation
256	BoundedStringQueue s = new BoundedStringQueue();	1✔
257
258	WordBuilder<@Nullable String> output = new WordBuilder<>();	1✔
259
260	for (String input : trace) {	1✔
261	output.add(exec(s, input));	1✔
262	}	1✔
263
264	QueryResult<BoundedStringQueue, @Nullable String> result;
265	result = new QueryResult<>(output.toWord(), s);	1✔
266
267	return result;	1✔
268	}
269	}
270	}

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