Aleksander Alekseev <aleksander@tigerdata.com> writes:
>> I thought about that, but I'm not sure how to build a bulletproof
>> check at reasonable (ie, near zero) cost. We could detect the example
>> case where an object refers directly to itself, by noticing that "in"
>> doesn't change in one iteration. But I'm pretty sure it's possible to
>> build reference loops involving two or more Perl objects, and those
>> would fool such a check.
> I was thinking about depth-first search where we store our current
> path in a set. If the visited node is already in the set then the
> graph has loops.
> This is not exactly cheap but the complexity is proportional to the
> cost of the serialization so I think we should be fine.
No, it'd be O(N^2) for an N-deep reference chain. Admittedly,
realistic use-cases would never have more than a couple of layers of
indirection. But this whole exercise is to guard against adversarial
inputs, I think. I don't really want to add cycles and complexity to
make our behavior a bit more friendly in cases that nobody is going
to get into unless they are trying to break the database.
regards, tom lane
