For 3.4/3.5 purposes, I propose a simpler algorithm: first, define a function which takes a module name and returns true if it is part of the internal warning machinery and false otherwise. This is easy because we know what import machinery we ship.

Then, to walk the stack in warnings.py, do something like:

frame = sys._get frame(1)
if is_import_machinery(frame.module_name):
  skip_frame = lambda modname: False
else:
  skip_frame = is_import_machinery
def next_unskipped_frame(f):
  new = f
  while new is f or skip_frame(new.module_name):
    new = new.caller
for i in range(stacklevel - 1):
  frame = next_unskipped_frame(frame)

This produces reasonable behavior for warnings issued by both regular user code and by warnings issued from inside the warning machinery, and it avoids having to explicitly keep track of call depths.

Then we can worry about coming up with an all-singing all-dancing generalized version for 3.6.