001/* Copyright (C) 2013 TU Dortmund
002 * This file is part of LearnLib, http://www.learnlib.de/.
003 * 
004 * LearnLib is free software; you can redistribute it and/or
005 * modify it under the terms of the GNU Lesser General Public
006 * License version 3.0 as published by the Free Software Foundation.
007 * 
008 * LearnLib is distributed in the hope that it will be useful,
009 * but WITHOUT ANY WARRANTY; without even the implied warranty of
010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
011 * Lesser General Public License for more details.
012 * 
013 * You should have received a copy of the GNU Lesser General Public
014 * License along with LearnLib; if not, see
015 * <http://www.gnu.de/documents/lgpl.en.html>.
016 */
017package de.learnlib.examples.example2;
018
019import java.io.IOException;
020import java.io.Writer;
021import java.lang.reflect.InvocationTargetException;
022import java.lang.reflect.Method;
023import java.util.ArrayDeque;
024import java.util.ArrayList;
025import java.util.Arrays;
026import java.util.Deque;
027import java.util.List;
028import java.util.Random;
029
030import net.automatalib.automata.transout.MealyMachine;
031import net.automatalib.commons.dotutil.DOT;
032import net.automatalib.util.graphs.dot.GraphDOT;
033import net.automatalib.words.Alphabet;
034import net.automatalib.words.Word;
035import net.automatalib.words.impl.SimpleAlphabet;
036import de.learnlib.algorithms.lstargeneric.ce.ObservationTableCEXHandlers;
037import de.learnlib.algorithms.lstargeneric.closing.ClosingStrategies;
038import de.learnlib.algorithms.lstargeneric.mealy.ExtensibleLStarMealy;
039import de.learnlib.api.EquivalenceOracle.MealyEquivalenceOracle;
040import de.learnlib.api.LearningAlgorithm.MealyLearner;
041import de.learnlib.api.SUL;
042import de.learnlib.cache.Caches;
043import de.learnlib.eqtests.basic.mealy.RandomWalkEQOracle;
044import de.learnlib.experiments.Experiment.MealyExperiment;
045import de.learnlib.oracles.ResetCounterSUL;
046import de.learnlib.oracles.SULOracle;
047import de.learnlib.statistics.SimpleProfiler;
048import de.learnlib.statistics.StatisticSUL;
049
050/**
051 * This example shows how a model of a Java class can be learned using the SUL
052 * (system under learning) interfaces and the random walks equivalence test.
053 *
054 * @author falkhowar
055 */
056public class Example {
057
058    /*
059     * The BoundedStringQueue is the class of which we are going to 
060     * infer a model. It wraps an ordinary queue of Strings, limiting
061     * its size to MAX_SIZE (3). Once the queue is full, additional 
062     * offers will be ignored.
063     * <p>
064     * However, the implementation uses the underlying queue in a strange
065     * way as the model will reveal.
066     */
067    public static class BoundedStringQueue {
068
069        // capacity
070        public static final int MAX_SIZE = 3;
071        // storage
072        private Deque<String> data = new ArrayDeque<>(3);
073
074        // add a String to the queue if capacity allows
075        public void offer(String s) {
076            if (data.size() < MAX_SIZE) {
077                data.offerFirst(s);
078            }
079        }
080
081        // get next element from queue (null for empty queue)
082        public String poll() {
083            return data.poll();
084        }
085    }
086
087    /*
088     * We use the BSQInput class to wrap concrete method invocations
089     * and use these as alphabet symbols for the learning algorithm
090     */
091    public static class BSQInput {
092
093        // method to invoke
094        public final Method action;
095        
096        // method parameter values
097        public final Object[] data;
098
099        public BSQInput(Method action, Object[] data) {
100            this.action = action;
101            this.data = data;
102        }
103
104        // this will be used for printing when 
105        // logging or exporting automata
106        @Override
107        public String toString() {
108            return action.getName() + Arrays.toString(data);
109        }
110    }
111
112    /*
113     * The BSQAdapter 
114     * 
115     */
116    public static class BSQAdapter implements SUL<BSQInput, String> {
117
118        // system under learning
119        private BoundedStringQueue sul;
120
121        // reset the SUL
122        @Override
123        public void reset() {
124            // we just create a new instance
125            sul = new BoundedStringQueue();
126        }
127
128        // execute one input on the SUL
129        @Override
130        public String step(BSQInput in) {
131            try {
132                // invoke the method wrapped by in
133                Object ret = in.action.invoke(sul, in.data);
134                // make sure that we return a string
135                return ret == null ? "" : (String) ret;
136            } 
137            catch (IllegalAccessException | 
138                    IllegalArgumentException | 
139                    InvocationTargetException e) {
140                // This should never happen. In a real experiment
141                // this would be the point when we want to issue
142                // a warning or stop the learning.
143                return "err";
144            }
145        }
146    }
147
148    public static void main(String[] args) throws NoSuchMethodException, IOException {
149
150        // create learning alphabet
151        
152        // offer(a)
153        BSQInput offer_a = new BSQInput(BoundedStringQueue.class.getMethod(
154                "offer", new Class<?>[]{String.class}), new Object[]{"a"});
155
156        // offer(b)
157        BSQInput offer_b = new BSQInput(BoundedStringQueue.class.getMethod(
158                "offer", new Class<?>[]{String.class}), new Object[]{"b"});
159
160        // poll()
161        BSQInput poll = new BSQInput(BoundedStringQueue.class.getMethod(
162                "poll", new Class<?>[]{}), new Object[]{});
163
164        Alphabet<BSQInput> inputs = new SimpleAlphabet<>();
165        inputs.add(offer_a);
166        inputs.add(offer_b);
167        inputs.add(poll);
168
169        // create an oracle that can answer membership queries
170        // using the BSQAdapter
171        SUL<BSQInput,String> sul = new BSQAdapter();
172        
173        // oracle for counting queries wraps sul
174        StatisticSUL<BSQInput, String> statisticSul = new ResetCounterSUL<>("membership queries", sul);
175        
176        SUL<BSQInput,String> effectiveSul = statisticSul;
177        // use caching in order to avoid duplicate queries
178        effectiveSul = Caches.createSULCache(inputs, effectiveSul);
179        
180        SULOracle<BSQInput, String> mqOracle = new SULOracle<>(effectiveSul);
181
182        // create initial set of suffixes
183        List<Word<BSQInput>> suffixes = new ArrayList<>();
184        suffixes.add(Word.fromSymbols(offer_a));
185        suffixes.add(Word.fromSymbols(offer_b));
186        suffixes.add(Word.fromSymbols(poll));
187
188        // construct L* instance (almost classic Mealy version)
189        // almost: we use words (Word<String>) in cells of the table 
190        // instead of single outputs.
191        MealyLearner<BSQInput,String> lstar =
192                new ExtensibleLStarMealy<>(
193                inputs, // input alphabet
194                mqOracle, // mq oracle
195                suffixes, // initial suffixes
196                ObservationTableCEXHandlers.CLASSIC_LSTAR, // handling of counterexamples
197                ClosingStrategies.CLOSE_FIRST // always choose first unclosedness found 
198                );
199
200        // create random walks equivalence test
201        MealyEquivalenceOracle<BSQInput,String> randomWalks =
202                new RandomWalkEQOracle<>(
203                0.05, // reset SUL w/ this probability before a step 
204                10000, // max steps (overall)
205                false, // reset step count after counterexample 
206                new Random(46346293), // make results reproducible 
207                sul // system under learning
208                );
209
210        // construct a learning experiment from
211        // the learning algorithm and the random walks test.
212        // The experiment will execute the main loop of
213        // active learning
214        MealyExperiment<BSQInput,String> experiment =
215                new MealyExperiment<>(lstar, randomWalks, inputs);
216
217        // turn on time profiling
218        experiment.setProfile(true);
219
220        // enable logging of models
221        experiment.setLogModels(true);
222
223        // run experiment
224        experiment.run();
225
226        // get learned model
227        MealyMachine<?, BSQInput, ?, String> result = experiment.getFinalHypothesis();
228
229        // report results
230        System.out.println("-------------------------------------------------------");
231
232        // profiling
233        System.out.println(SimpleProfiler.getResults());
234
235        // learning statistics
236        System.out.println(experiment.getRounds().getSummary());
237        System.out.println(statisticSul.getStatisticalData().getSummary());
238
239        // model statistics
240        System.out.println("States: " + result.size());
241        System.out.println("Sigma: " + inputs.size());
242
243        // show model
244        System.out.println();
245        System.out.println("Model: ");
246        
247        GraphDOT.write(result, inputs, System.out); // may throw IOException!
248        Writer w = DOT.createDotWriter(true);
249        GraphDOT.write(result, inputs, w);
250        w.close();
251
252        System.out.println("-------------------------------------------------------");
253
254    }
255}