Repository: rollbar/pyrollbar

Issue:
Limits on locals() logging do not prevent runaway traversal
Currently the values defined in DEFAULT_LOCALS_SIZES
don't prevent traversal of large collections. The Shortener only applies after the whole object graph has been copied, as far as I can see. In our case, data transformation, it is not uncommon to have massive lists and dictionaries with 100k+ objects. 

In traverse.py
```
return list_handler(list(traverse(elem, key=key + (i,), **kw) for i, elem in enumerate(obj)), key=key)
```
traverses and creates a copy of the collection. This can itself be very time consuming as well as memory intensive. Neither things one wants in a logging library. Memory use in particular should be practically bounded.

In addition, there is no limit to the amount of recursion except for circular reference checks. So for example a highly imbalanced tree implemented in dict() that has degraded to a linked list will be traversed. 

I'd like to apply the iteration limits defined in configuration to the generators above. Maybe making a `def limited_enumerate(iterable, stop_limit)` to plug into enumerate.

As well I'd like to add a recursion count that respects an optional limit.

Thoughts ? Let me know if I've erred as this is all based on inspection. I haven't written a test.



Discussion:

Patch:
diff --git a/rollbar/lib/transform.py b/rollbar/lib/transform.py
index 49391ec..86b4e39 100644
--- a/rollbar/lib/transform.py
+++ b/rollbar/lib/transform.py
@@ -1,4 +1,6 @@
 class Transform(object):
+    depth_first = True
+
     def default(self, o, key=None):
         return o
 
diff --git a/rollbar/lib/transforms/__init__.py b/rollbar/lib/transforms/__init__.py
index 975f808..92d180f 100644
--- a/rollbar/lib/transforms/__init__.py
+++ b/rollbar/lib/transforms/__init__.py
@@ -89,7 +89,7 @@ def _transform(obj, transform, key=None):
         "allowed_circular_reference_types": _ALLOWED_CIRCULAR_REFERENCE_TYPES,
     }
 
-    return traverse.traverse(obj, key=key, **handlers)
+    return traverse.traverse(obj, key=key, depth_first=transform.depth_first, **handlers)
 
 
 __all__ = ["transform", "Transform"]
diff --git a/rollbar/lib/transforms/shortener.py b/rollbar/lib/transforms/shortener.py
index 2b33dbb..383b163 100644
--- a/rollbar/lib/transforms/shortener.py
+++ b/rollbar/lib/transforms/shortener.py
@@ -4,9 +4,10 @@ import itertools
 import reprlib
 
 from collections.abc import Mapping
+from typing import Union, Tuple
 
 from rollbar.lib import (
-    integer_types, key_in, key_depth, number_types, sequence_types,
+    integer_types, key_in, key_depth, sequence_types,
     string_types)
 from rollbar.lib.transform import Transform
 
@@ -25,7 +26,89 @@ _type_name_mapping = {
 }
 
 
+def _max_left_right(max_len: int, seperator_len: int) -> Tuple[int, int]:
+    left = max(0, (max_len-seperator_len)//2)
+    right = max(0, max_len-seperator_len-left)
+    return left, right
+
+
+def shorten_array(obj: array, max_len: int) -> array:
+    if len(obj) <= max_len:
+        return obj
+
+    return obj[:max_len]
+
+
+def shorten_bytes(obj: bytes, max_len: int) -> bytes:
+    if len(obj) <= max_len:
+        return obj
+
+    return obj[:max_len]
+
+
+def shorten_deque(obj: collections.deque, max_len: int) -> collections.deque:
+    if len(obj) <= max_len:
+        return obj
+
+    return collections.deque(itertools.islice(obj, max_len))
+
+
+def shorten_frozenset(obj: frozenset, max_len: int) -> frozenset:
+    if len(obj) <= max_len:
+        return obj
+
+    return frozenset([elem for i, elem in enumerate(obj) if i < max_len] + ['...'])
+
+
+def shorten_int(obj: int, max_len: int) -> Union[int, str]:
+    s = repr(obj)
+    if len(s) <= max_len:
+        return obj
+
+    left, right = _max_left_right(max_len, 3)
+    return s[:left] + '...' + s[len(s)-right:]
+
+
+def shorten_list(obj: list, max_len: int) -> list:
+    if len(obj) <= max_len:
+        return obj
+
+    return obj[:max_len] + ['...']
+
+
+def shorten_mapping(obj: Union[dict, Mapping], max_keys: int) -> dict:
+    if len(obj) <= max_keys:
+        return obj
+
+    return {k: obj[k] for k in itertools.islice(obj.keys(), max_keys)}
+
+
+def shorten_set(obj: set, max_len: int) -> set:
+    if len(obj) <= max_len:
+        return obj
+
+    return set([elem for i, elem in enumerate(obj) if i < max_len] + ['...'])
+
+
+def shorten_string(obj: str, max_len: int) -> str:
+    if len(obj) <= max_len:
+        return obj
+
+    left, right = _max_left_right(max_len, 3)
+    return obj[:left] + '...' + obj[len(obj)-right:]
+
+
+def shorten_tuple(obj: tuple, max_len: int) -> tuple:
+    if len(obj) <= max_len:
+        return obj
+
+    return obj[:max_len] + ('...',)
+
+
+
 class ShortenerTransform(Transform):
+    depth_first = False
+
     def __init__(self, safe_repr=True, keys=None, **sizes):
         super(ShortenerTransform, self).__init__()
         self.safe_repr = safe_repr
@@ -47,26 +130,33 @@ class ShortenerTransform(Transform):
 
         return self._repr.maxother
 
-    def _shorten_sequence(self, obj, max_keys):
-        _len = len(obj)
-        if _len <= max_keys:
-            return obj
-
-        return self._repr.repr(obj)
-
-    def _shorten_mapping(self, obj, max_keys):
-        _len = len(obj)
-        if _len <= max_keys:
-            return obj
-
-        return {k: obj[k] for k in itertools.islice(obj.keys(), max_keys)}
+    def _shorten(self, val):
+        max_size = self._get_max_size(val)
 
-    def _shorten_basic(self, obj, max_len):
-        val = str(obj)
-        if len(val) <= max_len:
-            return obj
+        if isinstance(val, array):
+            return shorten_array(val, max_size)
+        if isinstance(val, bytes):
+            return shorten_bytes(val, max_size)
+        if isinstance(val, collections.deque):
+            return shorten_deque(val, max_size)
+        if isinstance(val, (dict, Mapping)):
+            return shorten_mapping(val, max_size)
+        if isinstance(val, float):
+            return val
+        if isinstance(val, frozenset):
+            return shorten_frozenset(val, max_size)
+        if isinstance(val, int):
+            return shorten_int(val, max_size)
+        if isinstance(val, list):
+            return shorten_list(val, max_size)
+        if isinstance(val, set):
+            return shorten_set(val, max_size)
+        if isinstance(val, str):
+            return shorten_string(val, max_size)
+        if isinstance(val, tuple):
+            return shorten_tuple(val, max_size)
 
-        return self._repr.repr(obj)
+        return self._shorten_other(val)
 
     def _shorten_other(self, obj):
         if obj is None:
@@ -77,19 +167,6 @@ class ShortenerTransform(Transform):
 
         return self._repr.repr(obj)
 
-    def _shorten(self, val):
-        max_size = self._get_max_size(val)
-
-        if isinstance(val, dict):
-            return self._shorten_mapping(val, max_size)
-        if isinstance(val, (string_types, sequence_types)):
-            return self._shorten_sequence(val, max_size)
-
-        if isinstance(val, number_types):
-            return self._shorten_basic(val, self._repr.maxlong)
-
-        return self._shorten_other(val)
-
     def _should_shorten(self, val, key):
         if not key:
             return False
@@ -100,18 +177,18 @@ class ShortenerTransform(Transform):
         if not key:
             return False
 
-        maxdepth = key_depth(key, self.keys)
-        if maxdepth == 0:
+        max_depth = key_depth(key, self.keys)
+        if max_depth == 0:
             return False
 
-        return (maxdepth + self._repr.maxlevel) <= len(key)
+        return (max_depth + self._repr.maxlevel) <= len(key)
 
     def default(self, o, key=None):
         if self._should_drop(o, key):
-            if isinstance(o, dict):
-                return '{...}'
+            if isinstance(o, (dict, Mapping)):
+                return {'...': '...'}
             if isinstance(o, sequence_types):
-                return '[...]'
+                return ['...']
 
         if self._should_shorten(o, key):
             return self._shorten(o)
diff --git a/rollbar/lib/traverse.py b/rollbar/lib/traverse.py
index de00d5b..47d4bc8 100644
--- a/rollbar/lib/traverse.py
+++ b/rollbar/lib/traverse.py
@@ -81,6 +81,7 @@ def traverse(
     circular_reference_handler=_default_handlers[CIRCULAR],
     allowed_circular_reference_types=None,
     memo=None,
+    depth_first=True,
     **custom_handlers
 ):
     memo = memo or {}
@@ -108,6 +109,7 @@ def traverse(
         "circular_reference_handler": circular_reference_handler,
         "allowed_circular_reference_types": allowed_circular_reference_types,
         "memo": memo,
+        "depth_first": depth_first,
     }
     kw.update(custom_handlers)
 
@@ -115,35 +117,50 @@ def traverse(
         if obj_type is STRING:
             return string_handler(obj, key=key)
         elif obj_type is TUPLE:
-            return tuple_handler(
-                tuple(
-                    traverse(elem, key=key + (i,), **kw) for i, elem in enumerate(obj)
-                ),
-                key=key,
-            )
+            if depth_first:
+                return tuple_handler(
+                    tuple(
+                        traverse(elem, key=key + (i,), **kw) for i, elem in enumerate(obj)
+                    ),
+                    key=key,
+                )
+            # Breadth first
+            return tuple(traverse(elem, key=key + (i,), **kw) for i, elem in enumerate(tuple_handler(obj, key=key)))
         elif obj_type is NAMEDTUPLE:
-            return namedtuple_handler(
-                obj._make(
-                    traverse(v, key=key + (k,), **kw)
-                    for k, v in obj._asdict().items()
-                ),
-                key=key,
-            )
+            if depth_first:
+                return namedtuple_handler(
+                    obj._make(
+                        traverse(v, key=key + (k,), **kw)
+                        for k, v in obj._asdict().items()
+                    ),
+                    key=key,
+                )
+            # Breadth first
+            return obj._make(traverse(v, key=key + (k,), **kw) for k, v in namedtuple_handler(obj, key=key)._asdict().items())
         elif obj_type is LIST:
-            return list_handler(
-                [traverse(elem, key=key + (i,), **kw) for i, elem in enumerate(obj)],
-                key=key,
-            )
+            if depth_first:
+                return list_handler(
+                    [traverse(elem, key=key + (i,), **kw) for i, elem in enumerate(obj)],
+                    key=key,
+                )
+            # Breadth first
+            return [traverse(elem, key=key + (i,), **kw) for i, elem in enumerate(list_handler(obj, key=key))]
         elif obj_type is SET:
-            return set_handler(
-                {traverse(elem, key=key + (i,), **kw) for i, elem in enumerate(obj)},
-                key=key,
-            )
+            if depth_first:
+                return set_handler(
+                    {traverse(elem, key=key + (i,), **kw) for i, elem in enumerate(obj)},
+                    key=key,
+                )
+            # Breadth first
+            return {traverse(elem, key=key + (i,), **kw) for i, elem in enumerate(set_handler(obj, key=key))}
         elif obj_type is MAPPING:
-            return mapping_handler(
-                {k: traverse(v, key=key + (k,), **kw) for k, v in obj.items()},
-                key=key,
-            )
+            if depth_first:
+                return mapping_handler(
+                    {k: traverse(v, key=key + (k,), **kw) for k, v in obj.items()},
+                    key=key,
+                )
+            # Breadth first
+            return {k: traverse(v, key=key + (k,), **kw) for k, v in mapping_handler(obj, key=key).items()}
         elif obj_type is PATH:
             return path_handler(obj, key=key)
         elif obj_type is DEFAULT:


Test patch:
diff --git a/rollbar/test/test_rollbar.py b/rollbar/test/test_rollbar.py
index 151f616..29daf3d 100644
--- a/rollbar/test/test_rollbar.py
+++ b/rollbar/test/test_rollbar.py
@@ -1555,7 +1555,7 @@ class RollbarTest(BaseTest):
 
         self.assertEqual(1, len(payload['data']['body']['trace']['frames'][-1]['argspec']))
         self.assertEqual('large', payload['data']['body']['trace']['frames'][-1]['argspec'][0])
-        self.assertEqual("'###############################################...################################################'",
+        self.assertEqual("################################################...#################################################",
                          payload['data']['body']['trace']['frames'][-1]['locals']['large'])
 
     @mock.patch('rollbar.send_payload')
@@ -1586,12 +1586,12 @@ class RollbarTest(BaseTest):
 
         self.assertEqual('large', payload['data']['body']['trace']['frames'][-1]['argspec'][0])
         self.assertTrue(
-            ("['hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', ...]" ==
+            (['hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', '...'] ==
                 payload['data']['body']['trace']['frames'][-1]['argspec'][0])
 
             or
 
-            ("['hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', ...]" ==
+            (['hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', 'hi', '...'] ==
                     payload['data']['body']['trace']['frames'][0]['locals']['xlarge']))
 
 
diff --git a/rollbar/test/test_shortener_transform.py b/rollbar/test/test_shortener_transform.py
index 4499efe..c1f5fe7 100644
--- a/rollbar/test/test_shortener_transform.py
+++ b/rollbar/test/test_shortener_transform.py
@@ -2,10 +2,9 @@ import sys
 from array import array
 from collections import deque
 
-from rollbar import DEFAULT_LOCALS_SIZES
+from rollbar import DEFAULT_LOCALS_SIZES, SETTINGS
 from rollbar.lib import transforms
 from rollbar.lib.transforms.shortener import ShortenerTransform
-from rollbar.lib.type_info import Sequence
 from rollbar.test import BaseTest
 
 
@@ -13,12 +12,35 @@ class TestClassWithAVeryVeryVeryVeryVeryVeryVeryLongName:
     pass
 
 
+class KeyMemShortenerTransform(ShortenerTransform):
+    """
+    A shortener that just stores the keys.
+    """
+    keysUsed = []
+
+    def default(self, o, key=None):
+        self.keysUsed.append((key, o))
+        return super(KeyMemShortenerTransform, self).default(o, key=key)
+
+
 class ShortenerTransformTest(BaseTest):
     def setUp(self):
-        self.data = {
-            'string': 'x' * 120,
-            'long': 17955682733916468498414734863645002504519623752387,
-            'dict': {
+        self.shortener = ShortenerTransform(keys=[('shorten',)], **DEFAULT_LOCALS_SIZES)
+
+    def test_shorten_string(self):
+        original = 'x' * 120
+        shortened = '{}...{}'.format('x'*48, 'x'*49)
+        self.assertEqual(shortened, self.shortener.default(original, ('shorten',)))
+        self.assertEqual(original, self.shortener.default(original, ('nope',)))
+
+    def test_shorten_long(self):
+        original = 17955682733916468498414734863645002504519623752387
+        shortened = '179556827339164684...5002504519623752387'
+        self.assertEqual(shortened, self.shortener.default(original, ('shorten',)))
+        self.assertEqual(original, self.shortener.default(original, ('nope',)))
+
+    def test_shorten_mapping(self):
+        original = {
                 'one': 'one',
                 'two': 'two',
                 'three': 'three',
@@ -30,89 +52,69 @@ class ShortenerTransformTest(BaseTest):
                 'nine': 'nine',
                 'ten': 'ten',
                 'eleven': 'eleven'
-            },
-            'list': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
-            'tuple': (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11),
-            'set': set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]),
-            'frozenset': frozenset([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]),
-            'array': array('l', [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]),
-            'deque': deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], 15),
-            'other': TestClassWithAVeryVeryVeryVeryVeryVeryVeryLongName()
-        }
-
-    def _assert_shortened(self, key, expected):
-        shortener = ShortenerTransform(keys=[(key,)], **DEFAULT_LOCALS_SIZES)
-        result = transforms.transform(self.data, shortener)
-
-        if key == 'dict':
-            self.assertEqual(expected, len(result))
-        else:
-            # the repr output can vary between Python versions
-            stripped_result_key = result[key].strip("'\"u")
-
-        if key == 'other':
-            self.assertIn(expected, stripped_result_key)
-        elif key != 'dict':
-            self.assertEqual(expected, stripped_result_key)
-
-        # make sure nothing else was shortened
-        result.pop(key)
-        self.assertNotIn('...', str(result))
-        self.assertNotIn('...', str(self.data))
-
-    def test_no_shorten(self):
-        shortener = ShortenerTransform(**DEFAULT_LOCALS_SIZES)
-        result = transforms.transform(self.data, shortener)
-        self.assertEqual(self.data, result)
-
-    def test_shorten_string(self):
-        expected = '{}...{}'.format('x'*47, 'x'*48)
-        self._assert_shortened('string', expected)
-
-    def test_shorten_long(self):
-        expected = '179556827339164684...5002504519623752387'
-        self._assert_shortened('long', expected)
+            }
+        shortened = {
+                'one': 'one',
+                'two': 'two',
+                'three': 'three',
+                'four': 'four',
+                'five': 'five',
+                'six': 'six',
+                'seven': 'seven',
+                'eight': 'eight',
+                'nine': 'nine',
+                'ten': 'ten',
+            }
+        self.assertEqual(shortened, self.shortener.default(original, ('shorten',)))
+        self.assertEqual(original, self.shortener.default(original, ('nope',)))
 
-    def test_shorten_mapping(self):
-        # here, expected is the number of key value pairs
-        expected = 10
-        self._assert_shortened('dict', expected)
+    def test_shorten_bytes(self):
+        original = b'\x78' * 120
+        shortened = b'\x78' * 100
+        self.assertEqual(shortened, self.shortener.default(original, ('shorten',)))
+        self.assertEqual(original, self.shortener.default(original, ('nope',)))
 
     def test_shorten_list(self):
-        expected = '[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]'
-        self._assert_shortened('list', expected)
+        original = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
+        shortened = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, '...']
+        self.assertEqual(shortened, self.shortener.default(original, ('shorten',)))
+        self.assertEqual(original, self.shortener.default(original, ('nope',)))
 
     def test_shorten_tuple(self):
-        expected = '(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...)'
-        self._assert_shortened('tuple', expected)
+        original = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
+        shortened = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, '...')
+        self.assertEqual(shortened, self.shortener.default(original, ('shorten',)))
+        self.assertEqual(original, self.shortener.default(original, ('nope',)))
 
     def test_shorten_set(self):
-        expected = 'set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...])'
-        if sys.version_info >= (3, 5):
-            expected = '{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...}'
-        self._assert_shortened('set', expected)
+        original = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
+        shortened = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, '...'}
+        self.assertEqual(shortened, self.shortener.default(original, ('shorten',)))
+        self.assertEqual(original, self.shortener.default(original, ('nope',)))
 
     def test_shorten_frozenset(self):
-        expected = 'frozenset([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...])'
-        if sys.version_info >= (3, 5):
-            expected = 'frozenset({1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...})'
-        self._assert_shortened('frozenset', expected)
+        original = frozenset([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
+        shortened = frozenset([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, '...'])
+        self.assertEqual(shortened, self.shortener.default(original, ('shorten',)))
+        self.assertEqual(original, self.shortener.default(original, ('nope',)))
 
     def test_shorten_array(self):
-        expected = 'array(\'l\', [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...])'
-        if sys.version_info >= (3, 10):
-            expected = '[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]'
-        self._assert_shortened('array', expected)
+        original = array('l', [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
+        shortened = array('l', [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
+        self.assertEqual(shortened, self.shortener.default(original, ('shorten',)))
+        self.assertEqual(original, self.shortener.default(original, ('nope',)))
 
     def test_shorten_deque(self):
-        expected = 'deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...])'
-        if issubclass(deque, Sequence):
-            expected = '[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...]'
-        self._assert_shortened('deque', expected)
+        original = deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], 15)
+        shortened = deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 15)
+        self.assertEqual(shortened, self.shortener.default(original, ('shorten',)))
+        self.assertEqual(original, self.shortener.default(original, ('nope',)))
 
     def test_shorten_other(self):
-        expected = '<rollbar.test.test_shortener_transform.TestClas...'
-        self._assert_shortened('other', expected)
+        original = TestClassWithAVeryVeryVeryVeryVeryVeryVeryLongName()
+        shortened = '<rollbar.test.test_shortener_transform.TestClas...'
+        self.assertIn(shortened, self.shortener.default(original, ('shorten',)))
+        self.assertEqual(original, self.shortener.default(original, ('nope',)))
 
     def test_shorten_object(self):
         data = {'request': {'POST': {i: i for i in range(12)}}}
@@ -189,8 +191,8 @@ class ShortenerTransformTest(BaseTest):
                             "locals": {
                                 "kwargs": {
                                     # Shortened
-                                    "app": "['foo', 'bar', 'baz', 'qux', 'quux', 'corge', 'grault', 'garply', 'waldo', "
-                                           "'fred', ...]",
+                                    "app": ['foo', 'bar', 'baz', 'qux', 'quux', 'corge', 'grault', 'garply', 'waldo',
+                                           'fred', '...'],
                                     "extra": {
                                         "request": "<class 'some.package.MyClass'>"
                                     }
@@ -200,15 +202,15 @@ class ShortenerTransformTest(BaseTest):
                                         "three": {
                                             "four": {
                                                 "five": {
-                                                    "six": '{...}',  # Dropped because it is past the maxlevel.
+                                                    "six": {'...': '...'},  # Dropped because it is past the maxlevel.
                                                     # Shortened
-                                                    "ten": "'Yep! this should still be here, but it is a lit...ong "
-                                                           "side, so we might want to cut it down a bit.'"
+                                                    "ten": "Yep! this should still be here, but it is a litt...long "
+                                                           "side, so we might want to cut it down a bit."
                                                 }
                                             }
                                         }
                                     },
-                                    "a": "['foo', 'bar', 'baz', 'qux', 5, 6, 7, 8, 9, 10, ...]",   # Shortened
+                                    "a": ['foo', 'bar', 'baz', 'qux', 5, 6, 7, 8, 9, 10, '...'],   # Shortened
                                     "b": '140715041065664816...7453168916351054663',  # Shortened
                                     "app_id": 140715046161904,
                                     "bar": "im a bar",
@@ -221,3 +223,55 @@ class ShortenerTransformTest(BaseTest):
         }
 
         self.assertEqual(result, expected)
+
+    def test_breadth_first(self):
+        obj = {
+            "one": ["four", "five", 6, 7],
+            "two": ("eight", "nine", "ten"),
+            "three": {
+                "eleven": 12,
+                "thirteen": 14
+            }
+        }
+
+        shortener_instance = KeyMemShortenerTransform(
+            safe_repr=True,
+            keys=[
+                ('request', 'POST'),
+                ('request', 'json'),
+                ('body', 'request', 'POST'),
+                ('body', 'request', 'json'),
+            ],
+            **SETTINGS['locals']['sizes']
+        )
+
+        transforms.transform(obj, [shortener_instance], key=())
+
+        self.assertEqual(
+            shortener_instance.keysUsed,
+            [
+                ((), {
+                    "one": ["four", "five", 6, 7],
+                    "two": ("eight", "nine", "ten"),
+                    "three": {
+                        "eleven": 12,
+                        "thirteen": 14
+                    }
+                }),
+                (("one",), ["four", "five", 6, 7]),
+                (("one", 0), "four"),
+                (("one", 1), "five"),
+                (("one", 2), 6),
+                (("one", 3), 7),
+                (("two",), ("eight", "nine", "ten")),
+                (("two", 0), "eight"),
+                (("two", 1), "nine"),
+                (("two", 2), "ten"),
+                (("three",), {
+                    "eleven": 12,
+                    "thirteen": 14
+                }),
+                (("three", "eleven"), 12),
+                (("three", "thirteen"), 14),
+            ],
+        )
diff --git a/rollbar/test/test_traverse.py b/rollbar/test/test_traverse.py
index db07ee2..5606070 100644
--- a/rollbar/test/test_traverse.py
+++ b/rollbar/test/test_traverse.py
@@ -1,3 +1,4 @@
+from rollbar.lib.transform import Transform
 from rollbar.lib.traverse import traverse
 
 from rollbar.test import BaseTest
@@ -19,6 +20,17 @@ class NamedTuple(tuple):
         return [l for l in self._labels if l is not None]
 
 
+class KeyMemTransform(Transform):
+    """
+    A transform that just stores the keys.
+    """
+    keys = []
+
+    def default(self, o, key=None):
+        self.keys.append((key, o))
+        return o
+
+
 class RollbarTraverseTest(BaseTest):
     """
     Objects that appear to be a namedtuple, like SQLAlchemy's KeyedTuple,
@@ -35,3 +47,116 @@ class RollbarTraverseTest(BaseTest):
     def test_bad_object(self):
         setattr(self.tuple, "_fields", "not quite a named tuple")
         self.assertEqual(traverse(self.tuple), (1, 2, 3))
+
+    def test_depth_first(self):
+        obj = {
+            "one": ["four", "five", 6, 7],
+            "two": ("eight", "nine", "ten"),
+            "three": {
+                "eleven": 12,
+                "thirteen": 14
+            }
+        }
+        transform = KeyMemTransform()
+        transform.keys = []
+
+        traverse(
+            obj,
+            key=(),
+            string_handler=transform.default,
+            tuple_handler=transform.default,
+            namedtuple_handler=transform.default,
+            list_handler=transform.default,
+            set_handler=transform.default,
+            mapping_handler=transform.default,
+            path_handler=transform.default,
+            default_handler=transform.default,
+            circular_reference_handler=transform.default,
+            allowed_circular_reference_types=transform.default,
+        )
+
+        self.assertEqual(
+            transform.keys,
+            [
+                (("one", 0), "four"),
+                (("one", 1), "five"),
+                (("one", 2), 6),
+                (("one", 3), 7),
+                (("one",), ["four", "five", 6, 7]),
+                (("two", 0), "eight"),
+                (("two", 1), "nine"),
+                (("two", 2), "ten"),
+                (("two",), ("eight", "nine", "ten")),
+                (("three", "eleven"), 12),
+                (("three", "thirteen"), 14),
+                (("three",), {
+                    "eleven": 12,
+                    "thirteen": 14
+                }),
+                ((), {
+                    "one": ["four", "five", 6, 7],
+                    "two": ("eight", "nine", "ten"),
+                    "three": {
+                        "eleven": 12,
+                        "thirteen": 14
+                    }
+                }),
+            ],
+        )
+
+    def test_breadth_first(self):
+        obj = {
+            "one": ["four", "five", 6, 7],
+            "two": ("eight", "nine", "ten"),
+            "three": {
+                "eleven": 12,
+                "thirteen": 14
+            }
+        }
+        transform = KeyMemTransform()
+        transform.keys = []
+
+        traverse(
+            obj,
+            key=(),
+            string_handler=transform.default,
+            tuple_handler=transform.default,
+            namedtuple_handler=transform.default,
+            list_handler=transform.default,
+            set_handler=transform.default,
+            mapping_handler=transform.default,
+            path_handler=transform.default,
+            default_handler=transform.default,
+            circular_reference_handler=transform.default,
+            allowed_circular_reference_types=transform.default,
+            depth_first=False,
+        )
+
+        self.assertEqual(
+            transform.keys,
+            [
+                ((), {
+                    "one": ["four", "five", 6, 7],
+                    "two": ("eight", "nine", "ten"),
+                    "three": {
+                        "eleven": 12,
+                        "thirteen": 14
+                    }
+                }),
+                (("one",), ["four", "five", 6, 7]),
+                (("one", 0), "four"),
+                (("one", 1), "five"),
+                (("one", 2), 6),
+                (("one", 3), 7),
+                (("two",), ("eight", "nine", "ten")),
+                (("two", 0), "eight"),
+                (("two", 1), "nine"),
+                (("two", 2), "ten"),
+                (("three",), {
+                    "eleven": 12,
+                    "thirteen": 14
+                }),
+                (("three", "eleven"), 12),
+                (("three", "thirteen"), 14),
+            ],
+        )