Report cycles when inferring linked lists

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Run Celeriac on the attached file with the --linked-lists flag 

What is the expected output? What do you see instead?
Celeriac crashes with an out of memory exception when running the instrumented 
program.

This is caused by a cycle in the Person class. 

Original issue reported on code.google.com by Todd.Sch...@gmail.com on 13 Apr 2013 at 12:32

Attachments:

• StableMatching.cs

[GoogleCodeExporter]

Expected behavior here is to terminate when the cycle is completed?

And all this time I thought detecting cycles in a linked list was just an 
interview question. 

Original comment by melonhea...@gmail.com on 13 Apr 2013 at 2:46

[GoogleCodeExporter]

Ha, I've never been asked that one before. 

For ring buffers, it would make sense to terminate when the cycle is complete. 
But I'm not sure if that's the case in general. Can you check what Chicory does?

Original comment by Todd.Sch...@gmail.com on 13 Apr 2013 at 3:16

[GoogleCodeExporter]

I can't get linked lists to work in Chicory. Filed a bug here: 
https://code.google.com/p/daikon/issues/detail?id=11

Original comment by melonhea...@gmail.com on 4 Jun 2013 at 11:25

[GoogleCodeExporter]

Documented the failure in the user manual, so if this is fixed update that. 
It's not an enhancement.

The canonical solution is to use two trackers on the linked list, start them at 
the same point and iterate through the list, advance tracker A two elements at 
a time and advance tracker B one element at a time. Then compare if they refer 
to the same element (and not null), if they are then the list contains a cycle. 
If A ever gets to null then there is no cycle

Original comment by melonhea...@gmail.com on 14 Jun 2013 at 12:04

• Added labels: Type-Enhancement
• Removed labels: Type-Defect