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

97.83

/oracles/filters/cache/src/main/java/de/learnlib/filter/cache/dfa/DFACacheOracle.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.filter.cache.dfa;

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

import de.learnlib.api.Resumable;
import de.learnlib.api.oracle.EquivalenceOracle.DFAEquivalenceOracle;
import de.learnlib.api.oracle.MembershipOracle;
import de.learnlib.api.query.Query;
import de.learnlib.filter.cache.LearningCacheOracle.DFALearningCacheOracle;
import de.learnlib.filter.cache.dfa.DFACacheOracle.DFACacheOracleState;
import net.automatalib.SupportsGrowingAlphabet;
import net.automatalib.commons.util.Pair;
import net.automatalib.incremental.dfa.Acceptance;
import net.automatalib.incremental.dfa.IncrementalDFABuilder;
import net.automatalib.words.Word;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * DFA cache. This cache is implemented as a membership oracle: upon construction, it is provided with a delegate
 * oracle. Queries that can be answered from the cache are answered directly, others are forwarded to the delegate
 * oracle. When the delegate oracle has finished processing these remaining queries, the results are incorporated into
 * the cache.
 * <p>
 * <b>Note:</b> this implementation is <b>not</b> thread-safe. If you require a cache that is usable in a parallel
 * environment. use the {@code ThreadSafeDFACacheOracle} (or rather the {@code ThreadSafeDFACaches} factory) from the
 * {@code learnlib-parallelism} artifact.
 *
 * @param <I>
 *         input symbol class
 */
public class DFACacheOracle<I>
        implements DFALearningCacheOracle<I>, SupportsGrowingAlphabet<I>, Resumable<DFACacheOracleState<I>> {

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

    private IncrementalDFABuilder<I> incDfa;
    private final MembershipOracle<I, Boolean> delegate;

    DFACacheOracle(IncrementalDFABuilder<I> incDfa, MembershipOracle<I, Boolean> delegate) {
        this.incDfa = incDfa;
        this.delegate = delegate;
    }

    @Override
    public DFAEquivalenceOracle<I> createCacheConsistencyTest() {
        return new DFACacheConsistencyTest<>(incDfa);
    }

    @Override
    public void processQueries(Collection<? extends Query<I, Boolean>> queries) {
        if (queries.isEmpty()) {
            return;
        }

        final Pair<Collection<ProxyQuery<I>>, Collection<Query<I, Boolean>>> cacheResult = queryCache(queries);
        final Collection<ProxyQuery<I>> unanswered = cacheResult.getFirst();
        final Collection<Query<I, Boolean>> duplicates = cacheResult.getSecond();

        delegate.processQueries(unanswered);
        updateCache(unanswered);

        if (!duplicates.isEmpty()) {
            queryCache(duplicates);
        }
    }

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

    @Override
    public DFACacheOracleState<I> suspend() {
        return new DFACacheOracleState<>(incDfa);
    }

    @Override
    public void resume(DFACacheOracleState<I> state) {
        final Class<?> thisClass = this.incDfa.getClass();
        final Class<?> stateClass = state.getBuilder().getClass();

        if (!thisClass.equals(stateClass)) {
            LOGGER.warn(
                    "You currently plan to use a '{}', but the state contained a '{}'. This may yield unexpected behavior.",
                    thisClass,
                    stateClass);
        }

        this.incDfa = state.getBuilder();
    }

    protected Pair<Collection<ProxyQuery<I>>, Collection<Query<I, Boolean>>> queryCache(Collection<? extends Query<I, Boolean>> queries) {
        final List<ProxyQuery<I>> unanswered = new ArrayList<>();
        final List<Query<I, Boolean>> duplicates = new ArrayList<>();
        final Set<Word<I>> cache = new HashSet<>();

        for (Query<I, Boolean> q : queries) {
            final Word<I> input = q.getInput();
            final Acceptance acc = incDfa.lookup(input);
            if (acc != Acceptance.DONT_KNOW) {
                q.answer(acc.toBoolean());
            } else {
                if (cache.add(input)) { // never seen before
                    unanswered.add(new ProxyQuery<>(q));
                } else {
                    duplicates.add(q);
                }
            }
        }

        return Pair.of(unanswered, duplicates);
    }

    protected void updateCache(Collection<? extends ProxyQuery<I>> queries) {
        for (ProxyQuery<I> q : queries) {
            incDfa.insert(q.getInput(), q.getAnswer());
        }
    }

    public static class DFACacheOracleState<I> {

        private final IncrementalDFABuilder<I> builder;

        DFACacheOracleState(IncrementalDFABuilder<I> builder) {
            this.builder = builder;
        }

        IncrementalDFABuilder<I> getBuilder() {
            return builder;
        }
    }
}

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.filter.cache.dfa;
17
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.HashSet;
21	import java.util.List;
22	import java.util.Set;
23
24	import de.learnlib.api.Resumable;
25	import de.learnlib.api.oracle.EquivalenceOracle.DFAEquivalenceOracle;
26	import de.learnlib.api.oracle.MembershipOracle;
27	import de.learnlib.api.query.Query;
28	import de.learnlib.filter.cache.LearningCacheOracle.DFALearningCacheOracle;
29	import de.learnlib.filter.cache.dfa.DFACacheOracle.DFACacheOracleState;
30	import net.automatalib.SupportsGrowingAlphabet;
31	import net.automatalib.commons.util.Pair;
32	import net.automatalib.incremental.dfa.Acceptance;
33	import net.automatalib.incremental.dfa.IncrementalDFABuilder;
34	import net.automatalib.words.Word;
35	import org.slf4j.Logger;
36	import org.slf4j.LoggerFactory;
37
38	/**
39	* DFA cache. This cache is implemented as a membership oracle: upon construction, it is provided with a delegate
40	* oracle. Queries that can be answered from the cache are answered directly, others are forwarded to the delegate
41	* oracle. When the delegate oracle has finished processing these remaining queries, the results are incorporated into
42	* the cache.
43	* <p>
44	* <b>Note:</b> this implementation is <b>not</b> thread-safe. If you require a cache that is usable in a parallel
45	* environment. use the {@code ThreadSafeDFACacheOracle} (or rather the {@code ThreadSafeDFACaches} factory) from the
46	* {@code learnlib-parallelism} artifact.
47	*
48	* @param <I>
49	* input symbol class
50	*/
51	public class DFACacheOracle<I>
52	implements DFALearningCacheOracle<I>, SupportsGrowingAlphabet<I>, Resumable<DFACacheOracleState<I>> {
53
54	private static final Logger LOGGER = LoggerFactory.getLogger(DFACacheOracle.class);	2✔
55
56	private IncrementalDFABuilder<I> incDfa;
57	private final MembershipOracle<I, Boolean> delegate;
58
59	DFACacheOracle(IncrementalDFABuilder<I> incDfa, MembershipOracle<I, Boolean> delegate) {	2✔
60	this.incDfa = incDfa;	2✔
61	this.delegate = delegate;	2✔
62	}	2✔
63
64	@Override
65	public DFAEquivalenceOracle<I> createCacheConsistencyTest() {
66	return new DFACacheConsistencyTest<>(incDfa);	2✔
67	}
68
69	@Override
70	public void processQueries(Collection<? extends Query<I, Boolean>> queries) {
71	if (queries.isEmpty()) {	2✔
72	return;	2✔
73	}
74
75	final Pair<Collection<ProxyQuery<I>>, Collection<Query<I, Boolean>>> cacheResult = queryCache(queries);	2✔
76	final Collection<ProxyQuery<I>> unanswered = cacheResult.getFirst();	2✔
77	final Collection<Query<I, Boolean>> duplicates = cacheResult.getSecond();	2✔
78
79	delegate.processQueries(unanswered);	2✔
80	updateCache(unanswered);	2✔
81
82	if (!duplicates.isEmpty()) {	2✔
83	queryCache(duplicates);	2✔
84	}
85	}	2✔
86
87	@Override
88	public void addAlphabetSymbol(I symbol) {
89	incDfa.addAlphabetSymbol(symbol);	1✔
90	}	1✔
91
92	@Override
93	public DFACacheOracleState<I> suspend() {
94	return new DFACacheOracleState<>(incDfa);	2✔
95	}
96
97	@Override
98	public void resume(DFACacheOracleState<I> state) {
99	final Class<?> thisClass = this.incDfa.getClass();	2✔
100	final Class<?> stateClass = state.getBuilder().getClass();	2✔
101
102	if (!thisClass.equals(stateClass)) {	2✔
103	LOGGER.warn(	×
104	"You currently plan to use a '{}', but the state contained a '{}'. This may yield unexpected behavior.",
105	thisClass,
106	stateClass);
107	}
108
109	this.incDfa = state.getBuilder();	2✔
110	}	2✔
111
112	protected Pair<Collection<ProxyQuery<I>>, Collection<Query<I, Boolean>>> queryCache(Collection<? extends Query<I, Boolean>> queries) {
113	final List<ProxyQuery<I>> unanswered = new ArrayList<>();	2✔
114	final List<Query<I, Boolean>> duplicates = new ArrayList<>();	2✔
115	final Set<Word<I>> cache = new HashSet<>();	2✔
116
117	for (Query<I, Boolean> q : queries) {	2✔
118	final Word<I> input = q.getInput();	2✔
119	final Acceptance acc = incDfa.lookup(input);	2✔
120	if (acc != Acceptance.DONT_KNOW) {	2✔
121	q.answer(acc.toBoolean());	2✔
122	} else {
123	if (cache.add(input)) { // never seen before	2✔
124	unanswered.add(new ProxyQuery<>(q));	2✔
125	} else {
126	duplicates.add(q);	2✔
127	}
128	}
129	}	2✔
130
131	return Pair.of(unanswered, duplicates);	2✔
132	}
133
134	protected void updateCache(Collection<? extends ProxyQuery<I>> queries) {
135	for (ProxyQuery<I> q : queries) {	2✔
136	incDfa.insert(q.getInput(), q.getAnswer());	2✔
137	}	2✔
138	}	2✔
139
140	public static class DFACacheOracleState<I> {
141
142	private final IncrementalDFABuilder<I> builder;
143
144	DFACacheOracleState(IncrementalDFABuilder<I> builder) {	2✔
145	this.builder = builder;	2✔
146	}	2✔
147
148	IncrementalDFABuilder<I> getBuilder() {
149	return builder;	2✔
150	}
151	}
152	}

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