How does HasNextMonitorTemplate work?

Moderator: Automated Software Engineering

LordHoto
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 135
Registriert: 14. Dez 2009 17:00

How does HasNextMonitorTemplate work?

Beitrag von LordHoto » 15. Dez 2011 12:11

Hello again,

I am currently looking into why our implementation fails two test cases in test.HasNext. Now I am looking at HasNextMonitorTemplate and I am not sure I understand how the test is supposed to work.

The FSM the HasNextMonitorTemplate seems to use is defined as:

Code: Alles auswählen

protected State<String> setupStatesAndTransitions() {
	State<String> initial = makeState(false);
	State<String> middle = makeState(false);
	State<String> error = makeState(true);
		
	initial.addTransition(getSymbolByLabel("next"), middle);
	middle.addTransition(getSymbolByLabel("next"), error);
	error.addTransition(getSymbolByLabel("next"), error);
	return initial;
}
That looks to me as it would describe the following FSM:

Code: Alles auswählen

initial --next--> middle --next--> Error*
Where --next--> means it's a transition via the input "next". And the "*" denotes a final, thus in our case an error state. I left out the next loop in the error state since it should not be of any concern for us.

Now I am looking at testNoMatch, which is one of the tests failing for us. It is implemented as follows:

Code: Alles auswählen

public void testNoMatch() {
	template.processEvent("next", v);
	template.processEvent("hasNext", v);
	template.processEvent("next", v);
	Assert.assertEquals("", template.getTrace());
}
I am confused why the trace should be empty now though. If I interpret the FSM definition correctly the execution should be as follows IMHO:

Current state for v: none, since it is not monitored yet
Incoming event: "next"
Current state for v: middle, since it is inserted as "initial" and then the "next" event it processed, which moves it to "middle".
Incoming event: "hasNext"
Current state for v: middle, since there is no hasNext transition
Incoming event: "next"
Current state for v: error, since we were in "middle" and "next" leads us to the "error" state.

Thus I would think the trace should contain "{I=i1}". But maybe I do not get this right and if I get an input which is not handled in the FSM it auto magically moves us back to the initial state, or removes the monitor? Hopefully someone can enlighten me here :-).
Compiler 1 Tutor WS 12/13

Benutzeravatar
ericbodden
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 243
Registriert: 5. Apr 2010 19:06

Re: How does HasNextMonitorTemplate work?

Beitrag von ericbodden » 15. Dez 2011 12:28

Hi.

The misunderstanding is here:
LordHoto hat geschrieben: Current state for v: middle, since it is inserted as "initial" and then the "next" event it processed, which moves it to "middle".
Incoming event: "hasNext"
Current state for v: middle, since there is no hasNext transition
When a state has no transition for the incoming symbol this does not mean that we just stay where we are. (This is therefore different from cases where there is a self-loop.) Instead it means that the monitor will not match the trace, and therefore the monitor can actually be discarded.

You can think about it from a point of view of regular-language acceptance. The FSM defines the language described by the RegEx "next+ next", or in your case without the next-loop the language described by the RegEx "next next". But the string/trace "next hasNext next" is not a member of the languages defined by either one of those two regular expressions.

An alternative design would be to require that FSMs passed to MOPBox would always need to be "complete", i.e., each state would have an outgoing transition for each symbol. In that case, a hasNext-transition from the middle state would need to go to a new, artificial "garbage state" which can never be left again. MOPBox, however, does impose that restriction on its monitors, due to the semantics describe above.

Hope that helps...
-- Eric

Benutzeravatar
ericbodden
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 243
Registriert: 5. Apr 2010 19:06

Re: How does HasNextMonitorTemplate work?

Beitrag von ericbodden » 15. Dez 2011 12:38

One more hint:

To cope with this issue in a simple way, it may make sense to compute define that a symbol a is in OutTrans(s) of a state s also if s has no a-transition at all.
-- Eric

LordHoto
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 135
Registriert: 14. Dez 2009 17:00

Re: How does HasNextMonitorTemplate work?

Beitrag von LordHoto » 15. Dez 2011 12:43

ericbodden hat geschrieben:Hi.

The misunderstanding is here:
LordHoto hat geschrieben: Current state for v: middle, since it is inserted as "initial" and then the "next" event it processed, which moves it to "middle".
Incoming event: "hasNext"
Current state for v: middle, since there is no hasNext transition
When a state has no transition for the incoming symbol this does not mean that we just stay where we are. Instead it means that the monitor will not match the trace, and therefore the monitor can actually be discarded.

You can think about it from a point of view of regular-language acceptance. The FSM defines the language described by the RegEx "next+ next", or in your case without the next-loop the language described by the RegEx "next next". But the string/trace "next hasNext next" is not a member of the languages defined by either one of those two regular expressions.

An alternative design would be to require that FSMs passed to MOPBox would always need to be "complete", i.e., each state would have an outgoing transition for each symbol. In that case, a hasNext-transition from the middle state would need to go to a new, artificial "garbage state" which can never be left again. MOPBox, however, does impose that restriction on its monitors, due to the semantics describe above.

Hope that helps...
Thank you for your fast explanation. That really helps indeed. I think the paper on symbol based indexing does not cover this in the pseudo code though.
Compiler 1 Tutor WS 12/13

Benutzeravatar
ericbodden
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 243
Registriert: 5. Apr 2010 19:06

Re: How does HasNextMonitorTemplate work?

Beitrag von ericbodden » 15. Dez 2011 15:33

LordHoto hat geschrieben:
ericbodden hat geschrieben: Thank you for your fast explanation. That really helps indeed. I think the paper on symbol based indexing does not cover this in the pseudo code though.
Indeed it appears that the author made the implicit assumption that state machines would always be "complete".
-- Eric

Antworten

Zurück zu „Automated Software Engineering“