Avoid infinite recursion in metadata_to_dict

The entry point is aws_xray_sdk.core.utils.conversion.metadata_to_dict; start by reproducing the circular-object examples from the issue and reviewing the current conversion behavior. Done means circular metadata terminates without a stack overflow while retaining the existing serialization behavior for nested objects.

Following from https://github.com/aws/aws-xray-sdk-python/issues/298:

It'd be also really good if this code [aws_xray_sdk.core.utils.conversion.metadata_to_dict] didn't overflow the stack on circular objects like this, because doing so is:

• poor for performance (repeatedly doing the full metadata_to_dict conversion over and over at each level of the recursion is potentially exponential work, and the resulting object may be huge too)
• unreliable (stack overflow can lead to problems like we see here)

For the serialization of metadata customer added, it seems like there is no more intelligent way but do recursion

One option that's still recursion is to manually avoid re-serialising things. This is pretty similar to what currently happens, in that nested objects will be replaced by {}:

def metadata_to_dict(obj):
    def _recur(obj, seen_above):
        instance_id = id(metadata)
        if instance_id in seen_above:
            # already serialised this object, avoid recursion
            return {}
        seen_above.add(instance_id)

        try:
            # ... existing implementation, but with _recur(..., stack), not metadata_to_dict
        except:
            # ...
        finally:
            seen_above.remove(instance_id)

    return _recur(obj, [])

The original example would then become something like {"x": {}}, and and similarly for:

x = X()
y = Y()
z = Z()

x.foo_x = y
y.foo_y = z
z.foo_z = x

x.bar_x = z

metadata_to_dict(x) 
# something like (note: z is still serialised twice)
# {"foo_x": {"foo_y": {"foo_z": {}}}, "bar_x": {"foo_z": {}}}

Thanks for providing the idea. One possibly very common case I would concern is that, for metadata that is very big but has no mutual references at all, walking through the new recursion will not only require the same time complexity, but will also introduce new space complexity for maintaining a temp list as big as the metadata. I can see this is not a very soon (but definitely worthwhile) enhancement we would consider to update at this moment.