bug#24012: 25.0.95; forward-comment backwards takes O(n^2)

[Leo Liu <sdl.web@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 341 bytes --]


1. Use the attached file as an example, open it in emacs in ruby-mode
2. Move point to end of buffer and eval (forward-comment (- (point)))

The last step takes about 0.25 seconds on my MacBook 3 GHz Intel Core
i7. If you double the lines of comments, the time increase by 4 folds.

Any idea why forward-comment backwards is so slow?

Leo


[-- Attachment #2: tt.rb --]
[-- Type: text/plain, Size: 24526 bytes --]

### PropEr is free software: you can redistribute it and/or modify
### it under the terms of the GNU General Public License as published by
### the Free Software Foundation, either version 3 of the License, or
### (at your option) any later version.
###
### PropEr is distributed in the hope that it will be useful,
### but WITHOUT ANY WARRANTY; without even the implied warranty of
### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
### GNU General Public License for more details.
###
### You should have received a copy of the GNU General Public License
### along with PropEr.  If not, see <http://www.gnu.org/licenses/>.

### @copyright 2010-2016 Manolis Papadakis, Eirini Arvaniti and Kostis Sagonas
### @version {@version}
### @author Eirini Arvaniti

### @doc This module defines the `proper_fsm' behaviour, useful for testing
### systems that can be modeled as finite state machines. That is, a finite
### collection of named states and transitions between them. `{@module}' is
### closely related to {@link proper_statem} and is, in fact, implemented in
### terms of that. Testcases generated using `{@module}' will be on precisely
### the same form as testcases generated using {@link proper_statem}. The
### difference lies in the way the callback modules are specified.
### The relation between {@link proper_statem} and `{@module}' is similar
### to the one between `gen_server' and `gen_fsm' in OTP libraries.
###
### Due to name conflicts with functions automatically imported from
### {@link proper_statem}, a fully qualified call is needed in order to
### use the  <a href="#index">API functions </a> of `{@module}'.
###
### === The states of the finite state machine ===
### Following the convention used in `gen_fsm behaviour', the state is
### separated into a `StateName::'{@type state_name()} and some
### `StateData::'{@type state_data()}. `StateName' is used to denote a state
### of the finite state machine and `StateData' is any relevant information
### that has to be stored in the model state. States are fully
### represented as tuples `{StateName, StateData}'.
###
### `StateName' is usually an atom (i.e. the name of the state), but can also
### be a tuple. In the latter case, the first element of the tuple must be an
### atom specifying the name of the state, whereas the rest of the elements can
### be arbitrary terms specifying state attributes. For example, when
### implementing the fsm of an elevator which can reach N different floors, the
### `StateName' for each floor could be `{floor,K}, 1 <= K <= N'.<br/>
### `StateData' can be an arbitrary term, but is usually a record.
###
### === Transitions between states ===
### A transition ({@type transition()}) is represented as a tuple
### `{TargetState, {call,M,F,A}}'. This means that performing the specified
### symbolic call at the current state of the fsm will lead to `TargetState'.
### The atom `history' can be used as `TargetState' to denote that a transition
### does not change the current state of the fsm.
###
### === The callback functions ===
### The following functions must be exported from the callback module
### implementing the finite state machine:
### <ul>
### <li> `initial_state() ->' {@type state_name()}
###   <p>Specifies the initial state of the finite state machine. As with
###   `proper_statem:initial_state/0', its result should be deterministic.
###   </p></li>
### <li> `initial_state_data() ::' {@type state_data()}
###   <p>Specifies what the state data should initially contain. Its result
###   should be deterministic</p></li>
### <li> `StateName(S::'{@type state_data()}`) ::'
###        `['{@type transition()}`]'
###   <p>There should be one instance of this function for each reachable
###   state `StateName' of the finite state machine. In case `StateName' is a
###   tuple the function takes a different form, described just below. The
###   function returns a list of possible transitions ({@type transition()})
###   from the current state.
###   At command generation time, the instance of this function with the same
###   name as the current state's name is called to return the list of possible
###   transitions. Then, PropEr will randomly choose a transition and,
###   according to that, generate the next symbolic call to be included in the
###   command sequence. However, before the call is actually included, a
###   precondition that might impose constraints on `StateData' is checked.<br/>
###   Note also that PropEr detects transitions that would raise an exception
###   of class `<error>' at generation time (not earlier) and does not choose
###   them. This feature can be used to include conditional transitions that
###   depend on the `StateData'.</p></li>
### <li> `StateName(Attr1::term(), ..., AttrN::term(),
###                 S::'{@type state_data()}`) ::'
###        `['{@type transition()}`]'
###   <p>There should be one instance of this function for each reachable state
###   `{StateName,Attr1,...,AttrN}' of the finite state machine. The function
###   has similar beaviour to `StateName/1', described above.</p></li>
### <li> `weight(From::'{@type state_name()}`,
###              Target::'{@type state_name()}`,
###              Call::'{@type symbolic_call()}`) -> integer()'
###   <p>This is an optional callback. When it is not defined (or not exported),
###   transitions are chosen with equal probability. When it is defined, it
###   assigns an integer weight to transitions from `From' to `Target'
###   triggered by symbolic call `Call'. In this case, each transition is chosen
###   with probability proportional to the weight assigned.</p></li>
### <li> `precondition(From::'{@type state_name()}`,
###                    Target::'{@type state_name()}`,
###                    StateData::'{@type state_data()}`,
###                    Call::'{@type symbolic_call()}`) -> boolean()'
###   <p>Similar to `proper_statem:precondition/2'. Specifies the
###   precondition that should hold about `StateData' so that `Call' can be
###   included in the command sequence. In case precondition doesn't hold, a
###   new transition is chosen using the appropriate `StateName/1' generator.
###   It is possible for more than one transitions to be triggered by the same
###   symbolic call and lead to different target states. In this case, at most
###   one of the target states may have a true precondition. Otherwise, PropEr
###   will not be able to detect which transition was chosen and an exception
###   will be raised.</p></li>
### <li> `postcondition(From::'{@type state_name()}`,
###                     Target::'{@type state_name()}`,
###                     StateData::'{@type state_data()}`,
###                     Call::'{@type symbolic_call()}`,
###                     Res::'{@type cmd_result()}`) -> boolean()'
###   <p>Similar to `proper_statem:postcondition/3'. Specifies the
###   postcondition that should hold about the result `Res' of the evaluation
###   of `Call'.</p></li>
### <li> `next_state_data(From::'{@type state_name()}`,
###                       Target::'{@type state_name()}`,
###                       StateData::'{@type state_data()}`,
###                       Res::'{@type cmd_result()}`,
###                       Call::'{@type symbolic_call()}`) ->'
###        {@type state_data()}
###   <p>Similar to `proper_statem:next_state/3'. Specifies how the
###   transition from `FromState' to `Target' triggered by `Call' affects the
###   `StateData'. `Res' refers to the result of `Call' and can be either
###   symbolic or dynamic.</p></li>
### </ul>
###
### === The property used ===
### This is an example of a property that can be used to test a
### finite state machine specification:
###
### ```prop_fsm() ->
###        ?FORALL(Cmds, proper_fsm:commands(?MODULE),
###                begin
###                    {_History, _State, Result} = proper_fsm:run_commands(?MODULE, Cmds),
###                    cleanup(),
###                    Result =:= ok
###                end).'''
### @end
### Copyright 2010-2016 Manolis Papadakis <manopapad@gmail.com>,
###                     Eirini Arvaniti <eirinibob@gmail.com>
###                 and Kostis Sagonas <kostis@cs.ntua.gr>
###
### This file is part of PropEr.
###
### PropEr is free software: you can redistribute it and/or modify
### it under the terms of the GNU General Public License as published by
### the Free Software Foundation, either version 3 of the License, or
### (at your option) any later version.
###
### PropEr is distributed in the hope that it will be useful,
### but WITHOUT ANY WARRANTY; without even the implied warranty of
### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
### GNU General Public License for more details.
###
### You should have received a copy of the GNU General Public License
### along with PropEr.  If not, see <http://www.gnu.org/licenses/>.

### @copyright 2010-2016 Manolis Papadakis, Eirini Arvaniti and Kostis Sagonas
### @version {@version}
### @author Eirini Arvaniti

### @doc This module defines the `proper_fsm' behaviour, useful for testing
### systems that can be modeled as finite state machines. That is, a finite
### collection of named states and transitions between them. `{@module}' is
### closely related to {@link proper_statem} and is, in fact, implemented in
### terms of that. Testcases generated using `{@module}' will be on precisely
### the same form as testcases generated using {@link proper_statem}. The
### difference lies in the way the callback modules are specified.
### The relation between {@link proper_statem} and `{@module}' is similar
### to the one between `gen_server' and `gen_fsm' in OTP libraries.
###
### Due to name conflicts with functions automatically imported from
### {@link proper_statem}, a fully qualified call is needed in order to
### use the  <a href="#index">API functions </a> of `{@module}'.
###
### === The states of the finite state machine ===
### Following the convention used in `gen_fsm behaviour', the state is
### separated into a `StateName::'{@type state_name()} and some
### `StateData::'{@type state_data()}. `StateName' is used to denote a state
### of the finite state machine and `StateData' is any relevant information
### that has to be stored in the model state. States are fully
### represented as tuples `{StateName, StateData}'.
###
### `StateName' is usually an atom (i.e. the name of the state), but can also
### be a tuple. In the latter case, the first element of the tuple must be an
### atom specifying the name of the state, whereas the rest of the elements can
### be arbitrary terms specifying state attributes. For example, when
### implementing the fsm of an elevator which can reach N different floors, the
### `StateName' for each floor could be `{floor,K}, 1 <= K <= N'.<br/>
### `StateData' can be an arbitrary term, but is usually a record.
###
### === Transitions between states ===
### A transition ({@type transition()}) is represented as a tuple
### `{TargetState, {call,M,F,A}}'. This means that performing the specified
### symbolic call at the current state of the fsm will lead to `TargetState'.
### The atom `history' can be used as `TargetState' to denote that a transition
### does not change the current state of the fsm.
###
### === The callback functions ===
### The following functions must be exported from the callback module
### implementing the finite state machine:
### <ul>
### <li> `initial_state() ->' {@type state_name()}
###   <p>Specifies the initial state of the finite state machine. As with
###   `proper_statem:initial_state/0', its result should be deterministic.
###   </p></li>
### <li> `initial_state_data() ::' {@type state_data()}
###   <p>Specifies what the state data should initially contain. Its result
###   should be deterministic</p></li>
### <li> `StateName(S::'{@type state_data()}`) ::'
###        `['{@type transition()}`]'
###   <p>There should be one instance of this function for each reachable
###   state `StateName' of the finite state machine. In case `StateName' is a
###   tuple the function takes a different form, described just below. The
###   function returns a list of possible transitions ({@type transition()})
###   from the current state.
###   At command generation time, the instance of this function with the same
###   name as the current state's name is called to return the list of possible
###   transitions. Then, PropEr will randomly choose a transition and,
###   according to that, generate the next symbolic call to be included in the
###   command sequence. However, before the call is actually included, a
###   precondition that might impose constraints on `StateData' is checked.<br/>
###   Note also that PropEr detects transitions that would raise an exception
###   of class `<error>' at generation time (not earlier) and does not choose
###   them. This feature can be used to include conditional transitions that
###   depend on the `StateData'.</p></li>
### <li> `StateName(Attr1::term(), ..., AttrN::term(),
###                 S::'{@type state_data()}`) ::'
###        `['{@type transition()}`]'
###   <p>There should be one instance of this function for each reachable state
###   `{StateName,Attr1,...,AttrN}' of the finite state machine. The function
###   has similar beaviour to `StateName/1', described above.</p></li>
### <li> `weight(From::'{@type state_name()}`,
###              Target::'{@type state_name()}`,
###              Call::'{@type symbolic_call()}`) -> integer()'
###   <p>This is an optional callback. When it is not defined (or not exported),
###   transitions are chosen with equal probability. When it is defined, it
###   assigns an integer weight to transitions from `From' to `Target'
###   triggered by symbolic call `Call'. In this case, each transition is chosen
###   with probability proportional to the weight assigned.</p></li>
### <li> `precondition(From::'{@type state_name()}`,
###                    Target::'{@type state_name()}`,
###                    StateData::'{@type state_data()}`,
###                    Call::'{@type symbolic_call()}`) -> boolean()'
###   <p>Similar to `proper_statem:precondition/2'. Specifies the
###   precondition that should hold about `StateData' so that `Call' can be
###   included in the command sequence. In case precondition doesn't hold, a
###   new transition is chosen using the appropriate `StateName/1' generator.
###   It is possible for more than one transitions to be triggered by the same
###   symbolic call and lead to different target states. In this case, at most
###   one of the target states may have a true precondition. Otherwise, PropEr
###   will not be able to detect which transition was chosen and an exception
###   will be raised.</p></li>
### <li> `postcondition(From::'{@type state_name()}`,
###                     Target::'{@type state_name()}`,
###                     StateData::'{@type state_data()}`,
###                     Call::'{@type symbolic_call()}`,
###                     Res::'{@type cmd_result()}`) -> boolean()'
###   <p>Similar to `proper_statem:postcondition/3'. Specifies the
###   postcondition that should hold about the result `Res' of the evaluation
###   of `Call'.</p></li>
### <li> `next_state_data(From::'{@type state_name()}`,
###                       Target::'{@type state_name()}`,
###                       StateData::'{@type state_data()}`,
###                       Res::'{@type cmd_result()}`,
###                       Call::'{@type symbolic_call()}`) ->'
###        {@type state_data()}
###   <p>Similar to `proper_statem:next_state/3'. Specifies how the
###   transition from `FromState' to `Target' triggered by `Call' affects the
###   `StateData'. `Res' refers to the result of `Call' and can be either
###   symbolic or dynamic.</p></li>
### </ul>
###
### === The property used ===
### This is an example of a property that can be used to test a
### finite state machine specification:
###
### ```prop_fsm() ->
###        ?FORALL(Cmds, proper_fsm:commands(?MODULE),
###                begin
###                    {_History, _State, Result} = proper_fsm:run_commands(?MODULE, Cmds),
###                    cleanup(),
###                    Result =:= ok
###                end).'''
### @end
### Copyright 2010-2016 Manolis Papadakis <manopapad@gmail.com>,
###                     Eirini Arvaniti <eirinibob@gmail.com>
###                 and Kostis Sagonas <kostis@cs.ntua.gr>
###
### This file is part of PropEr.
###
### PropEr is free software: you can redistribute it and/or modify
### it under the terms of the GNU General Public License as published by
### the Free Software Foundation, either version 3 of the License, or
### (at your option) any later version.
###
### PropEr is distributed in the hope that it will be useful,
### but WITHOUT ANY WARRANTY; without even the implied warranty of
### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
### GNU General Public License for more details.
###
### You should have received a copy of the GNU General Public License
### along with PropEr.  If not, see <http://www.gnu.org/licenses/>.

### @copyright 2010-2016 Manolis Papadakis, Eirini Arvaniti and Kostis Sagonas
### @version {@version}
### @author Eirini Arvaniti

### @doc This module defines the `proper_fsm' behaviour, useful for testing
### systems that can be modeled as finite state machines. That is, a finite
### collection of named states and transitions between them. `{@module}' is
### closely related to {@link proper_statem} and is, in fact, implemented in
### terms of that. Testcases generated using `{@module}' will be on precisely
### the same form as testcases generated using {@link proper_statem}. The
### difference lies in the way the callback modules are specified.
### The relation between {@link proper_statem} and `{@module}' is similar
### to the one between `gen_server' and `gen_fsm' in OTP libraries.
###
### Due to name conflicts with functions automatically imported from
### {@link proper_statem}, a fully qualified call is needed in order to
### use the  <a href="#index">API functions </a> of `{@module}'.
###
### === The states of the finite state machine ===
### Following the convention used in `gen_fsm behaviour', the state is
### separated into a `StateName::'{@type state_name()} and some
### `StateData::'{@type state_data()}. `StateName' is used to denote a state
### of the finite state machine and `StateData' is any relevant information
### that has to be stored in the model state. States are fully
### represented as tuples `{StateName, StateData}'.
###
### `StateName' is usually an atom (i.e. the name of the state), but can also
### be a tuple. In the latter case, the first element of the tuple must be an
### atom specifying the name of the state, whereas the rest of the elements can
### be arbitrary terms specifying state attributes. For example, when
### implementing the fsm of an elevator which can reach N different floors, the
### `StateName' for each floor could be `{floor,K}, 1 <= K <= N'.<br/>
### `StateData' can be an arbitrary term, but is usually a record.
###
### === Transitions between states ===
### A transition ({@type transition()}) is represented as a tuple
### `{TargetState, {call,M,F,A}}'. This means that performing the specified
### symbolic call at the current state of the fsm will lead to `TargetState'.
### The atom `history' can be used as `TargetState' to denote that a transition
### does not change the current state of the fsm.
###
### === The callback functions ===
### The following functions must be exported from the callback module
### implementing the finite state machine:
### <ul>
### <li> `initial_state() ->' {@type state_name()}
###   <p>Specifies the initial state of the finite state machine. As with
###   `proper_statem:initial_state/0', its result should be deterministic.
###   </p></li>
### <li> `initial_state_data() ::' {@type state_data()}
###   <p>Specifies what the state data should initially contain. Its result
###   should be deterministic</p></li>
### <li> `StateName(S::'{@type state_data()}`) ::'
###        `['{@type transition()}`]'
###   <p>There should be one instance of this function for each reachable
###   state `StateName' of the finite state machine. In case `StateName' is a
###   tuple the function takes a different form, described just below. The
###   function returns a list of possible transitions ({@type transition()})
###   from the current state.
###   At command generation time, the instance of this function with the same
###   name as the current state's name is called to return the list of possible
###   transitions. Then, PropEr will randomly choose a transition and,
###   according to that, generate the next symbolic call to be included in the
###   command sequence. However, before the call is actually included, a
###   precondition that might impose constraints on `StateData' is checked.<br/>
###   Note also that PropEr detects transitions that would raise an exception
###   of class `<error>' at generation time (not earlier) and does not choose
###   them. This feature can be used to include conditional transitions that
###   depend on the `StateData'.</p></li>
### <li> `StateName(Attr1::term(), ..., AttrN::term(),
###                 S::'{@type state_data()}`) ::'
###        `['{@type transition()}`]'
###   <p>There should be one instance of this function for each reachable state
###   `{StateName,Attr1,...,AttrN}' of the finite state machine. The function
###   has similar beaviour to `StateName/1', described above.</p></li>
### <li> `weight(From::'{@type state_name()}`,
###              Target::'{@type state_name()}`,
###              Call::'{@type symbolic_call()}`) -> integer()'
###   <p>This is an optional callback. When it is not defined (or not exported),
###   transitions are chosen with equal probability. When it is defined, it
###   assigns an integer weight to transitions from `From' to `Target'
###   triggered by symbolic call `Call'. In this case, each transition is chosen
###   with probability proportional to the weight assigned.</p></li>
### <li> `precondition(From::'{@type state_name()}`,
###                    Target::'{@type state_name()}`,
###                    StateData::'{@type state_data()}`,
###                    Call::'{@type symbolic_call()}`) -> boolean()'
###   <p>Similar to `proper_statem:precondition/2'. Specifies the
###   precondition that should hold about `StateData' so that `Call' can be
###   included in the command sequence. In case precondition doesn't hold, a
###   new transition is chosen using the appropriate `StateName/1' generator.
###   It is possible for more than one transitions to be triggered by the same
###   symbolic call and lead to different target states. In this case, at most
###   one of the target states may have a true precondition. Otherwise, PropEr
###   will not be able to detect which transition was chosen and an exception
###   will be raised.</p></li>
### <li> `postcondition(From::'{@type state_name()}`,
###                     Target::'{@type state_name()}`,
###                     StateData::'{@type state_data()}`,
###                     Call::'{@type symbolic_call()}`,
###                     Res::'{@type cmd_result()}`) -> boolean()'
###   <p>Similar to `proper_statem:postcondition/3'. Specifies the
###   postcondition that should hold about the result `Res' of the evaluation
###   of `Call'.</p></li>
### <li> `next_state_data(From::'{@type state_name()}`,
###                       Target::'{@type state_name()}`,
###                       StateData::'{@type state_data()}`,
###                       Res::'{@type cmd_result()}`,
###                       Call::'{@type symbolic_call()}`) ->'
###        {@type state_data()}
###   <p>Similar to `proper_statem:next_state/3'. Specifies how the
###   transition from `FromState' to `Target' triggered by `Call' affects the
###   `StateData'. `Res' refers to the result of `Call' and can be either
###   symbolic or dynamic.</p></li>
### </ul>
###
### === The property used ===
### This is an example of a property that can be used to test a
### finite state machine specification:
###
### ```prop_fsm() ->
###        ?FORALL(Cmds, proper_fsm:commands(?MODULE),
###                begin
###                    {_History, _State, Result} = proper_fsm:run_commands(?MODULE, Cmds),
###                    cleanup(),
###                    Result =:= ok
###                end).'''
### @end