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

93.94

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

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

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

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