13138848026

Committed 04 Feb 2025 02:53PM UTC coverage: 92.108% (+2.2%) from 89.877%

Build # 13138848026

Build Type

push

github

Committed by

mtf90

Commit Message

[maven-release-plugin] prepare release automatalib-0.12.0

Run Details

16609 of 18032 relevant lines covered (92.11%)

1.7 hits per line

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

96.15

/incremental/src/main/java/net/automatalib/incremental/dfa/dag/IncrementalPCDFADAGBuilder.java

/* Copyright (C) 2013-2025 TU Dortmund University
 * This file is part of AutomataLib <https://automatalib.net>.
 *
 * 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 net.automatalib.incremental.dfa.dag;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

import net.automatalib.alphabet.Alphabet;
import net.automatalib.incremental.ConflictException;
import net.automatalib.incremental.dfa.Acceptance;
import net.automatalib.word.Word;

/**
 * The prefix-closed version of {@link IncrementalDFADAGBuilder}. Contrary to the regular lookup semantics, where an
 * exact response to a lookup can only be given, if the exact word has been observed before, the prefix-closed semantics
 * behave as follows:
 *
 * <ul>
 * <li>prefixes of previously observed accepted words will result in a {@link Acceptance#TRUE} response as well.</li>
 * <li>continuations of previously observed rejected words will result in a {@link Acceptance#FALSE} response as
 * well.</li>
 * </ul>
 *
 * @param <I>
 *         input symbol class
 */
public class IncrementalPCDFADAGBuilder<I> extends AbstractIncrementalDFADAGBuilder<I> {

    public IncrementalPCDFADAGBuilder(Alphabet<I> inputAlphabet) {
        super(inputAlphabet);
    }

    @Override
    public Acceptance lookup(Word<? extends I> word) {
        State s = getState(word);
        if (s == null) {
            return Acceptance.DONT_KNOW;
        }
        return s == sink ? Acceptance.FALSE : s.getAcceptance();
    }

    @Override
    State getState(Word<? extends I> word) {

        if (init.getAcceptance() == Acceptance.FALSE) {
            return sink;
        }

        State s = init;
        for (I sym : word) {
            int idx = inputAlphabet.getSymbolIndex(sym);
            s = s.getSuccessor(idx);
            if (s == null || s == sink) {
                return s;
            }
        }
        return s;
    }

    @Override
    public void insert(Word<? extends I> word, boolean accepting) {

        State curr = init;
        State conf = null;

        Deque<Transition> path = new ArrayDeque<>();

        for (I sym : word) {
            if (curr.getAcceptance() == Acceptance.FALSE) {
                if (accepting) {
                    throw new ConflictException("Conflict");
                }
                return;
            }

            if (conf == null && curr.isConfluence()) {
                conf = curr;
            }

            int idx = inputAlphabet.getSymbolIndex(sym);

            State succ = curr.getSuccessor(idx);
            if (succ == null) {
                break;
            }
            path.push(new Transition(curr, idx));
            curr = succ;
        }

        int len = word.length();
        Acceptance acc = Acceptance.fromBoolean(accepting);
        int prefixLen = path.size();

        State last = curr;

        if (prefixLen == len) {
            Acceptance currAcc = curr.getAcceptance();
            if (currAcc == acc) {
                return;
            }
            if (currAcc != Acceptance.DONT_KNOW) {
                throw new ConflictException("Incompatible acceptances: " + currAcc + " vs " + acc);
            }
            if (accepting) {
                if (conf != null || last.isConfluence()) {
                    last = clone(last, Acceptance.TRUE);
                } else if (last == init) {
                    updateInitSignature(Acceptance.TRUE);
                    return;
                } else {
                    last = updateSignature(last, acc);
                }
            } else {
                // once we insert a rejected word, we need a sink
                if (sink == null) {
                    sink = State.SINK;
                }
                if (conf == null && !last.isConfluence()) {
                    purge(last);
                }
                if (last == init) {
                    updateInitSignature(Acceptance.FALSE);
                    return;
                }
                last = sink;
            }
        } else {
            if (conf != null) {
                if (conf == last) {
                    conf = null;
                }
                last = hiddenClone(last);
                if (conf == null) {
                    Transition peek = path.peek();
                    assert peek != null;
                    State prev = peek.state;
                    if (prev == init) {
                        updateInitSignature(peek.transIdx, last);
                    } else {
                        updateSignature(prev, peek.transIdx, last);
                    }
                }
            } else if (last != init) {
                hide(last);
            }

            Word<? extends I> suffix = word.subWord(prefixLen);
            I sym = suffix.firstSymbol();
            int suffTransIdx = inputAlphabet.getSymbolIndex(sym);
            State suffixState = createSuffix(suffix.subWord(1), accepting);

            if (last == init) {
                if (accepting) {
                    updateInitSignature(Acceptance.TRUE, suffTransIdx, suffixState);
                } else {
                    updateInitSignature(suffTransIdx, suffixState);
                }
            } else {
                if (accepting) {
                    last = unhide(last, Acceptance.TRUE, suffTransIdx, suffixState);
                } else {
                    last = unhide(last, suffTransIdx, suffixState);
                }

                if (conf != null) {
                    // in case of a cyclic structure, the suffix may make predecessors of 'conf' confluent due to un-hiding
                    // update the reference with whatever confluent state comes first
                    final Iterator<Transition> iter = path.descendingIterator();
                    while (iter.hasNext()) {
                        final State s = iter.next().state;
                        if (s.isConfluence()) {
                            conf = s;
                            break;
                        }
                    }
                }
            }
        }

        if (path.isEmpty()) {
            return;
        }

        if (conf != null) {
            Transition next;
            do {
                next = path.pop();
                State state = next.state;
                int idx = next.transIdx;
                if (accepting) {
                    state = clone(state, Acceptance.TRUE, idx, last);
                } else {
                    state = clone(state, idx, last);
                }
                last = state;
            } while (next.state != conf);
        }

        while (path.size() > 1) {
            Transition next = path.pop();
            State state = next.state;
            int idx = next.transIdx;

            // when extending the path we previously traversed (i.e. expanding the suffix), it may happen that we end up
            // adding a cyclic transition. If this is the case, simply clone the current state and update the parent in
            // the next iteration
            if (state == last) {
                last = clone(state, idx, last);
                continue;
            }

            State updated;
            Acceptance oldAcc = state.getAcceptance();
            if (accepting) {
                updated = updateSignature(state, Acceptance.TRUE, idx, last);
            } else {
                updated = updateSignature(state, idx, last);
            }
            if (state == updated && oldAcc == updated.getAcceptance()) {
                return;
            }
            last = updated;
        }

        int finalIdx = path.pop().transIdx;

        if (accepting) {
            updateInitSignature(Acceptance.TRUE, finalIdx, last);
        } else {
            updateInitSignature(finalIdx, last);
        }
    }

    /**
     * Removes a state and all of its (non-confluent) successors from the register.
     *
     * @param state
     *         the state to purge
     */
    private void purge(State state) {
        StateSignature sig = state.getSignature();
        if (sig == null) {
            return;
        }
        if (state.getAcceptance() == Acceptance.TRUE) {
            throw new IllegalStateException("Attempting to purge accepting state");
        }
        if (register.remove(sig) == null) {
            return;
        }
        sig.acceptance = Acceptance.FALSE;
        for (int i = 0; i < alphabetSize; i++) {
            State succ = sig.successors.get(i);
            if (succ != null) {
                if (succ.isConfluence()) {
                    succ.decreaseIncoming();
                } else {
                    purge(succ);
                }
            }
        }
    }

    /**
     * Creates a suffix state sequence, i.e., a linear sequence of states connected by transitions labeled by the
     * letters of the given suffix word.
     *
     * @param suffix
     *         the suffix word
     * @param accepting
     *         whether the final state should be accepting
     *
     * @return the first state in the sequence
     */
    private State createSuffix(Word<? extends I> suffix, boolean accepting) {
        State last;
        Acceptance intermediate;
        if (accepting) {
            StateSignature sig = new StateSignature(alphabetSize, Acceptance.TRUE);
            last = replaceOrRegister(sig);
            intermediate = Acceptance.TRUE;
        } else {
            if (sink == null) {
                sink = State.SINK;
            }
            last = sink;
            intermediate = Acceptance.DONT_KNOW;
        }

        int len = suffix.length();
        for (int i = len - 1; i >= 0; i--) {
            StateSignature sig = new StateSignature(alphabetSize, intermediate);
            I sym = suffix.getSymbol(i);
            int idx = inputAlphabet.getSymbolIndex(sym);
            sig.successors.set(idx, last);
            last = replaceOrRegister(sig);
        }

        return last;
    }

}

1	/* Copyright (C) 2013-2025 TU Dortmund University
2	* This file is part of AutomataLib <https://automatalib.net>.
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 net.automatalib.incremental.dfa.dag;
17
18	import java.util.ArrayDeque;
19	import java.util.Deque;
20	import java.util.Iterator;
21
22	import net.automatalib.alphabet.Alphabet;
23	import net.automatalib.incremental.ConflictException;
24	import net.automatalib.incremental.dfa.Acceptance;
25	import net.automatalib.word.Word;
26
27	/**
28	* The prefix-closed version of {@link IncrementalDFADAGBuilder}. Contrary to the regular lookup semantics, where an
29	* exact response to a lookup can only be given, if the exact word has been observed before, the prefix-closed semantics
30	* behave as follows:
31	*
32	* <ul>
33	* <li>prefixes of previously observed accepted words will result in a {@link Acceptance#TRUE} response as well.</li>
34	* <li>continuations of previously observed rejected words will result in a {@link Acceptance#FALSE} response as
35	* well.</li>
36	* </ul>
37	*
38	* @param <I>
39	* input symbol class
40	*/
41	public class IncrementalPCDFADAGBuilder<I> extends AbstractIncrementalDFADAGBuilder<I> {	2✔
42
43	public IncrementalPCDFADAGBuilder(Alphabet<I> inputAlphabet) {
44	super(inputAlphabet);	2✔
45	}	2✔
46
47	@Override
48	public Acceptance lookup(Word<? extends I> word) {
49	State s = getState(word);	2✔
50	if (s == null) {	2✔
51	return Acceptance.DONT_KNOW;	2✔
52	}
53	return s == sink ? Acceptance.FALSE : s.getAcceptance();	2✔
54	}
55
56	@Override
57	State getState(Word<? extends I> word) {
58
59	if (init.getAcceptance() == Acceptance.FALSE) {	2✔
60	return sink;	2✔
61	}
62
63	State s = init;	2✔
64	for (I sym : word) {	2✔
65	int idx = inputAlphabet.getSymbolIndex(sym);	2✔
66	s = s.getSuccessor(idx);	2✔
67	if (s == null \|\| s == sink) {	2✔
68	return s;	2✔
69	}
70	}	2✔
71	return s;	2✔
72	}
73
74	@Override
75	public void insert(Word<? extends I> word, boolean accepting) {
76
77	State curr = init;	2✔
78	State conf = null;	2✔
79
80	Deque<Transition> path = new ArrayDeque<>();	2✔
81
82	for (I sym : word) {	2✔
83	if (curr.getAcceptance() == Acceptance.FALSE) {	2✔
84	if (accepting) {	2✔
85	throw new ConflictException("Conflict");	2✔
86	}
87	return;	2✔
88	}
89
90	if (conf == null && curr.isConfluence()) {	2✔
91	conf = curr;	2✔
92	}
93
94	int idx = inputAlphabet.getSymbolIndex(sym);	2✔
95
96	State succ = curr.getSuccessor(idx);	2✔
97	if (succ == null) {	2✔
98	break;	2✔
99	}
100	path.push(new Transition(curr, idx));	2✔
101	curr = succ;	2✔
102	}	2✔
103
104	int len = word.length();	2✔
105	Acceptance acc = Acceptance.fromBoolean(accepting);	2✔
106	int prefixLen = path.size();	2✔
107
108	State last = curr;	2✔
109
110	if (prefixLen == len) {	2✔
111	Acceptance currAcc = curr.getAcceptance();	2✔
112	if (currAcc == acc) {	2✔
113	return;	2✔
114	}
115	if (currAcc != Acceptance.DONT_KNOW) {	2✔
116	throw new ConflictException("Incompatible acceptances: " + currAcc + " vs " + acc);	2✔
117	}
118	if (accepting) {	2✔
119	if (conf != null \|\| last.isConfluence()) {	2✔
120	last = clone(last, Acceptance.TRUE);	2✔
121	} else if (last == init) {	2✔
122	updateInitSignature(Acceptance.TRUE);	2✔
123	return;	2✔
124	} else {
125	last = updateSignature(last, acc);	2✔
126	}
127	} else {
128	// once we insert a rejected word, we need a sink
129	if (sink == null) {	2✔
130	sink = State.SINK;	2✔
131	}
132	if (conf == null && !last.isConfluence()) {	2✔
133	purge(last);	2✔
134	}
135	if (last == init) {	2✔
136	updateInitSignature(Acceptance.FALSE);	2✔
137	return;	2✔
138	}
139	last = sink;	2✔
140	}
141	} else {	2✔
142	if (conf != null) {	2✔
143	if (conf == last) {	2✔
144	conf = null;	2✔
145	}
146	last = hiddenClone(last);	2✔
147	if (conf == null) {	2✔
148	Transition peek = path.peek();	2✔
149	assert peek != null;	2✔
150	State prev = peek.state;	2✔
151	if (prev == init) {	2✔
152	updateInitSignature(peek.transIdx, last);	×
153	} else {
154	updateSignature(prev, peek.transIdx, last);	2✔
155	}
156	}	2✔
157	} else if (last != init) {	2✔
158	hide(last);	2✔
159	}
160
161	Word<? extends I> suffix = word.subWord(prefixLen);	2✔
162	I sym = suffix.firstSymbol();	2✔
163	int suffTransIdx = inputAlphabet.getSymbolIndex(sym);	2✔
164	State suffixState = createSuffix(suffix.subWord(1), accepting);	2✔
165
166	if (last == init) {	2✔
167	if (accepting) {	2✔
168	updateInitSignature(Acceptance.TRUE, suffTransIdx, suffixState);	2✔
169	} else {
170	updateInitSignature(suffTransIdx, suffixState);	2✔
171	}
172	} else {
173	if (accepting) {	2✔
174	last = unhide(last, Acceptance.TRUE, suffTransIdx, suffixState);	2✔
175	} else {
176	last = unhide(last, suffTransIdx, suffixState);	2✔
177	}
178
179	if (conf != null) {	2✔
180	// in case of a cyclic structure, the suffix may make predecessors of 'conf' confluent due to un-hiding
181	// update the reference with whatever confluent state comes first
182	final Iterator<Transition> iter = path.descendingIterator();	2✔
183	while (iter.hasNext()) {	2✔
184	final State s = iter.next().state;	2✔
185	if (s.isConfluence()) {	2✔
186	conf = s;	2✔
187	break;	2✔
188	}
189	}	2✔
190	}
191	}
192	}
193
194	if (path.isEmpty()) {	2✔
195	return;	2✔
196	}
197
198	if (conf != null) {	2✔
199	Transition next;
200	do {
201	next = path.pop();	2✔
202	State state = next.state;	2✔
203	int idx = next.transIdx;	2✔
204	if (accepting) {	2✔
205	state = clone(state, Acceptance.TRUE, idx, last);	2✔
206	} else {
207	state = clone(state, idx, last);	2✔
208	}
209	last = state;	2✔
210	} while (next.state != conf);	2✔
211	}
212
213	while (path.size() > 1) {	2✔
214	Transition next = path.pop();	2✔
215	State state = next.state;	2✔
216	int idx = next.transIdx;	2✔
217
218	// when extending the path we previously traversed (i.e. expanding the suffix), it may happen that we end up
219	// adding a cyclic transition. If this is the case, simply clone the current state and update the parent in
220	// the next iteration
221	if (state == last) {	2✔
222	last = clone(state, idx, last);	×
223	continue;	×
224	}
225
226	State updated;
227	Acceptance oldAcc = state.getAcceptance();	2✔
228	if (accepting) {	2✔
229	updated = updateSignature(state, Acceptance.TRUE, idx, last);	2✔
230	} else {
231	updated = updateSignature(state, idx, last);	2✔
232	}
233	if (state == updated && oldAcc == updated.getAcceptance()) {	2✔
234	return;	2✔
235	}
236	last = updated;	2✔
237	}	2✔
238
239	int finalIdx = path.pop().transIdx;	2✔
240
241	if (accepting) {	2✔
242	updateInitSignature(Acceptance.TRUE, finalIdx, last);	2✔
243	} else {
244	updateInitSignature(finalIdx, last);	2✔
245	}
246	}	2✔
247
248	/**
249	* Removes a state and all of its (non-confluent) successors from the register.
250	*
251	* @param state
252	* the state to purge
253	*/
254	private void purge(State state) {
255	StateSignature sig = state.getSignature();	2✔
256	if (sig == null) {	2✔
257	return;	×
258	}
259	if (state.getAcceptance() == Acceptance.TRUE) {	2✔
260	throw new IllegalStateException("Attempting to purge accepting state");	×
261	}
262	if (register.remove(sig) == null) {	2✔
263	return;	×
264	}
265	sig.acceptance = Acceptance.FALSE;	2✔
266	for (int i = 0; i < alphabetSize; i++) {	2✔
267	State succ = sig.successors.get(i);	2✔
268	if (succ != null) {	2✔
269	if (succ.isConfluence()) {	2✔
270	succ.decreaseIncoming();	2✔
271	} else {
272	purge(succ);	2✔
273	}
274	}
275	}
276	}	2✔
277
278	/**
279	* Creates a suffix state sequence, i.e., a linear sequence of states connected by transitions labeled by the
280	* letters of the given suffix word.
281	*
282	* @param suffix
283	* the suffix word
284	* @param accepting
285	* whether the final state should be accepting
286	*
287	* @return the first state in the sequence
288	*/
289	private State createSuffix(Word<? extends I> suffix, boolean accepting) {
290	State last;
291	Acceptance intermediate;
292	if (accepting) {	2✔
293	StateSignature sig = new StateSignature(alphabetSize, Acceptance.TRUE);	2✔
294	last = replaceOrRegister(sig);	2✔
295	intermediate = Acceptance.TRUE;	2✔
296	} else {	2✔
297	if (sink == null) {	2✔
298	sink = State.SINK;	2✔
299	}
300	last = sink;	2✔
301	intermediate = Acceptance.DONT_KNOW;	2✔
302	}
303
304	int len = suffix.length();	2✔
305	for (int i = len - 1; i >= 0; i--) {	2✔
306	StateSignature sig = new StateSignature(alphabetSize, intermediate);	2✔
307	I sym = suffix.getSymbol(i);	2✔
308	int idx = inputAlphabet.getSymbolIndex(sym);	2✔
309	sig.successors.set(idx, last);	2✔
310	last = replaceOrRegister(sig);	2✔
311	}
312
313	return last;	2✔
314	}
315
316	}

LearnLib / automatalib / 13138848026

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