Unexpected stack limit error with dif/2

[ghost]

I built https://github.com/SWI-Prolog/swipl-devel/commit/e8c2e0dd02446e61543e6c41bb76429c8186c5f0 and:

?- dif(A, B), C=[D|D], A=[D|E], B=[C|D], D=[E|E].
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 0.3Gb, global: 0.5Gb, trail: 40.0Mb
ERROR:   Stack depth: 5,529,124, last-call: 50%, Choice points: 4
ERROR:   In:
ERROR:     [5,529,124] dif:simplify_ornode_([length:2], _133602362, _133602364)
ERROR:     [5,529,120] dif:dif_c_c_l([length:1], _133602390, [length:1|_133602404])
ERROR:     [5,529,119] dif:dif_c_c([length:1|_133602432], [length:2|_133602438], _133602426)
ERROR:     [5,529,118] dif:subunifier([length:1], _133602458)
ERROR:     [5,529,116] dif:subunifier([length:1], _133602484)
ERROR: 
ERROR: Use the --stack_limit=size[KMG] command line option or
ERROR: ?- set_prolog_flag(stack_limit, 2_147_483_648). to double the limit.
?-

[JanWielemaker]

Making them equal creates a cyclic term:

?- C=[D|D], A=[D|E], B=[C|D], D=[E|E], A = B.
C = D, D = A, A = E, E = B, B = [[_S1|_S1]|_S1], % where
    _S1 = [_S1|_S1].

I don't really see how we can prevent the current implementation from looping in these cases. Most likely it is possible. It is pretty hard to understand though. Setting the occurs_check flag to true makes this work.

If you like debugging, what happens is quite well displayed by the graphical debugger if you comment this line near the start:

 :- set_prolog_flag(generate_debug_info, false).

[ghost]

Without cyclic term:

?- dif(A, B), C=[D|D], A=[C|D], B=[E|F], G=[H|H], E=[F|G].
ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 0.2Gb, global: 0.5Gb, trail: 50.2Mb
ERROR:   Stack depth: 5,131,875, last-call: 50%, Choice points: 4
ERROR:   In:
ERROR:     [5,131,875] system:unifiable([length:1|_137769030], _137769022, _137769024)
ERROR:     [5,131,873] dif:dif_c_c([length:1|_137769058], _137769050, _137769052)
ERROR:     [5,131,872] dif:subunifier([length:1], _137769078)
ERROR:     [5,131,870] dif:subunifier([length:1], _137769104)
ERROR:     [5,131,868] dif:subunifier([length:1], _137769130)
ERROR:
ERROR: Use the --stack_limit=size[KMG] command line option or
ERROR: ?- set_prolog_flag(stack_limit, 2_147_483_648). to double the limit.
?-

[UWN]

Same in 8.5.16

[UWN]

(So far) shortest example with infinite trees:

?- dif(A, B), A=[A|C], B=[D|E], D=[B].
ERROR: Stack limit (1.0Gb) exceeded

[UWN]

The query

?- dif(A, B), C=[D|D], A=[C|D], B=[E|F], G=[H|H], E=[F|G].

leads to apparent looping but no overflow (with default memory limits), that is at least taking more than 11h, when run with

?- set_prolog_flag(occurs_check, true).

similar apparent looping (I did not check it that long) for

?- set_prolog_flag(occurs_check, error).

[UWN]

More looping, less overflow in 9.1.12