Not terminating loop possible with RX_PCRE_REGULAR_EXPRESSION.replace_all

Hi All,

I've encountered a regular expression that causes a loop not to
terminate. It happens when you want to insert something at the
beginning of a string, optionally replacing a prefix. Example code:

--------------------------------------------------
class

	TEST

create

	make

feature

	make is
		local
			rx: RX_PCRE_REGULAR_EXPRESSION
			s: STRING
		do
			create rx.make
			rx.compile ("^(bye\.)?")
			rx.match (" world")
			s := rx.replace_all ("hello")    -- <== problem
			print (s + "%N")
		end

end
--------------------------------------------------

If you run this program, hit Ctrl+C quickly, as it will eat up all
your CPU and memory very very quickly.

What it should do is emit "hello world" obviously.


The problem is in rx.replace_all. This calls
RX_REGULAR_EXPRESSION.append_replace_all_to_string, where we have this
loop:

			from until not has_matched loop
				STRING_.append_substring_to_string (a_string, subject, subject_start, captured_start_position (0) - 1)
				append_replacement_to_string (a_string, a_replacement)
				match_substring (subject, captured_end_position (0) + 1, subject_end)
			end

What happens is that the start position is 1, and the end position is
0. has_matched is always true. I'm not sure how to solve this. This
was what I have now:

			p: INTEGER
		do
			from until not has_matched loop
				STRING_.append_substring_to_string (a_string, subject, subject_start, captured_start_position (0) - 1)
				append_replacement_to_string (a_string, a_replacement)
				p := captured_end_position (0)
				if p = 0 then
					-- Get out of loop if we matched beginning
					match_count := 0
				else
					match_substring (subject, p + 1, subject_end)
				end
			end

Works for this particular case of course, but not sure of the
ramifications, or on how to solve it more generally.

Probably there should be a test that we are not advancing, and that
should terminate the loop as well. But I have currently no clue how to
write that code.


Here the compile_ge.xace to compile this sample:

--------------------------------------------------
<?xml version="1.0"?>

<system name="test">
	<root class="TEST" creation="make"/>
	<option name="assertion" value="none"/>
	<option name="finalize" value="true"/>
	<option name="garbage_collector" value="internal"/>
	<cluster name="test" location="."/>
	<cluster name="ge" location="${GOBO}/library"/>
	<cluster name="argument" location="${GOBO}/library/argument" prefix="ap_"/>
	<cluster name="kernel" location="${GOBO}/library/kernel" prefix="kl_">
		<option name="abstract" value="true"/>
		<cluster name="basic"/>
		<cluster name="io"/>
		<cluster name="misc"/>
		<cluster name="unicode"/>
		<cluster name="support"/>
		<cluster name="spec">
			<option name="abstract" value="true"/>
			<cluster name="ge" prefix="kl_spec_"/>
		</cluster>
	</cluster>
	<cluster name="lexical" location="${GOBO}/library/lexical" prefix="lx_">
		<option name="abstract" value="true"/>
		<cluster name="automaton"/>
		<cluster name="error"/>
		<cluster name="generation"/>
		<cluster name="lex"/>
		<cluster name="regexp"/>
		<cluster name="scanner"/>
		<cluster name="skeleton"/>
		<cluster name="support"/>
	</cluster>
	<cluster name="math" location="${GOBO}/library/math" prefix="ma_">
		<option name="abstract" value="true"/>
		<cluster name="decimal"/>
	</cluster>
	<cluster name="parse" location="${GOBO}/library/parse" prefix="pr_">
		<option name="abstract" value="true"/>
		<cluster name="error"/>
		<cluster name="fsm"/>
		<cluster name="generation"/>
		<cluster name="grammar"/>
		<cluster name="parser"/>
		<cluster name="skeleton"/>
		<cluster name="support"/>
		<cluster name="yacc"/>
	</cluster>
	<cluster name="pattern" location="${GOBO}/library/pattern" prefix="dp_">
		<option name="abstract" value="true"/>
		<cluster name="bridge"/>
		<cluster name="command"/>
	</cluster>
	<cluster name="regexp" location="${GOBO}/library/regexp" prefix="rx_">
		<option name="abstract" value="true"/>
		<cluster name="interface"/>
		<cluster name="pcre"/>
		<cluster name="support"/>
	</cluster>
	<cluster name="string" location="${GOBO}/library/string" prefix="st_">
		<option name="abstract" value="true"/>
		<cluster name="collation"/>
		<cluster name="unicode"/>
		<cluster name="support"/>
		<cluster name="date"/>
		<cluster name="formatter">
			<option name="abstract" value="true"/>
			<cluster name="general"/>
			<cluster name="parameter"/>
		</cluster>
	</cluster>
	<cluster name="structure" location="${GOBO}/library/structure" prefix="ds_">
		<option name="abstract" value="true"/>
		<cluster name="container"/>
		<cluster name="dispenser"/>
		<cluster name="list"/>
		<cluster name="set"/>
		<cluster name="sort"/>
		<cluster name="support"/>
		<cluster name="table"/>
	</cluster>
	<cluster name="test" location="${GOBO}/library/test" prefix="ts_">
		<option name="abstract" value="true"/>
		<cluster name="generation"/>
		<cluster name="harness"/>
	</cluster>
	<cluster name="time" location="${GOBO}/library/time" prefix="dt_">
		<option name="abstract" value="true"/>
		<cluster name="clock"/>
		<cluster name="date"/>
		<cluster name="stopwatch"/>
		<cluster name="time_zone"/>
	</cluster>
	<cluster name="tools" location="${GOBO}/library/tools" prefix="et_">
		<option name="abstract" value="true"/>
		<cluster name="eiffel" prefix="et_eiffel_">
			<option name="abstract" value="true"/>
			<cluster name="ast">
				<option name="abstract" value="true"/>
				<cluster name="agent"/>
				<cluster name="assertion"/>
				<cluster name="class"/>
				<cluster name="constant"/>
				<cluster name="expression"/>
				<cluster name="feature"/>
				<cluster name="group"/>
				<cluster name="instruction"/>
				<cluster name="misc"/>
				<cluster name="name"/>
				<cluster name="type"/>
			</cluster>
			<cluster name="compilation"/>
			<cluster name="dynamic"/>
			<cluster name="error"/>
			<cluster name="generation"/>
			<cluster name="parser"/>
			<cluster name="processor"/>
		</cluster>
		<cluster name="lace" prefix="et_lace_">
			<option name="abstract" value="true"/>
			<cluster name="ast"/>
			<cluster name="error"/>
			<cluster name="parser"/>
		</cluster>
		<cluster name="ecf" prefix="et_ecf_">
			<option name="abstract" value="true"/>
			<cluster name="ast"/>
			<cluster name="error"/>
			<cluster name="parser"/>
		</cluster>
		<cluster name="xace" prefix="et_xace_">
			<option name="abstract" value="true"/>
			<cluster name="ast"/>
			<cluster name="error"/>
			<cluster name="generator"/>
			<cluster name="parser"/>
			<cluster name="support"/>
		</cluster>
	</cluster>
	<cluster name="utility" location="${GOBO}/library/utility" prefix="ut_">
		<option name="abstract" value="true"/>
		<cluster name="error"/>
		<cluster name="formatter"/>
		<cluster name="config"/>
		<cluster name="support"/>
		<cluster name="transcoder"/>
		<cluster name="uri"/>
	</cluster>
	<cluster name="xml" location="${GOBO}/library/xml" prefix="xm_">
		<option name="abstract" value="true"/>
		<cluster name="position"/>
		<cluster name="source"/>
		<cluster name="general"/>
		<cluster name="event"/>
		<cluster name="tree"/>
		<cluster name="formatter"/>
		<cluster name="resolver">
			<option name="abstract" value="true"/>
			<cluster name="resolver_interface" location="interface" relative="true"/>
			<cluster name="catalog"/>
			<cluster name="simple"/>
			<cluster name="uri"/>
		</cluster>
		<cluster name="parser">
			<option name="abstract" value="true"/>
			<cluster name="interface"/>
			<cluster name="eiffel"/>
			<cluster name="no_expat"/>
		</cluster>
		<cluster name="xml_xpointer" location="${GOBO}/library/xml/xpointer">
			<option name="abstract" value="true"/>
			<cluster name="xpointer_common" location="common" relative="true"/>
			<cluster name="xpointer_event" location="event" relative="true"/>
		</cluster>
	</cluster>
	<cluster name="xml_xslt" location="${GOBO}/library/xml/xslt" prefix="xm_">
		<option name="abstract" value="true"/>
		<cluster name="pattern"/>
		<cluster name="xslt_function" location="function" relative="true"/>
		<cluster name="instruction"/>
		<cluster name="style"/>
		<cluster name="tracing"/>
		<cluster name="number"/>
		<cluster name="xslt_sort" location="sort" relative="true"/>
		<cluster name="xslt_event" location="event" relative="true"/>
		<cluster name="runtime"/>
		<cluster name="xslt_core" location="core" relative="true"/>
		<cluster name="xslt_serializer" location="serializer" relative="true"/>
	</cluster>
	<cluster name="xml_xpath" location="${GOBO}/library/xml/xpath" prefix="xm_">
		<option name="abstract" value="true"/>
		<cluster name="data_model"/>
		<cluster name="tinytree"/>
		<cluster name="xpath_tree" location="tree" relative="true"/>
		<cluster name="value"/>
		<cluster name="expression"/>
		<cluster name="xpath_event" location="event" relative="true"/>
		<cluster name="function"/>
		<cluster name="sort"/>
		<cluster name="stand_alone"/>
		<cluster name="node_test"/>
		<cluster name="type"/>
		<cluster name="xpath_xpointer" location="xpointer" relative="true"/>
		<cluster name="core"/>
	</cluster>
	<cluster name="free_elks" location="${GOBO}/library/free_elks" prefix="fe_">
		<option name="abstract" value="true"/>
		<cluster name="fake"/>
		<cluster name="kernel"/>
		<cluster name="refactoring"/>
		<cluster name="structures">
			<cluster name="access"/>
			<cluster name="cursor_tree"/>
			<cluster name="cursors"/>
			<cluster name="dispenser"/>
			<cluster name="iteration"/>
			<cluster name="list"/>
			<cluster name="set">
				<cluster name="strategies"/>
			</cluster>
			<cluster name="sort"/>
			<cluster name="storage"/>
			<cluster name="table"/>
			<cluster name="traversing"/>
			<cluster name="tree"/>
		</cluster>
		<cluster name="support"/>
	</cluster>
</system>
--------------------------------------------------


-- 
All the best,

Berend de Boer


------------------------------------

To Post a message, send it to:   [email protected]
To Unsubscribe, send a blank message to: [email protected]! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/gobo-eiffel/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/gobo-eiffel/join
    (Yahoo! ID required)

<*> To change settings via email:
    mailto:[email protected] 
    mailto:[email protected]

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/