6412002873

Committed 04 Oct 2023 10:05PM UTC coverage: 92.303% (+0.02%) from 92.282%

Build # 6412002873

Build Type

push

github

Committed by

mtf90

Commit Message

further tweak versions

* downgrade maven-javadoc-plugin version because it (for whatever reason) doesn't work on Java 11+
* update previously missed doc skin version

Run Details

11573 of 12538 relevant lines covered (92.3%)

1.67 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.48

/oracles/membership-oracles/src/main/java/de/learnlib/oracle/membership/AbstractSULOmegaOracle.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.oracle.membership;

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

import de.learnlib.api.ObservableSUL;
import de.learnlib.api.SUL;
import de.learnlib.api.oracle.MembershipOracle.MealyMembershipOracle;
import de.learnlib.api.oracle.OmegaMembershipOracle;
import de.learnlib.api.oracle.OmegaMembershipOracle.MealyOmegaMembershipOracle;
import de.learnlib.api.query.OmegaQuery;
import net.automatalib.commons.util.Pair;
import net.automatalib.words.Word;
import net.automatalib.words.WordBuilder;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * An omega membership oracle for an {@link ObservableSUL}.
 * <p>
 * The behavior is similar to a {@link SULOracle}, except that this class answers {@link OmegaQuery}s.
 * <p>
 * After some symbols (i.e. after {@link OmegaQuery#getPrefix()}, and after each {@link OmegaQuery#getLoop()}) the state
 * of the {@link ObservableSUL} is retrieved, and used to answer the query.
 * <p>
 * This class is <b>not</b> thread-safe.
 *
 * @param <S>
 *         the state type of the {@link ObservableSUL}
 * @param <I>
 *         the input type
 * @param <O>
 *         the output type
 * @param <Q>
 *         the state information type that is used to answer {@link OmegaQuery}s
 *
 * @author Jeroen Meijer
 */
public abstract class AbstractSULOmegaOracle<S extends Object, I, O, Q> implements MealyOmegaMembershipOracle<Q, I, O> {

    private final ObservableSUL<S, I, O> sul;

    protected AbstractSULOmegaOracle(ObservableSUL<S, I, O> sul) {
        this.sul = sul;
    }

    /**
     * Gets the {@link ObservableSUL}.
     *
     * @return the {@link ObservableSUL}.
     */
    public ObservableSUL<S, I, O> getSul() {
        return sul;
    }

    @Override
    public void processQueries(Collection<? extends OmegaQuery<I, Word<O>>> queries) {
        for (OmegaQuery<I, Word<O>> q : queries) {
            final Pair<@Nullable Word<O>, Integer> output = answerQuery(q.getPrefix(), q.getLoop(), q.getRepeat());
            q.answer(output.getFirst(), output.getSecond());
        }
    }

    protected abstract Q getQueryState(ObservableSUL<S, I, O> sul);

    @Override
    public Pair<@Nullable Word<O>, Integer> answerQuery(Word<I> prefix, Word<I> loop, int repeat) {
        assert repeat > 0;
        sul.pre();
        try {
            final int traceLength = prefix.length() + loop.length() * repeat;
            final WordBuilder<I> inputBuilder = new WordBuilder<>(traceLength, prefix);
            final WordBuilder<O> outputBuilder = new WordBuilder<>(traceLength);
            final List<Q> states = new ArrayList<>(repeat + 1);

            for (int i = 0; i < prefix.length(); i++) {
                outputBuilder.append(sul.step(prefix.getSymbol(i)));
            }
            states.add(getQueryState(sul));

            for (int i = 0; i < repeat; i++) {
                inputBuilder.append(loop);
                for (int j = 0; j < loop.length(); j++) {
                    outputBuilder.append(sul.step(loop.getSymbol(j)));
                }
                final Q nextState = getQueryState(sul);

                int prefixLength = prefix.length();
                for (Q q: states) {
                    if (isSameState(inputBuilder.toWord(), nextState, inputBuilder.toWord(0, prefixLength), q)) {
                        return Pair.of(outputBuilder.toWord(), i + 1);
                    }
                    prefixLength += loop.length();
                }
                states.add(nextState);
            }

            return Pair.of(null, -1);
        } finally {
            sul.post();
        }
    }

    @Override
    public MealyMembershipOracle<I, O> getMembershipOracle() {
        return new SULOracle<>(sul);
    }

    /**
     * Creates a new {@link AbstractSULOmegaOracle}, while making sure the invariants of the {@link ObservableSUL} are
     * satisfied.
     *
     * @param sul the {@link ObservableSUL} to wrap around.
     * @param deepCopies whether to test for state equivalence directly on the retrieved state.
     *
     * @param <S> the state type
     * @param <I> the input type
     * @param <O> the output type
     *
     * @return the {@link AbstractSULOmegaOracle}.
     */
    public static <S extends Object, I, O> AbstractSULOmegaOracle<S, I, O, ?> newOracle(ObservableSUL<S, I, O> sul,
                                                                                        boolean deepCopies) {
        final AbstractSULOmegaOracle<S, I, O, ?> abstractSulOmegaOracle;
        if (deepCopies) {
            if (!sul.deepCopies()) {
                throw new IllegalArgumentException("SUL can not make deep copies of states.");
            } else {
                abstractSulOmegaOracle = new DeepCopySULOmegaOracle<>(sul);
            }
        } else {
            if (!sul.canFork()) {
                throw new IllegalArgumentException("SUL must be forkable.");
            } else {
                abstractSulOmegaOracle = new ShallowCopySULOmegaOracle<>(sul);
            }
        }

        return abstractSulOmegaOracle;
    }

    /**
     * Creates a new {@link AbstractSULOmegaOracle} that assumes the {@link SUL} can not make deep copies.
     *
     * @see #newOracle(ObservableSUL, boolean)
     *
     * @param <S> the state type
     * @param <I> the input type
     * @param <O> the output type
     */
    public static <S extends Object, I, O> AbstractSULOmegaOracle<S, I, O, ?> newOracle(ObservableSUL<S, I, O> sul) {
        return newOracle(sul, !sul.canFork());
    }

    /**
     * A {@link AbstractSULOmegaOracle} that uses {@link Object#hashCode()}, and {@link Object#equals(Object)} to test
     * for state equivalence. When the hash codes of two states are equal this class will use two access sequences to
     * move two {@link ObservableSUL}s to those states and perform an equality check.
     * <p>
     * The state information used to answer {@link OmegaQuery}s is of type {@link Integer}. The values of those integers
     * are actually hash codes of states of the {@link ObservableSUL}.
     *
     * @author Jeroen Meijer
     *
     * @param <S> the state type
     * @param <I> the input type
     * @param <O> the output type
     */
    private static final class ShallowCopySULOmegaOracle<S extends Object, I, O>
            extends AbstractSULOmegaOracle<S, I, O, Integer> {

        /**
         * A forked {@link SUL} is necessary when we need to step to two particular states at the same time.
         */
        private final ObservableSUL<S, I, O> forkedSUL;

        /**
         * Constructs a new {@link ShallowCopySULOmegaOracle}, use {@link #newOracle(ObservableSUL)} to create an
         * instance. This method makes sure the invariants of the {@link ObservableSUL} are satisfied (i.e., the {@link
         * ObservableSUL} must be forkable, i.e. ({@code {@link SUL#canFork()} == true}).
         *
         * @param sul the SUL
         */
        ShallowCopySULOmegaOracle(ObservableSUL<S, I, O> sul) {
            super(sul);
            assert sul.canFork();
            forkedSUL = sul.fork();
        }

        /**
         * Returns the state as a hash code.
         *
         * @param sul the {@link ObservableSUL} to retrieve the current state from.
         *
         * @return the hash code of the state.
         */
        @Override
        protected Integer getQueryState(ObservableSUL<S, I, O> sul) {
            return sul.getState().hashCode();
        }

        /**
         * Test for state equivalence, by means of {@link Object#hashCode()}, and {@link Object#equals(Object)}.
         *
         * @see OmegaMembershipOracle#isSameState(Word, Object, Word, Object)
         *
         * @return whether the following conditions hold:
         *  1. the hash codes are the same, i.e. {@code s1.equals(s2)}, and
         *  2. the two access sequences lead to the same state.
         */
        @Override
        public boolean isSameState(Word<I> input1, Integer s1, Word<I> input2, Integer s2) {
            if (!s1.equals(s2)) {
                return false;
            } else {
                // in this case the hash codes are equal, now we must check if we accidentally had a hash-collision.
                final ObservableSUL<S, I, O> sul1 = getSul();
                final ObservableSUL<S, I, O> sul2 = forkedSUL;

                // assert sul1 is already in the correct state
                assert s1.equals(sul1.getState().hashCode());

                sul2.pre();
                try {
                    // step through the second SUL
                    for (I sym : input2) {
                        sul2.step(sym);
                    }

                    assert sul1.getState().hashCode() == sul2.getState().hashCode();
                    assert s2.equals(sul2.getState().hashCode());

                    // check for state equivalence
                    return sul1.getState().equals(sul2.getState());
                } finally {
                    sul2.post();
                }
            }
        }
    }

    /**
     * A {@link AbstractSULOmegaOracle} for states that are deep copies. When a state is a deep copy, this means we can
     * simply invoke {@link Object#equals(Object)} on both.
     * <p>
     * The state information used to answer {@link OmegaQuery}s is of type {@link S}.
     *
     * @author Jeroen Meijer
     *
     * @param <S> the state type
     * @param <I> the input type
     * @param <O> the output type
     */
    private static final class DeepCopySULOmegaOracle<S extends Object, I, O>
            extends AbstractSULOmegaOracle<S, I, O, S> {

        /**
         * Constructs a {@link DeepCopySULOmegaOracle}, use {@link #newOracle(ObservableSUL, boolean)} to create an
         * actual instance. This method will make sure the invariants of the {@link ObservableSUL} are satisfied.
         *
         * @param sul the {@link ObservableSUL}.
         */
        DeepCopySULOmegaOracle(ObservableSUL<S, I, O> sul) {
            super(sul);
        }

        /**
         * Returns the current state of the {@link ObservableSUL}.
         *
         * @param sul the {@link ObservableSUL} to retrieve the current state from.
         *
         * @return the current state.
         */
        @Override
        protected S getQueryState(ObservableSUL<S, I, O> sul) {
            return sul.getState();
        }

        /**
         * Test for state equivalence using {@link Object#equals(Object)}.
         *
         * @see OmegaMembershipOracle#isSameState(Word, Object, Word, Object)
         */
        @Override
        public boolean isSameState(Word<I> input1, S s1, Word<I> input2, S s2) {
            return s1.equals(s2);
        }
    }
}

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.oracle.membership;
17
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.List;
21
22	import de.learnlib.api.ObservableSUL;
23	import de.learnlib.api.SUL;
24	import de.learnlib.api.oracle.MembershipOracle.MealyMembershipOracle;
25	import de.learnlib.api.oracle.OmegaMembershipOracle;
26	import de.learnlib.api.oracle.OmegaMembershipOracle.MealyOmegaMembershipOracle;
27	import de.learnlib.api.query.OmegaQuery;
28	import net.automatalib.commons.util.Pair;
29	import net.automatalib.words.Word;
30	import net.automatalib.words.WordBuilder;
31	import org.checkerframework.checker.nullness.qual.Nullable;
32
33	/**
34	* An omega membership oracle for an {@link ObservableSUL}.
35	* <p>
36	* The behavior is similar to a {@link SULOracle}, except that this class answers {@link OmegaQuery}s.
37	* <p>
38	* After some symbols (i.e. after {@link OmegaQuery#getPrefix()}, and after each {@link OmegaQuery#getLoop()}) the state
39	* of the {@link ObservableSUL} is retrieved, and used to answer the query.
40	* <p>
41	* This class is <b>not</b> thread-safe.
42	*
43	* @param <S>
44	* the state type of the {@link ObservableSUL}
45	* @param <I>
46	* the input type
47	* @param <O>
48	* the output type
49	* @param <Q>
50	* the state information type that is used to answer {@link OmegaQuery}s
51	*
52	* @author Jeroen Meijer
53	*/
54	public abstract class AbstractSULOmegaOracle<S extends Object, I, O, Q> implements MealyOmegaMembershipOracle<Q, I, O> {	2✔
55
56	private final ObservableSUL<S, I, O> sul;
57
58	protected AbstractSULOmegaOracle(ObservableSUL<S, I, O> sul) {	2✔
59	this.sul = sul;	2✔
60	}	2✔
61
62	/**
63	* Gets the {@link ObservableSUL}.
64	*
65	* @return the {@link ObservableSUL}.
66	*/
67	public ObservableSUL<S, I, O> getSul() {
68	return sul;	2✔
69	}
70
71	@Override
72	public void processQueries(Collection<? extends OmegaQuery<I, Word<O>>> queries) {
73	for (OmegaQuery<I, Word<O>> q : queries) {	2✔
74	final Pair<@Nullable Word<O>, Integer> output = answerQuery(q.getPrefix(), q.getLoop(), q.getRepeat());	2✔
75	q.answer(output.getFirst(), output.getSecond());	2✔
76	}	2✔
77	}	2✔
78
79	protected abstract Q getQueryState(ObservableSUL<S, I, O> sul);
80
81	@Override
82	public Pair<@Nullable Word<O>, Integer> answerQuery(Word<I> prefix, Word<I> loop, int repeat) {
83	assert repeat > 0;	2✔
84	sul.pre();	2✔
85	try {
86	final int traceLength = prefix.length() + loop.length() * repeat;	2✔
87	final WordBuilder<I> inputBuilder = new WordBuilder<>(traceLength, prefix);	2✔
88	final WordBuilder<O> outputBuilder = new WordBuilder<>(traceLength);	2✔
89	final List<Q> states = new ArrayList<>(repeat + 1);	2✔
90
91	for (int i = 0; i < prefix.length(); i++) {	2✔
92	outputBuilder.append(sul.step(prefix.getSymbol(i)));	2✔
93	}
94	states.add(getQueryState(sul));	2✔
95
96	for (int i = 0; i < repeat; i++) {	2✔
97	inputBuilder.append(loop);	2✔
98	for (int j = 0; j < loop.length(); j++) {	2✔
99	outputBuilder.append(sul.step(loop.getSymbol(j)));	2✔
100	}
101	final Q nextState = getQueryState(sul);	2✔
102
103	int prefixLength = prefix.length();	2✔
104	for (Q q: states) {	2✔
105	if (isSameState(inputBuilder.toWord(), nextState, inputBuilder.toWord(0, prefixLength), q)) {	2✔
106	return Pair.of(outputBuilder.toWord(), i + 1);	2✔
107	}
108	prefixLength += loop.length();	2✔
109	}	2✔
110	states.add(nextState);	2✔
111	}
112
113	return Pair.of(null, -1);	2✔
114	} finally {
115	sul.post();	2✔
116	}
117	}
118
119	@Override
120	public MealyMembershipOracle<I, O> getMembershipOracle() {
121	return new SULOracle<>(sul);	×
122	}
123
124	/**
125	* Creates a new {@link AbstractSULOmegaOracle}, while making sure the invariants of the {@link ObservableSUL} are
126	* satisfied.
127	*
128	* @param sul the {@link ObservableSUL} to wrap around.
129	* @param deepCopies whether to test for state equivalence directly on the retrieved state.
130	*
131	* @param <S> the state type
132	* @param <I> the input type
133	* @param <O> the output type
134	*
135	* @return the {@link AbstractSULOmegaOracle}.
136	*/
137	public static <S extends Object, I, O> AbstractSULOmegaOracle<S, I, O, ?> newOracle(ObservableSUL<S, I, O> sul,
138	boolean deepCopies) {
139	final AbstractSULOmegaOracle<S, I, O, ?> abstractSulOmegaOracle;
140	if (deepCopies) {	2✔
141	if (!sul.deepCopies()) {	2✔
142	throw new IllegalArgumentException("SUL can not make deep copies of states.");	2✔
143	} else {
144	abstractSulOmegaOracle = new DeepCopySULOmegaOracle<>(sul);	2✔
145	}
146	} else {
147	if (!sul.canFork()) {	2✔
148	throw new IllegalArgumentException("SUL must be forkable.");	2✔
149	} else {
150	abstractSulOmegaOracle = new ShallowCopySULOmegaOracle<>(sul);	2✔
151	}
152	}
153
154	return abstractSulOmegaOracle;	2✔
155	}
156
157	/**
158	* Creates a new {@link AbstractSULOmegaOracle} that assumes the {@link SUL} can not make deep copies.
159	*
160	* @see #newOracle(ObservableSUL, boolean)
161	*
162	* @param <S> the state type
163	* @param <I> the input type
164	* @param <O> the output type
165	*/
166	public static <S extends Object, I, O> AbstractSULOmegaOracle<S, I, O, ?> newOracle(ObservableSUL<S, I, O> sul) {
167	return newOracle(sul, !sul.canFork());	2✔
168	}
169
170	/**
171	* A {@link AbstractSULOmegaOracle} that uses {@link Object#hashCode()}, and {@link Object#equals(Object)} to test
172	* for state equivalence. When the hash codes of two states are equal this class will use two access sequences to
173	* move two {@link ObservableSUL}s to those states and perform an equality check.
174	* <p>
175	* The state information used to answer {@link OmegaQuery}s is of type {@link Integer}. The values of those integers
176	* are actually hash codes of states of the {@link ObservableSUL}.
177	*
178	* @author Jeroen Meijer
179	*
180	* @param <S> the state type
181	* @param <I> the input type
182	* @param <O> the output type
183	*/
184	private static final class ShallowCopySULOmegaOracle<S extends Object, I, O>	2✔
185	extends AbstractSULOmegaOracle<S, I, O, Integer> {
186
187	/**
188	* A forked {@link SUL} is necessary when we need to step to two particular states at the same time.
189	*/
190	private final ObservableSUL<S, I, O> forkedSUL;
191
192	/**
193	* Constructs a new {@link ShallowCopySULOmegaOracle}, use {@link #newOracle(ObservableSUL)} to create an
194	* instance. This method makes sure the invariants of the {@link ObservableSUL} are satisfied (i.e., the {@link
195	* ObservableSUL} must be forkable, i.e. ({@code {@link SUL#canFork()} == true}).
196	*
197	* @param sul the SUL
198	*/
199	ShallowCopySULOmegaOracle(ObservableSUL<S, I, O> sul) {
200	super(sul);	2✔
201	assert sul.canFork();	2✔
202	forkedSUL = sul.fork();	2✔
203	}	2✔
204
205	/**
206	* Returns the state as a hash code.
207	*
208	* @param sul the {@link ObservableSUL} to retrieve the current state from.
209	*
210	* @return the hash code of the state.
211	*/
212	@Override
213	protected Integer getQueryState(ObservableSUL<S, I, O> sul) {
214	return sul.getState().hashCode();	2✔
215	}
216
217	/**
218	* Test for state equivalence, by means of {@link Object#hashCode()}, and {@link Object#equals(Object)}.
219	*
220	* @see OmegaMembershipOracle#isSameState(Word, Object, Word, Object)
221	*
222	* @return whether the following conditions hold:
223	* 1. the hash codes are the same, i.e. {@code s1.equals(s2)}, and
224	* 2. the two access sequences lead to the same state.
225	*/
226	@Override
227	public boolean isSameState(Word<I> input1, Integer s1, Word<I> input2, Integer s2) {
228	if (!s1.equals(s2)) {	2✔
229	return false;	2✔
230	} else {
231	// in this case the hash codes are equal, now we must check if we accidentally had a hash-collision.
232	final ObservableSUL<S, I, O> sul1 = getSul();	2✔
233	final ObservableSUL<S, I, O> sul2 = forkedSUL;	2✔
234
235	// assert sul1 is already in the correct state
236	assert s1.equals(sul1.getState().hashCode());	2✔
237
238	sul2.pre();	2✔
239	try {
240	// step through the second SUL
241	for (I sym : input2) {	2✔
242	sul2.step(sym);	2✔
243	}	2✔
244
245	assert sul1.getState().hashCode() == sul2.getState().hashCode();	2✔
246	assert s2.equals(sul2.getState().hashCode());	2✔
247
248	// check for state equivalence
249	return sul1.getState().equals(sul2.getState());	2✔
250	} finally {
251	sul2.post();	2✔
252	}
253	}
254	}
255	}
256
257	/**
258	* A {@link AbstractSULOmegaOracle} for states that are deep copies. When a state is a deep copy, this means we can
259	* simply invoke {@link Object#equals(Object)} on both.
260	* <p>
261	* The state information used to answer {@link OmegaQuery}s is of type {@link S}.
262	*
263	* @author Jeroen Meijer
264	*
265	* @param <S> the state type
266	* @param <I> the input type
267	* @param <O> the output type
268	*/
269	private static final class DeepCopySULOmegaOracle<S extends Object, I, O>
270	extends AbstractSULOmegaOracle<S, I, O, S> {
271
272	/**
273	* Constructs a {@link DeepCopySULOmegaOracle}, use {@link #newOracle(ObservableSUL, boolean)} to create an
274	* actual instance. This method will make sure the invariants of the {@link ObservableSUL} are satisfied.
275	*
276	* @param sul the {@link ObservableSUL}.
277	*/
278	DeepCopySULOmegaOracle(ObservableSUL<S, I, O> sul) {
279	super(sul);	2✔
280	}	2✔
281
282	/**
283	* Returns the current state of the {@link ObservableSUL}.
284	*
285	* @param sul the {@link ObservableSUL} to retrieve the current state from.
286	*
287	* @return the current state.
288	*/
289	@Override
290	protected S getQueryState(ObservableSUL<S, I, O> sul) {
291	return sul.getState();	2✔
292	}
293
294	/**
295	* Test for state equivalence using {@link Object#equals(Object)}.
296	*
297	* @see OmegaMembershipOracle#isSameState(Word, Object, Word, Object)
298	*/
299	@Override
300	public boolean isSameState(Word<I> input1, S s1, Word<I> input2, S s2) {
301	return s1.equals(s2);	2✔
302	}
303	}
304	}

LearnLib / learnlib / 6412002873

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