Ocaml "Out of memory" exception; verbose mode says "Stack overflow in structural comparison"

Question

A very huge ocaml program from an alien source needs to be fixed. One of the problem is that the program crashes at seemingly innocent line:

Hashtbl.mem loc_to_no loc

with "Out of memory" exception. The thing is that there's surely enough memory out there and this line is executed just fine for other inputs and even earlier during the processing of the problem one.

Having run it with OCAMLRUNPARAM="v=63", I see a line that is printed right before crash:

Stack overflow in structural comparison

The structures involved are defined below. loc is of type location.

type ('a, 'b, 'c) automaton = {
  aut_id : int ;               
  mutable start_location : (('a, 'b, 'c) location) option ;
  mutable end_location   : (('a, 'b, 'c) location) option ;
  mutable aut_attributes : 'a ;                            
}
and ('a, 'b, 'c) location = {                              
  loc_id : int ;
  mutable succs : ('c * ('a, 'b, 'c) location) list ;
  mutable preds : ('c * ('a, 'b, 'c) location) list ;
  automaton : ('a, 'b, 'c) automaton ;
  mutable loc_attributes : 'b ;
}

What should be done to make the code execute?

Answer 1

Well, the hash table lookup uses "=" (structural equality) to determine if a key is the same as what you are looking for. Structural equality requires deep-checking all the substructures and stuff. You have a complicated recursive data structure. Perhaps there is a cycle in the structure at some point, which would cause it to loop infinitely. In any case, think about how you want the hash table to tell if a key is the same as yours, and then you need to use that kind of equality instead of the default structural equality; use the Hashtbl.Make functor to define a hash table module that has a custom equality and/or hash function.