replace/all/deep hangs up

[hiiamboris]

Looks like not the first time: #2808 #3132, so the algorithm should probably be revisited to prevent further failures like this.

Describe the bug

>> b: [a: 123]
== [a: 123]
>> replace/deep copy b quote a: quote x:
== [x: a: 123]      ;) this is wrong really
>> replace/all copy b quote a: quote x:
== [x: 123]
>> replace/all/deep copy b quote a: quote x:
***HANGS***

What likely happens:

• /deep switches replace into parse mode
• quote a: becomes just a: in parse expression and does not advance the input
• it just inserts x: indefinitely into the same point then

To reproduce

b: [a: 123]
replace/deep copy b quote a: quote x:
replace/all copy b quote a: quote x:
; replace/all/deep copy b quote a: quote x:

Expected behavior

>> replace/deep copy b quote a: quote x:
== [x: 123]
>> replace/all/deep copy b quote a: quote x:
== [x: 123]
>> replace/all/deep [a: [a: 123]] quote a: quote x:
== [x: [x: 123]]

Platform version (please complete the following information)

Red 0.6.4 for Windows built 27-Nov-2019/10:17:45+03:00 commit #b2aafe6

[9214]

If rewrite is in order, then we need to come up with desideratum and discuss subtle design points (e.g. lax/strict comparison and usage of Parse patterns).

[hiiamboris]

My initial thoughts:

1. I propose decoupling /deep from parse. I imagine it's there as a quick way to provide recursion, which parse implements already. Doesn't make any sense to me any other way. Both are useful: /parse without /deep (less boilerplate code) and /deep without /parse (where one doesn't want to shoot one's feet off completely, esp. in generic mezzanines).

2. In /parse mode, both pattern and value should be patterns. I have found multiple times that final value is very limiting and practically discarding the usefulness of parse. E.g. I want to support cases like replace/all [1 2 3] [set x integer!] [(form x)].

• Relation of replace/parse with mapparse should be considered, as they share similarity in their function.
• Biggest issue of replace/all [1 2 3] [set x integer!] [(form x)] example is that it makes value argument obsolete: a single expression [change set x integer! (form x)] is more natural/readable. So maybe it should be better served as separate replace-parse mezz or incorporated into mapparse by implementing a /deep refinement in it.

3. The original example deadlocks because the source grows on par with the input advancement. Obviously, declaring a refinement as eloquent as /parse should make one aware that one may deadlock it and should tread with care. But we could probably smarten it with some sanity checks, e.g. what if every 1000 or so iterations it evaluated if tail became any closer?

See also red/REP#18 on more radical changes ideas, like /all by default.

Another thought is, replace/parse/deep becomes quite potent, which is not necessarily a good thing. E.g. I may make a recursive visitor with it: replace/parse/deep input [copy x pattern] [(analyze the match and return :x)] which is outside of the design scope of replace, but still can be shorter than manual parse expression.

[9214]

So there's a split here:

• A humble replace that does only boring things expected from it — finding a match and replacing it;
• A beefed-up term-rewriting dialect that permits context-sensitive matching and pre/post processing.

[greggirwin]

Start humble.

[9214]

For the record, both R2's and R3's replace rely on find only. /deep implies parse because otherwise replace would need to maintain its own stack and handle recursion, which I think is a bit of an overkill.

So, we can have a simple replace like R2 and R3, and then we can have a more advanced replace (rewrite?) which wraps Parse and perhaps implements its own dialect on top of it; personally I imagine something among the lines of context-sensitive L-systems.

[hiiamboris]

I'd make replace/deep a recursive dumb predictable operation based on find/only. But I'd make apply native first. I think that was always the intent behind replace by the way.

[9214]

@hiiamboris that would limit the recursion level by the size of the Red's stack. Might be not that important for the common replace/deep cases.

[hiiamboris]

It's about ~2000 calls long. Parse has this limit too IIRC.

[9214]

red/runtime/parse.reds

Line 19 in 586f267

#define PARSE_MAX_DEPTH 10'000