6673301747

Committed 27 Oct 2023 11:46PM UTC coverage: 91.986% (-1.3%) from 93.327%

Build # 6673301747

Build Type

push

github

Committed by

mtf90

Commit Message

merge the release and sign-artifacts profiles

Run Details

10984 of 11941 relevant lines covered (91.99%)

1.72 hits per line

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

79.07

/filters/reuse/src/main/java/de/learnlib/filter/reuse/tree/ReuseTree.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.reuse.tree;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.Objects;
import java.util.Set;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

import de.learnlib.filter.reuse.ReuseCapableOracle;
import de.learnlib.filter.reuse.ReuseException;
import de.learnlib.filter.reuse.ReuseOracle;
import de.learnlib.filter.reuse.tree.BoundedDeque.AccessPolicy;
import de.learnlib.filter.reuse.tree.BoundedDeque.EvictPolicy;
import net.automatalib.alphabet.Alphabet;
import net.automatalib.graph.Graph;
import net.automatalib.visualization.VisualizationHelper;
import net.automatalib.word.Word;
import net.automatalib.word.WordBuilder;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * The {@link ReuseTree} is a tree like structure consisting of nodes (see {@link ReuseNode}) and edges (see {@link
 * ReuseEdge}) that is used by the {@link ReuseOracle}: <ul> <li>Nodes may contain a system state (see {@link
 * ReuseNode#fetchSystemState(boolean)}) that could be used for executing suffixes of membership queries. Each node
 * consists of a (possible empty) set of outgoing edges. <li>Edges consists beside source and target node of input and
 * output behavior. </ul> The {@link ReuseTree} is the central data structure that maintains observed behavior from the
 * SUL and maintains also available system states. The {@link ReuseTree} is only 'tree like' since it may contain
 * reflexive edges at nodes (only possible if {@link ReuseTreeBuilder#withFailureOutputs(Set)} or {@link
 * ReuseTreeBuilder#withInvariantInputs(Set)} is set).
 *
 * @param <S>
 *         system state class
 * @param <I>
 *         input symbol class
 * @param <O>
 *         output symbol class
 */
public final class ReuseTree<S, I, O> implements Graph<@Nullable ReuseNode<S, I, O>, @Nullable ReuseEdge<S, I, O>> {

    private final Alphabet<I> alphabet;
    private final int alphabetSize;
    private final Set<I> invariantInputSymbols;
    private final Set<O> failureOutputSymbols;
    private final boolean invalidateSystemstates;
    private final SystemStateHandler<S> systemStateHandler;
    private final int maxSystemStates;
    private final AccessPolicy accessPolicy;
    private final EvictPolicy evictPolicy;
    /** May be reset to zero, see {@link ReuseTree#clearTree()}. */
    private int nodeCount;
    /** May be reinitialized, see {@link ReuseTree#clearTree()}. */
    private ReuseNode<S, I, O> root;
    private final ReadWriteLock lock;

    ReuseTree(ReuseTreeBuilder<S, I, O> builder) {
        this.alphabet = builder.alphabet;
        this.invalidateSystemstates = builder.invalidateSystemstates;
        SystemStateHandler<S> handler = builder.systemStateHandler;
        // If the specified handler is null, no action is required
        if (handler == null) {
            handler = state -> {};
        }
        this.systemStateHandler = handler;
        this.invariantInputSymbols =
                (builder.invariantInputSymbols != null) ? builder.invariantInputSymbols : Collections.emptySet();
        this.failureOutputSymbols =
                (builder.failureOutputSymbols != null) ? builder.failureOutputSymbols : Collections.emptySet();

        this.maxSystemStates = builder.maxSystemStates;
        this.accessPolicy = builder.accessPolicy;
        this.evictPolicy = builder.evictPolicy;

        // local and not configurable
        this.alphabetSize = alphabet.size();
        this.root = createNode();

        this.lock = new ReentrantReadWriteLock();
    }

    private ReuseNode<S, I, O> createNode() {
        return new ReuseNode<>(nodeCount++, alphabetSize, maxSystemStates, accessPolicy, evictPolicy);
    }

    /**
     * Returns the known output for the given query or {@code null} if not known.
     *
     * @param query
     *         Not allowed to be {@code null}.
     *
     * @return The output for {@code query} if already known from the {@link ReuseTree} or {@code null} if unknown.
     */
    public @Nullable Word<O> getOutput(Word<I> query) {
        if (query == null) {
            String msg = "Query is not allowed to be null.";
            throw new IllegalArgumentException(msg);
        }

        final WordBuilder<O> output = new WordBuilder<>();

        this.lock.readLock().lock();
        try {
            ReuseNode<S, I, O> sink = getRoot();
            for (I symbol : query) {
                final ReuseEdge<S, I, O> edge = sink.getEdgeWithInput(alphabet.getSymbolIndex(symbol));
                if (edge == null) {
                    return null;
                }
                output.add(edge.getOutput());
                sink = edge.getTarget();
            }
        } finally {
            this.lock.readLock().unlock();
        }

        return output.toWord();
    }

    /**
     * Returns the root {@link ReuseNode} of the {@link ReuseTree}.
     *
     * @return root The root of the tree, never {@code null}.
     */
    public ReuseNode<S, I, O> getRoot() {
        return this.root;
    }

    /**
     * Returns the known output for "reflexive" edges in the tree for the given query. All other symbols are set to
     * {@code null}.
     *
     * @param query
     *         Not allowed to be {@code null}.
     *
     * @return The partial output for {@code query} from the {@link ReuseTree} with outputs for "reflexive" edges filled
     * with {@code null} for "non-reflexive" and not-known parts of the input word.
     */
    public Word<O> getPartialOutput(Word<I> query) {
        if (query == null) {
            String msg = "Query is not allowed to be null.";
            throw new IllegalArgumentException(msg);
        }

        final WordBuilder<O> output = new WordBuilder<>();

        this.lock.readLock().lock();
        try {
            ReuseNode<S, I, O> sink = getRoot();
            for (I symbol : query) {
                final ReuseEdge<S, I, O> edge = sink.getEdgeWithInput(alphabet.getSymbolIndex(symbol));
                // add null-pointers if no more outputs are available
                if (edge == null) {
                    break;
                }
                // add output for "reflexive" edges
                if (sink.equals(edge.getTarget())) {
                    output.add(edge.getOutput());
                } else { // for "non-reflexive" edges add a null-pointer.
                    output.add(null);
                }
                sink = edge.getTarget();
            }
        } finally {
            this.lock.readLock().unlock();
        }

        // fill the output with null-pointers to the size of the query.
        output.repeatAppend(query.size() - output.size(), (O) null);
        return output.toWord();
    }

    /**
     * This method removes all system states from the tree. The tree structure remains, but there will be nothing for
     * reuse.
     * <p>
     * The {@link SystemStateHandler} will be informed about all disposals.
     */
    public void disposeSystemStates() {
        this.lock.writeLock().lock();
        try {
            disposeSystemStates(getRoot());
        } finally {
            this.lock.writeLock().unlock();
        }
    }

    private void disposeSystemStates(ReuseNode<S, I, O> node) {
        Iterator<S> stateIt = node.systemStatesIterator();
        while (stateIt.hasNext()) {
            S state = stateIt.next();
            systemStateHandler.dispose(state);
        }
        node.clearSystemStates();

        for (ReuseEdge<S, I, O> edge : node.getEdges()) {
            if (edge != null) {
                if (!edge.getTarget().equals(node)) {
                    // only for non-reflexive edges, there are no circles in a tree
                    disposeSystemStates(edge.getTarget());
                }
            }
        }
    }

    /**
     * Clears the whole tree which means the root will be reinitialized by a new {@link ReuseNode} and all existing
     * system states will be disposed. All invariant input symbols as well as all failure output symbols will remain.
     * <p>
     * The {@link SystemStateHandler} will <b>not</b> be informed about any disposings.
     */
    public void clearTree() {
        this.lock.writeLock().lock();
        try {
            this.nodeCount = 0;
            disposeSystemStates(root);
            this.root = createNode();
        } finally {
            this.lock.writeLock().unlock();
        }
    }

    /**
     * Returns a reuseable {@link ReuseNode.NodeResult} with system state or {@code null} if none such exists. If
     * ''oldInvalidated'' was set to {@code true} (in the {@link ReuseOracle}) the system state is already removed from
     * the tree whenever one was available.
     *
     * @param query
     *         Not allowed to be {@code null}.
     */
    public ReuseNode.@Nullable NodeResult<S, I, O> fetchSystemState(Word<I> query) {
        if (query == null) {
            String msg = "Query is not allowed to be null.";
            throw new IllegalArgumentException(msg);
        }

        int length = 0;

        this.lock.readLock().lock();
        try {
            ReuseNode<S, I, O> sink = getRoot();
            ReuseNode<S, I, O> lastState = null;
            if (sink.hasSystemStates()) {
                lastState = sink;
            }

            ReuseNode<S, I, O> node;
            for (int i = 0; i < query.size(); i++) {
                node = sink.getTargetNodeForInput(alphabet.getSymbolIndex(query.getSymbol(i)));

                if (node == null) {
                    // we have reached the longest known prefix
                    break;
                }

                sink = node;
                if (sink.hasSystemStates()) {
                    lastState = sink;
                    length = i + 1;
                }
            }

            if (lastState == null) {
                return null;
            }

            S systemState = lastState.fetchSystemState(invalidateSystemstates);

            return new ReuseNode.NodeResult<>(lastState, systemState, length);
        } finally {
            this.lock.readLock().unlock();
        }
    }

    /**
     * Inserts the given {@link Word} with {@link ReuseCapableOracle.QueryResult} into the tree starting from the root
     * node of the tree. For the longest known prefix of the given {@link Word} there will be no new nodes or edges
     * created.
     * <p>
     * Will be called from the {@link ReuseOracle} if no system state was available for reuse for the query (otherwise
     * {@link #insert(Word, ReuseNode, ReuseCapableOracle.QueryResult)} would be called). The last node reached by the
     * last symbol of the query will hold the system state from the given {@link ReuseCapableOracle.QueryResult}.
     * <p>
     * This method should only be invoked internally from the {@link ReuseOracle} unless you know exactly what you are
     * doing (you may want to create a predefined reuse tree before start learning).
     *
     * @throws ReuseException
     *         if non-deterministic behavior is detected
     */
    public void insert(Word<I> query, ReuseCapableOracle.QueryResult<S, O> queryResult) {
        insert(query, getRoot(), queryResult);
    }

    /**
     * Inserts the given {@link Word} (suffix of a membership query) with {@link ReuseCapableOracle.QueryResult} (suffix
     * output) into the tree starting from the {@link ReuseNode} (contains prefix with prefix output) in the tree. For
     * the longest known prefix of the suffix from the given {@link Word} there will be no new nodes or edges created.
     * <p>
     * Will be called from the {@link ReuseOracle} if an available system state was reused for the query (otherwise
     * {@link #insert(Word, ReuseCapableOracle.QueryResult)} would be called). The old system state was already removed
     * from the {@link ReuseNode} (through {@link #fetchSystemState(Word)}) if the ''invalidateSystemstates'' flag in
     * the {@link ReuseOracle} was set to {@code true}.
     * <p>
     * This method should only be invoked internally from the {@link ReuseOracle} unless you know exactly what you are
     * doing (you may want to create a predefined reuse tree before start learning).
     *
     * @throws ReuseException
     *         if non-deterministic behavior is detected
     */
    public void insert(Word<I> query, ReuseNode<S, I, O> sink, ReuseCapableOracle.QueryResult<S, O> queryResult) {
        if (queryResult == null) {
            String msg = "The queryResult is not allowed to be null.";
            throw new IllegalArgumentException(msg);
        }
        if (sink == null) {
            String msg = "Node is not allowed to be null, called wrong method?";
            throw new IllegalArgumentException(msg);
        }
        if (query.size() != queryResult.output.size()) {
            String msg = "Size mismatch: " + query + "/" + queryResult.output;
            throw new IllegalArgumentException(msg);
        }

        ReuseNode<S, I, O> effectiveSink = sink;

        this.lock.writeLock().lock();
        try {
            for (int i = 0; i < query.size(); i++) {
                I in = query.getSymbol(i);
                O out = queryResult.output.getSymbol(i);

                ReuseEdge<S, I, O> edge = effectiveSink.getEdgeWithInput(alphabet.getSymbolIndex(in));
                if (edge != null) {
                    if (Objects.equals(edge.getOutput(), out)) {
                        effectiveSink = edge.getTarget();
                        continue;
                    }

                    throw new ReuseException(
                            "Conflict: input '" + query + "', output '" + queryResult.output + "', i=" + i +
                            ", cached output '" + edge.getOutput() + "'");
                }

                ReuseNode<S, I, O> rn;

                if (failureOutputSymbols.contains(out)) {
                    rn = effectiveSink;
                } else if (invariantInputSymbols.contains(in)) {
                    rn = effectiveSink;
                } else {
                    rn = createNode();
                }

                int index = alphabet.getSymbolIndex(in);
                effectiveSink.addEdge(index, new ReuseEdge<>(effectiveSink, rn, in, out));
                effectiveSink = rn;
            }

            S evictedState = effectiveSink.addSystemState(queryResult.newState);
            if (evictedState != null) {
                systemStateHandler.dispose(evictedState);
            }
        } finally {
            this.lock.writeLock().unlock();
        }
    }

    @Override
    public Collection<ReuseNode<S, I, O>> getNodes() {
        Collection<ReuseNode<S, I, O>> collection = new ArrayList<>();
        appendNodesRecursively(collection, getRoot());
        return collection;
    }

    private void appendNodesRecursively(Collection<ReuseNode<S, I, O>> nodes, ReuseNode<S, I, O> current) {
        nodes.add(current);
        for (int i = 0; i < alphabetSize; i++) {
            ReuseEdge<S, I, O> reuseEdge = current.getEdgeWithInput(i);
            if (reuseEdge == null) {
                continue;
            }
            if (!current.equals(reuseEdge.getTarget())) {
                appendNodesRecursively(nodes, reuseEdge.getTarget());
            }
        }
    }

    @Override
    public Collection<@Nullable ReuseEdge<S, I, O>> getOutgoingEdges(@Nullable ReuseNode<S, I, O> node) {
        return node == null ? Collections.emptyList() : node.getEdges();
    }

    @Override
    public @Nullable ReuseNode<S, I, O> getTarget(@Nullable ReuseEdge<S, I, O> edge) {
        return edge == null ? null : edge.getTarget();
    }

    @Override
    public VisualizationHelper<@Nullable ReuseNode<S, I, O>, @Nullable ReuseEdge<S, I, O>> getVisualizationHelper() {
        return new ReuseTreeDotHelper<>();
    }

    public static class ReuseTreeBuilder<S, I, O> {

        // mandatory
        private final Alphabet<I> alphabet;

        // optional
        private boolean invalidateSystemstates = true;
        private @Nullable SystemStateHandler<S> systemStateHandler;
        private Set<I> invariantInputSymbols;
        private Set<O> failureOutputSymbols;
        private int maxSystemStates = -1;
        private AccessPolicy accessPolicy = AccessPolicy.LIFO;
        private EvictPolicy evictPolicy = EvictPolicy.EVICT_OLDEST;

        public ReuseTreeBuilder(Alphabet<I> alphabet) {
            this.alphabet = alphabet;
            this.systemStateHandler = null;
            this.invariantInputSymbols = Collections.emptySet();
            this.failureOutputSymbols = Collections.emptySet();
        }

        public ReuseTreeBuilder<S, I, O> withSystemStateHandler(SystemStateHandler<S> systemStateHandler) {
            this.systemStateHandler = systemStateHandler;
            return this;
        }

        public ReuseTreeBuilder<S, I, O> withEnabledSystemstateInvalidation(boolean invalidate) {
            this.invalidateSystemstates = invalidate;
            return this;
        }

        public ReuseTreeBuilder<S, I, O> withInvariantInputs(Set<I> inputs) {
            this.invariantInputSymbols = inputs;
            return this;
        }

        public ReuseTreeBuilder<S, I, O> withFailureOutputs(Set<O> outputs) {
            this.failureOutputSymbols = outputs;
            return this;
        }

        public ReuseTreeBuilder<S, I, O> withMaxSystemStates(int maxSystemStates) {
            this.maxSystemStates = maxSystemStates;
            return this;
        }

        public ReuseTreeBuilder<S, I, O> withAccessPolicy(AccessPolicy accessPolicy) {
            this.accessPolicy = accessPolicy;
            return this;
        }

        public ReuseTreeBuilder<S, I, O> withEvictPolicy(EvictPolicy evictPolicy) {
            this.evictPolicy = evictPolicy;
            return this;
        }

        public ReuseTree<S, I, O> build() {
            return new ReuseTree<>(this);
        }
    }
}

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.reuse.tree;
17
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.Collections;
21	import java.util.Iterator;
22	import java.util.Objects;
23	import java.util.Set;
24	import java.util.concurrent.locks.ReadWriteLock;
25	import java.util.concurrent.locks.ReentrantReadWriteLock;
26
27	import de.learnlib.filter.reuse.ReuseCapableOracle;
28	import de.learnlib.filter.reuse.ReuseException;
29	import de.learnlib.filter.reuse.ReuseOracle;
30	import de.learnlib.filter.reuse.tree.BoundedDeque.AccessPolicy;
31	import de.learnlib.filter.reuse.tree.BoundedDeque.EvictPolicy;
32	import net.automatalib.alphabet.Alphabet;
33	import net.automatalib.graph.Graph;
34	import net.automatalib.visualization.VisualizationHelper;
35	import net.automatalib.word.Word;
36	import net.automatalib.word.WordBuilder;
37	import org.checkerframework.checker.nullness.qual.Nullable;
38
39	/**
40	* The {@link ReuseTree} is a tree like structure consisting of nodes (see {@link ReuseNode}) and edges (see {@link
41	* ReuseEdge}) that is used by the {@link ReuseOracle}: <ul> <li>Nodes may contain a system state (see {@link
42	* ReuseNode#fetchSystemState(boolean)}) that could be used for executing suffixes of membership queries. Each node
43	* consists of a (possible empty) set of outgoing edges. <li>Edges consists beside source and target node of input and
44	* output behavior. </ul> The {@link ReuseTree} is the central data structure that maintains observed behavior from the
45	* SUL and maintains also available system states. The {@link ReuseTree} is only 'tree like' since it may contain
46	* reflexive edges at nodes (only possible if {@link ReuseTreeBuilder#withFailureOutputs(Set)} or {@link
47	* ReuseTreeBuilder#withInvariantInputs(Set)} is set).
48	*
49	* @param <S>
50	* system state class
51	* @param <I>
52	* input symbol class
53	* @param <O>
54	* output symbol class
55	*/
56	public final class ReuseTree<S, I, O> implements Graph<@Nullable ReuseNode<S, I, O>, @Nullable ReuseEdge<S, I, O>> {
57
58	private final Alphabet<I> alphabet;
59	private final int alphabetSize;
60	private final Set<I> invariantInputSymbols;
61	private final Set<O> failureOutputSymbols;
62	private final boolean invalidateSystemstates;
63	private final SystemStateHandler<S> systemStateHandler;
64	private final int maxSystemStates;
65	private final AccessPolicy accessPolicy;
66	private final EvictPolicy evictPolicy;
67	/** May be reset to zero, see {@link ReuseTree#clearTree()}. */
68	private int nodeCount;
69	/** May be reinitialized, see {@link ReuseTree#clearTree()}. */
70	private ReuseNode<S, I, O> root;
71	private final ReadWriteLock lock;
72
73	ReuseTree(ReuseTreeBuilder<S, I, O> builder) {	2✔
74	this.alphabet = builder.alphabet;	2✔
75	this.invalidateSystemstates = builder.invalidateSystemstates;	2✔
76	SystemStateHandler<S> handler = builder.systemStateHandler;	2✔
77	// If the specified handler is null, no action is required
78	if (handler == null) {	2✔
79	handler = state -> {};	2✔
80	}
81	this.systemStateHandler = handler;	2✔
82	this.invariantInputSymbols =	2✔
83	(builder.invariantInputSymbols != null) ? builder.invariantInputSymbols : Collections.emptySet();	2✔
84	this.failureOutputSymbols =	2✔
85	(builder.failureOutputSymbols != null) ? builder.failureOutputSymbols : Collections.emptySet();	2✔
86
87	this.maxSystemStates = builder.maxSystemStates;	2✔
88	this.accessPolicy = builder.accessPolicy;	2✔
89	this.evictPolicy = builder.evictPolicy;	2✔
90
91	// local and not configurable
92	this.alphabetSize = alphabet.size();	2✔
93	this.root = createNode();	2✔
94
95	this.lock = new ReentrantReadWriteLock();	2✔
96	}	2✔
97
98	private ReuseNode<S, I, O> createNode() {
99	return new ReuseNode<>(nodeCount++, alphabetSize, maxSystemStates, accessPolicy, evictPolicy);	2✔
100	}
101
102	/**
103	* Returns the known output for the given query or {@code null} if not known.
104	*
105	* @param query
106	* Not allowed to be {@code null}.
107	*
108	* @return The output for {@code query} if already known from the {@link ReuseTree} or {@code null} if unknown.
109	*/
110	public @Nullable Word<O> getOutput(Word<I> query) {
111	if (query == null) {	2✔
112	String msg = "Query is not allowed to be null.";	×
113	throw new IllegalArgumentException(msg);	×
114	}
115
116	final WordBuilder<O> output = new WordBuilder<>();	2✔
117
118	this.lock.readLock().lock();	2✔
119	try {
120	ReuseNode<S, I, O> sink = getRoot();	2✔
121	for (I symbol : query) {	2✔
122	final ReuseEdge<S, I, O> edge = sink.getEdgeWithInput(alphabet.getSymbolIndex(symbol));	2✔
123	if (edge == null) {	2✔
124	return null;	2✔
125	}
126	output.add(edge.getOutput());	2✔
127	sink = edge.getTarget();	2✔
128	}	2✔
129	} finally {
130	this.lock.readLock().unlock();	2✔
131	}
132
133	return output.toWord();	2✔
134	}
135
136	/**
137	* Returns the root {@link ReuseNode} of the {@link ReuseTree}.
138	*
139	* @return root The root of the tree, never {@code null}.
140	*/
141	public ReuseNode<S, I, O> getRoot() {
142	return this.root;	2✔
143	}
144
145	/**
146	* Returns the known output for "reflexive" edges in the tree for the given query. All other symbols are set to
147	* {@code null}.
148	*
149	* @param query
150	* Not allowed to be {@code null}.
151	*
152	* @return The partial output for {@code query} from the {@link ReuseTree} with outputs for "reflexive" edges filled
153	* with {@code null} for "non-reflexive" and not-known parts of the input word.
154	*/
155	public Word<O> getPartialOutput(Word<I> query) {
156	if (query == null) {	2✔
157	String msg = "Query is not allowed to be null.";	×
158	throw new IllegalArgumentException(msg);	×
159	}
160
161	final WordBuilder<O> output = new WordBuilder<>();	2✔
162
163	this.lock.readLock().lock();	2✔
164	try {
165	ReuseNode<S, I, O> sink = getRoot();	2✔
166	for (I symbol : query) {	2✔
167	final ReuseEdge<S, I, O> edge = sink.getEdgeWithInput(alphabet.getSymbolIndex(symbol));	2✔
168	// add null-pointers if no more outputs are available
169	if (edge == null) {	2✔
170	break;	2✔
171	}
172	// add output for "reflexive" edges
173	if (sink.equals(edge.getTarget())) {	2✔
174	output.add(edge.getOutput());	×
175	} else { // for "non-reflexive" edges add a null-pointer.
176	output.add(null);	2✔
177	}
178	sink = edge.getTarget();	2✔
179	}	2✔
180	} finally {
181	this.lock.readLock().unlock();	2✔
182	}
183
184	// fill the output with null-pointers to the size of the query.
185	output.repeatAppend(query.size() - output.size(), (O) null);	2✔
186	return output.toWord();	2✔
187	}
188
189	/**
190	* This method removes all system states from the tree. The tree structure remains, but there will be nothing for
191	* reuse.
192	* <p>
193	* The {@link SystemStateHandler} will be informed about all disposals.
194	*/
195	public void disposeSystemStates() {
196	this.lock.writeLock().lock();	×
197	try {
198	disposeSystemStates(getRoot());	×
199	} finally {
200	this.lock.writeLock().unlock();	×
201	}
202	}	×
203
204	private void disposeSystemStates(ReuseNode<S, I, O> node) {
205	Iterator<S> stateIt = node.systemStatesIterator();	×
206	while (stateIt.hasNext()) {	×
207	S state = stateIt.next();	×
208	systemStateHandler.dispose(state);	×
209	}	×
210	node.clearSystemStates();	×
211
212	for (ReuseEdge<S, I, O> edge : node.getEdges()) {	×
213	if (edge != null) {	×
214	if (!edge.getTarget().equals(node)) {	×
215	// only for non-reflexive edges, there are no circles in a tree
216	disposeSystemStates(edge.getTarget());	×
217	}
218	}
219	}	×
220	}	×
221
222	/**
223	* Clears the whole tree which means the root will be reinitialized by a new {@link ReuseNode} and all existing
224	* system states will be disposed. All invariant input symbols as well as all failure output symbols will remain.
225	* <p>
226	* The {@link SystemStateHandler} will <b>not</b> be informed about any disposings.
227	*/
228	public void clearTree() {
229	this.lock.writeLock().lock();	×
230	try {
231	this.nodeCount = 0;	×
232	disposeSystemStates(root);	×
233	this.root = createNode();	×
234	} finally {
235	this.lock.writeLock().unlock();	×
236	}
237	}	×
238
239	/**
240	* Returns a reuseable {@link ReuseNode.NodeResult} with system state or {@code null} if none such exists. If
241	* ''oldInvalidated'' was set to {@code true} (in the {@link ReuseOracle}) the system state is already removed from
242	* the tree whenever one was available.
243	*
244	* @param query
245	* Not allowed to be {@code null}.
246	*/
247	public ReuseNode.@Nullable NodeResult<S, I, O> fetchSystemState(Word<I> query) {
248	if (query == null) {	2✔
249	String msg = "Query is not allowed to be null.";	×
250	throw new IllegalArgumentException(msg);	×
251	}
252
253	int length = 0;	2✔
254
255	this.lock.readLock().lock();	2✔
256	try {
257	ReuseNode<S, I, O> sink = getRoot();	2✔
258	ReuseNode<S, I, O> lastState = null;	2✔
259	if (sink.hasSystemStates()) {	2✔
260	lastState = sink;	2✔
261	}
262
263	ReuseNode<S, I, O> node;
264	for (int i = 0; i < query.size(); i++) {	2✔
265	node = sink.getTargetNodeForInput(alphabet.getSymbolIndex(query.getSymbol(i)));	2✔
266
267	if (node == null) {	2✔
268	// we have reached the longest known prefix
269	break;	2✔
270	}
271
272	sink = node;	2✔
273	if (sink.hasSystemStates()) {	2✔
274	lastState = sink;	2✔
275	length = i + 1;	2✔
276	}
277	}
278
279	if (lastState == null) {	2✔
280	return null;	2✔
281	}
282
283	S systemState = lastState.fetchSystemState(invalidateSystemstates);	2✔
284
285	return new ReuseNode.NodeResult<>(lastState, systemState, length);	2✔
286	} finally {
287	this.lock.readLock().unlock();	2✔
288	}
289	}
290
291	/**
292	* Inserts the given {@link Word} with {@link ReuseCapableOracle.QueryResult} into the tree starting from the root
293	* node of the tree. For the longest known prefix of the given {@link Word} there will be no new nodes or edges
294	* created.
295	* <p>
296	* Will be called from the {@link ReuseOracle} if no system state was available for reuse for the query (otherwise
297	* {@link #insert(Word, ReuseNode, ReuseCapableOracle.QueryResult)} would be called). The last node reached by the
298	* last symbol of the query will hold the system state from the given {@link ReuseCapableOracle.QueryResult}.
299	* <p>
300	* This method should only be invoked internally from the {@link ReuseOracle} unless you know exactly what you are
301	* doing (you may want to create a predefined reuse tree before start learning).
302	*
303	* @throws ReuseException
304	* if non-deterministic behavior is detected
305	*/
306	public void insert(Word<I> query, ReuseCapableOracle.QueryResult<S, O> queryResult) {
307	insert(query, getRoot(), queryResult);	2✔
308	}	2✔
309
310	/**
311	* Inserts the given {@link Word} (suffix of a membership query) with {@link ReuseCapableOracle.QueryResult} (suffix
312	* output) into the tree starting from the {@link ReuseNode} (contains prefix with prefix output) in the tree. For
313	* the longest known prefix of the suffix from the given {@link Word} there will be no new nodes or edges created.
314	* <p>
315	* Will be called from the {@link ReuseOracle} if an available system state was reused for the query (otherwise
316	* {@link #insert(Word, ReuseCapableOracle.QueryResult)} would be called). The old system state was already removed
317	* from the {@link ReuseNode} (through {@link #fetchSystemState(Word)}) if the ''invalidateSystemstates'' flag in
318	* the {@link ReuseOracle} was set to {@code true}.
319	* <p>
320	* This method should only be invoked internally from the {@link ReuseOracle} unless you know exactly what you are
321	* doing (you may want to create a predefined reuse tree before start learning).
322	*
323	* @throws ReuseException
324	* if non-deterministic behavior is detected
325	*/
326	public void insert(Word<I> query, ReuseNode<S, I, O> sink, ReuseCapableOracle.QueryResult<S, O> queryResult) {
327	if (queryResult == null) {	2✔
328	String msg = "The queryResult is not allowed to be null.";	×
329	throw new IllegalArgumentException(msg);	×
330	}
331	if (sink == null) {	2✔
332	String msg = "Node is not allowed to be null, called wrong method?";	×
333	throw new IllegalArgumentException(msg);	×
334	}
335	if (query.size() != queryResult.output.size()) {	2✔
336	String msg = "Size mismatch: " + query + "/" + queryResult.output;	×
337	throw new IllegalArgumentException(msg);	×
338	}
339
340	ReuseNode<S, I, O> effectiveSink = sink;	2✔
341
342	this.lock.writeLock().lock();	2✔
343	try {
344	for (int i = 0; i < query.size(); i++) {	2✔
345	I in = query.getSymbol(i);	2✔
346	O out = queryResult.output.getSymbol(i);	2✔
347
348	ReuseEdge<S, I, O> edge = effectiveSink.getEdgeWithInput(alphabet.getSymbolIndex(in));	2✔
349	if (edge != null) {	2✔
350	if (Objects.equals(edge.getOutput(), out)) {	2✔
351	effectiveSink = edge.getTarget();	2✔
352	continue;	2✔
353	}
354
355	throw new ReuseException(	2✔
356	"Conflict: input '" + query + "', output '" + queryResult.output + "', i=" + i +
357	", cached output '" + edge.getOutput() + "'");	2✔
358	}
359
360	ReuseNode<S, I, O> rn;
361
362	if (failureOutputSymbols.contains(out)) {	2✔
363	rn = effectiveSink;	2✔
364	} else if (invariantInputSymbols.contains(in)) {	2✔
365	rn = effectiveSink;	2✔
366	} else {
367	rn = createNode();	2✔
368	}
369
370	int index = alphabet.getSymbolIndex(in);	2✔
371	effectiveSink.addEdge(index, new ReuseEdge<>(effectiveSink, rn, in, out));	2✔
372	effectiveSink = rn;	2✔
373	}
374
375	S evictedState = effectiveSink.addSystemState(queryResult.newState);	2✔
376	if (evictedState != null) {	2✔
377	systemStateHandler.dispose(evictedState);	×
378	}
379	} finally {
380	this.lock.writeLock().unlock();	2✔
381	}
382	}	2✔
383
384	@Override
385	public Collection<ReuseNode<S, I, O>> getNodes() {
386	Collection<ReuseNode<S, I, O>> collection = new ArrayList<>();	2✔
387	appendNodesRecursively(collection, getRoot());	2✔
388	return collection;	2✔
389	}
390
391	private void appendNodesRecursively(Collection<ReuseNode<S, I, O>> nodes, ReuseNode<S, I, O> current) {
392	nodes.add(current);	2✔
393	for (int i = 0; i < alphabetSize; i++) {	2✔
394	ReuseEdge<S, I, O> reuseEdge = current.getEdgeWithInput(i);	2✔
395	if (reuseEdge == null) {	2✔
396	continue;	2✔
397	}
398	if (!current.equals(reuseEdge.getTarget())) {	2✔
399	appendNodesRecursively(nodes, reuseEdge.getTarget());	2✔
400	}
401	}
402	}	2✔
403
404	@Override
405	public Collection<@Nullable ReuseEdge<S, I, O>> getOutgoingEdges(@Nullable ReuseNode<S, I, O> node) {
406	return node == null ? Collections.emptyList() : node.getEdges();	2✔
407	}
408
409	@Override
410	public @Nullable ReuseNode<S, I, O> getTarget(@Nullable ReuseEdge<S, I, O> edge) {
411	return edge == null ? null : edge.getTarget();	2✔
412	}
413
414	@Override
415	public VisualizationHelper<@Nullable ReuseNode<S, I, O>, @Nullable ReuseEdge<S, I, O>> getVisualizationHelper() {
416	return new ReuseTreeDotHelper<>();	2✔
417	}
418
419	public static class ReuseTreeBuilder<S, I, O> {
420
421	// mandatory
422	private final Alphabet<I> alphabet;
423
424	// optional
425	private boolean invalidateSystemstates = true;	2✔
426	private @Nullable SystemStateHandler<S> systemStateHandler;
427	private Set<I> invariantInputSymbols;
428	private Set<O> failureOutputSymbols;
429	private int maxSystemStates = -1;	2✔
430	private AccessPolicy accessPolicy = AccessPolicy.LIFO;	2✔
431	private EvictPolicy evictPolicy = EvictPolicy.EVICT_OLDEST;	2✔
432
433	public ReuseTreeBuilder(Alphabet<I> alphabet) {	2✔
434	this.alphabet = alphabet;	2✔
435	this.systemStateHandler = null;	2✔
436	this.invariantInputSymbols = Collections.emptySet();	2✔
437	this.failureOutputSymbols = Collections.emptySet();	2✔
438	}	2✔
439
440	public ReuseTreeBuilder<S, I, O> withSystemStateHandler(SystemStateHandler<S> systemStateHandler) {
441	this.systemStateHandler = systemStateHandler;	2✔
442	return this;	2✔
443	}
444
445	public ReuseTreeBuilder<S, I, O> withEnabledSystemstateInvalidation(boolean invalidate) {
446	this.invalidateSystemstates = invalidate;	2✔
447	return this;	2✔
448	}
449
450	public ReuseTreeBuilder<S, I, O> withInvariantInputs(Set<I> inputs) {
451	this.invariantInputSymbols = inputs;	2✔
452	return this;	2✔
453	}
454
455	public ReuseTreeBuilder<S, I, O> withFailureOutputs(Set<O> outputs) {
456	this.failureOutputSymbols = outputs;	2✔
457	return this;	2✔
458	}
459
460	public ReuseTreeBuilder<S, I, O> withMaxSystemStates(int maxSystemStates) {
461	this.maxSystemStates = maxSystemStates;	2✔
462	return this;	2✔
463	}
464
465	public ReuseTreeBuilder<S, I, O> withAccessPolicy(AccessPolicy accessPolicy) {
466	this.accessPolicy = accessPolicy;	2✔
467	return this;	2✔
468	}
469
470	public ReuseTreeBuilder<S, I, O> withEvictPolicy(EvictPolicy evictPolicy) {
471	this.evictPolicy = evictPolicy;	2✔
472	return this;	2✔
473	}
474
475	public ReuseTree<S, I, O> build() {
476	return new ReuseTree<>(this);	2✔
477	}
478	}
479	}

LearnLib / learnlib / 6673301747

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