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

93.94

/algorithms/active/lstar/src/main/java/de/learnlib/algorithm/lstar/AbstractAutomatonLStar.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.lstar;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import de.learnlib.api.Resumable;
import de.learnlib.api.logging.Category;
import de.learnlib.api.oracle.MembershipOracle;
import de.learnlib.api.query.DefaultQuery;
import de.learnlib.datastructure.observationtable.ObservationTable;
import de.learnlib.datastructure.observationtable.Row;
import net.automatalib.SupportsGrowingAlphabet;
import net.automatalib.alphabet.Alphabet;
import net.automatalib.automaton.MutableDeterministic;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * Abstract base class for algorithms that produce (subclasses of) {@link MutableDeterministic} automata.
 * <p>
 * This class provides the L*-style hypothesis construction. Implementing classes solely have to specify how state and
 * transition properties should be derived.
 *
 * @param <A>
 *         automaton type, must be a subclass of {@link MutableDeterministic}
 * @param <I>
 *         input symbol type
 * @param <D>
 *         output domain type
 * @param <SP>
 *         state property type
 * @param <TP>
 *         transition property type
 */
public abstract class AbstractAutomatonLStar<A, I, D, S, T, SP, TP, AI extends MutableDeterministic<S, I, T, SP, TP> & SupportsGrowingAlphabet<I>>
        extends AbstractLStar<A, I, D> implements Resumable<AutomatonLStarState<I, D, AI, S>> {

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

    protected AI internalHyp;
    protected List<StateInfo<S, I>> stateInfos = new ArrayList<>();

    /**
     * Constructor.
     *
     * @param alphabet
     *         the learning alphabet
     * @param oracle
     *         the learning oracle
     */
    protected AbstractAutomatonLStar(Alphabet<I> alphabet, MembershipOracle<I, D> oracle, AI internalHyp) {
        super(alphabet, oracle);
        this.internalHyp = internalHyp;
        internalHyp.clear();
    }

    @Override
    public final void startLearning() {
        super.startLearning();
        updateInternalHypothesis();
    }

    /**
     * Performs the L*-style hypothesis construction. For creating states and transitions, the {@link
     * #stateProperty(ObservationTable, Row)} and {@link #transitionProperty(ObservationTable, Row, int)} methods are
     * used to derive the respective properties.
     */
    @SuppressWarnings("argument.type.incompatible")
    // all added nulls to stateInfos will be correctly set to non-null values
    protected void updateInternalHypothesis() {
        if (!table.isInitialized()) {
            throw new IllegalStateException("Cannot update internal hypothesis: not initialized");
        }

        int oldStates = internalHyp.size();
        int numDistinct = table.numberOfDistinctRows();

        int newStates = numDistinct - oldStates;

        stateInfos.addAll(Collections.nCopies(newStates, null));

        // TODO: Is there a quicker way than iterating over *all* rows?
        // FIRST PASS: Create new hypothesis states
        for (Row<I> sp : table.getShortPrefixRows()) {
            int id = sp.getRowContentId();
            StateInfo<S, I> info = stateInfos.get(id);
            if (info != null) {
                // State from previous hypothesis, property might have changed
                if (info.getRow() == sp) {
                    internalHyp.setStateProperty(info.getState(), stateProperty(table, sp));
                }
                continue;
            }

            S state = createState(id == 0, sp);

            stateInfos.set(id, new StateInfo<>(sp, state));
        }

        // SECOND PASS: Create hypothesis transitions
        for (StateInfo<S, I> info : stateInfos) {
            Row<I> sp = info.getRow();
            S state = info.getState();

            for (int i = 0; i < alphabet.size(); i++) {
                I input = alphabet.getSymbol(i);

                Row<I> succ = sp.getSuccessor(i);
                int succId = succ.getRowContentId();

                S succState = stateInfos.get(succId).getState();

                setTransition(state, input, succState, sp, i);
            }
        }
    }

    /**
     * Derives a state property from the corresponding row.
     *
     * @param table
     *         the current observation table
     * @param stateRow
     *         the row for which the state is created
     *
     * @return the state property of the corresponding state
     */
    protected abstract SP stateProperty(ObservationTable<I, D> table, Row<I> stateRow);

    protected S createState(boolean initial, Row<I> row) {
        SP prop = stateProperty(table, row);
        if (initial) {
            return internalHyp.addInitialState(prop);
        }
        return internalHyp.addState(prop);
    }

    protected void setTransition(S from, I input, S to, Row<I> fromRow, int inputIdx) {
        TP prop = transitionProperty(table, fromRow, inputIdx);
        internalHyp.setTransition(from, input, to, prop);
    }

    /**
     * Derives a transition property from the corresponding transition.
     * <p>
     * N.B.: Not the transition row is passed to this method, but the row for the outgoing state. The transition row can
     * be retrieved using {@link Row#getSuccessor(int)}.
     *
     * @param stateRow
     *         the row for the source state
     * @param inputIdx
     *         the index of the input symbol to consider
     *
     * @return the transition property of the corresponding transition
     */
    protected abstract TP transitionProperty(ObservationTable<I, D> table, Row<I> stateRow, int inputIdx);

    @Override
    protected final void doRefineHypothesis(DefaultQuery<I, D> ceQuery) {
        refineHypothesisInternal(ceQuery);
        updateInternalHypothesis();
    }

    protected void refineHypothesisInternal(DefaultQuery<I, D> ceQuery) {
        super.doRefineHypothesis(ceQuery);
    }

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

        this.internalHyp.addAlphabetSymbol(symbol);

        if (this.table.isInitialized()) {
            this.updateInternalHypothesis();
        }
    }

    @Override
    public AutomatonLStarState<I, D, AI, S> suspend() {
        return new AutomatonLStarState<>(table, internalHyp, stateInfos);
    }

    @Override
    public void resume(AutomatonLStarState<I, D, AI, S> state) {
        this.table = state.getObservationTable();
        this.internalHyp = state.getHypothesis();
        this.stateInfos = state.getStateInfos();

        final Alphabet<I> oldAlphabet = this.table.getInputAlphabet();
        if (!oldAlphabet.equals(this.alphabet)) {
            LOGGER.warn(Category.DATASTRUCTURE,
                        "The current alphabet '{}' differs from the resumed alphabet '{}'. Future behavior may be inconsistent",
                        this.alphabet,
                        oldAlphabet);
        }
    }

    static final class StateInfo<S, I> {

        private final Row<I> row;
        private final S state;

        StateInfo(Row<I> row, S state) {
            this.row = row;
            this.state = state;
        }

        public Row<I> getRow() {
            return row;
        }

        public S getState() {
            return state;
        }

        // IDENTITY SEMANTICS!
    }
}

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.lstar;
17
18	import java.util.ArrayList;
19	import java.util.Collections;
20	import java.util.List;
21
22	import de.learnlib.api.Resumable;
23	import de.learnlib.api.logging.Category;
24	import de.learnlib.api.oracle.MembershipOracle;
25	import de.learnlib.api.query.DefaultQuery;
26	import de.learnlib.datastructure.observationtable.ObservationTable;
27	import de.learnlib.datastructure.observationtable.Row;
28	import net.automatalib.SupportsGrowingAlphabet;
29	import net.automatalib.alphabet.Alphabet;
30	import net.automatalib.automaton.MutableDeterministic;
31	import org.slf4j.Logger;
32	import org.slf4j.LoggerFactory;
33
34	/**
35	* Abstract base class for algorithms that produce (subclasses of) {@link MutableDeterministic} automata.
36	* <p>
37	* This class provides the L*-style hypothesis construction. Implementing classes solely have to specify how state and
38	* transition properties should be derived.
39	*
40	* @param <A>
41	* automaton type, must be a subclass of {@link MutableDeterministic}
42	* @param <I>
43	* input symbol type
44	* @param <D>
45	* output domain type
46	* @param <SP>
47	* state property type
48	* @param <TP>
49	* transition property type
50	*/
51	public abstract class AbstractAutomatonLStar<A, I, D, S, T, SP, TP, AI extends MutableDeterministic<S, I, T, SP, TP> & SupportsGrowingAlphabet<I>>
52	extends AbstractLStar<A, I, D> implements Resumable<AutomatonLStarState<I, D, AI, S>> {
53
54	private static final Logger LOGGER = LoggerFactory.getLogger(AbstractAutomatonLStar.class);	2✔
55
56	protected AI internalHyp;
57	protected List<StateInfo<S, I>> stateInfos = new ArrayList<>();	2✔
58
59	/**
60	* Constructor.
61	*
62	* @param alphabet
63	* the learning alphabet
64	* @param oracle
65	* the learning oracle
66	*/
67	protected AbstractAutomatonLStar(Alphabet<I> alphabet, MembershipOracle<I, D> oracle, AI internalHyp) {
68	super(alphabet, oracle);	2✔
69	this.internalHyp = internalHyp;	2✔
70	internalHyp.clear();	2✔
71	}	2✔
72
73	@Override
74	public final void startLearning() {
75	super.startLearning();	2✔
76	updateInternalHypothesis();	2✔
77	}	2✔
78
79	/**
80	* Performs the L*-style hypothesis construction. For creating states and transitions, the {@link
81	* #stateProperty(ObservationTable, Row)} and {@link #transitionProperty(ObservationTable, Row, int)} methods are
82	* used to derive the respective properties.
83	*/
84	@SuppressWarnings("argument.type.incompatible")
85	// all added nulls to stateInfos will be correctly set to non-null values
86	protected void updateInternalHypothesis() {
87	if (!table.isInitialized()) {	2✔
88	throw new IllegalStateException("Cannot update internal hypothesis: not initialized");	×
89	}
90
91	int oldStates = internalHyp.size();	2✔
92	int numDistinct = table.numberOfDistinctRows();	2✔
93
94	int newStates = numDistinct - oldStates;	2✔
95
96	stateInfos.addAll(Collections.nCopies(newStates, null));	2✔
97
98	// TODO: Is there a quicker way than iterating over all rows?
99	// FIRST PASS: Create new hypothesis states
100	for (Row<I> sp : table.getShortPrefixRows()) {	2✔
101	int id = sp.getRowContentId();	2✔
102	StateInfo<S, I> info = stateInfos.get(id);	2✔
103	if (info != null) {	2✔
104	// State from previous hypothesis, property might have changed
105	if (info.getRow() == sp) {	2✔
106	internalHyp.setStateProperty(info.getState(), stateProperty(table, sp));	2✔
107	}
108	continue;
109	}
110
111	S state = createState(id == 0, sp);	2✔
112
113	stateInfos.set(id, new StateInfo<>(sp, state));	2✔
114	}	2✔
115
116	// SECOND PASS: Create hypothesis transitions
117	for (StateInfo<S, I> info : stateInfos) {	2✔
118	Row<I> sp = info.getRow();	2✔
119	S state = info.getState();	2✔
120
121	for (int i = 0; i < alphabet.size(); i++) {	2✔
122	I input = alphabet.getSymbol(i);	2✔
123
124	Row<I> succ = sp.getSuccessor(i);	2✔
125	int succId = succ.getRowContentId();	2✔
126
127	S succState = stateInfos.get(succId).getState();	2✔
128
129	setTransition(state, input, succState, sp, i);	2✔
130	}
131	}	2✔
132	}	2✔
133
134	/**
135	* Derives a state property from the corresponding row.
136	*
137	* @param table
138	* the current observation table
139	* @param stateRow
140	* the row for which the state is created
141	*
142	* @return the state property of the corresponding state
143	*/
144	protected abstract SP stateProperty(ObservationTable<I, D> table, Row<I> stateRow);
145
146	protected S createState(boolean initial, Row<I> row) {
147	SP prop = stateProperty(table, row);	2✔
148	if (initial) {	2✔
149	return internalHyp.addInitialState(prop);	2✔
150	}
151	return internalHyp.addState(prop);	2✔
152	}
153
154	protected void setTransition(S from, I input, S to, Row<I> fromRow, int inputIdx) {
155	TP prop = transitionProperty(table, fromRow, inputIdx);	2✔
156	internalHyp.setTransition(from, input, to, prop);	2✔
157	}	2✔
158
159	/**
160	* Derives a transition property from the corresponding transition.
161	* <p>
162	* N.B.: Not the transition row is passed to this method, but the row for the outgoing state. The transition row can
163	* be retrieved using {@link Row#getSuccessor(int)}.
164	*
165	* @param stateRow
166	* the row for the source state
167	* @param inputIdx
168	* the index of the input symbol to consider
169	*
170	* @return the transition property of the corresponding transition
171	*/
172	protected abstract TP transitionProperty(ObservationTable<I, D> table, Row<I> stateRow, int inputIdx);
173
174	@Override
175	protected final void doRefineHypothesis(DefaultQuery<I, D> ceQuery) {
176	refineHypothesisInternal(ceQuery);	2✔
177	updateInternalHypothesis();	2✔
178	}	2✔
179
180	protected void refineHypothesisInternal(DefaultQuery<I, D> ceQuery) {
181	super.doRefineHypothesis(ceQuery);	×
182	}	×
183
184	@Override
185	public void addAlphabetSymbol(I symbol) {
186	super.addAlphabetSymbol(symbol);	2✔
187
188	this.internalHyp.addAlphabetSymbol(symbol);	2✔
189
190	if (this.table.isInitialized()) {	2✔
191	this.updateInternalHypothesis();	2✔
192	}
193	}	2✔
194
195	@Override
196	public AutomatonLStarState<I, D, AI, S> suspend() {
197	return new AutomatonLStarState<>(table, internalHyp, stateInfos);	2✔
198	}
199
200	@Override
201	public void resume(AutomatonLStarState<I, D, AI, S> state) {
202	this.table = state.getObservationTable();	2✔
203	this.internalHyp = state.getHypothesis();	2✔
204	this.stateInfos = state.getStateInfos();	2✔
205
206	final Alphabet<I> oldAlphabet = this.table.getInputAlphabet();	2✔
207	if (!oldAlphabet.equals(this.alphabet)) {	2✔
208	LOGGER.warn(Category.DATASTRUCTURE,	×
209	"The current alphabet '{}' differs from the resumed alphabet '{}'. Future behavior may be inconsistent",
210	this.alphabet,
211	oldAlphabet);
212	}
213	}	2✔
214
215	static final class StateInfo<S, I> {
216
217	private final Row<I> row;
218	private final S state;
219
220	StateInfo(Row<I> row, S state) {	2✔
221	this.row = row;	2✔
222	this.state = state;	2✔
223	}	2✔
224
225	public Row<I> getRow() {
226	return row;	2✔
227	}
228
229	public S getState() {
230	return state;	2✔
231	}
232
233	// IDENTITY SEMANTICS!
234	}
235	}

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