title: How to get all possible filter options for a particular model across relationships?
body: <p>I'm trying to expose a very flexible query interface for powerusers of my django application and I need to find every way to filter a given model in respect to the model hierarchy it is embedded in.</p>
  
  <p>I have a deeply nested set of models like this:</p>
  
  <pre><code>from django.db import models
  
  class City(models.Model):
      name = models.CharField(max_length=15)
  
  class Team(models.Model):
      location = models.ForeignKey(City)
      name = models.CharField(max_length=15)
  
  class Employee(models.Model):
      teams = models.ManyToManyField(Team)
      location = models.ForeignKey(City)
  
  class Task(models.Model):
      assignee = models.ForeignKey(Employee)
  </code></pre>
  
  <p>With <a href="https://docs.djangoproject.com/en/1.8/ref/models/querysets/" rel="nofollow">querysets</a> I can construct a complex query, for example finding all tasks that are assigned to employees from Munich:</p>
  
  <pre><code>tasks = Task.objects.filter(assignee__location="Munich")
  </code></pre>
  
  <p>or something more complex, going through M2M:</p>
  
  <pre><code>tasks = Task.objects.filter(assignee__teams__location__="Munich")
  </code></pre>
  
  <p>I want to guide my users through the process of constructing a meaningful complex query and would like to display all choices they have to filter the model <code>Task</code> by, so I came up with this algorithm:</p>
  
  <pre><code>def traverse(waiting,result=list(),grave=set()):
      if not waiting:
          # If there is nothing waiting we are done
          return
      objekt, prefix = waiting.pop(0) # Remove an item from the front of the queue
      SEPARATION_CHARACTER = "__" #django uses __ instead of . in query strings
      newprefix=prefix
      if prefix:
          newprefix = prefix +SEPARATION_CHARACTER
      try:
          modelname = objekt._meta.object_name
          if modelname in grave:
              # If the current model name is in the graveyard, it has been touched by another
              # chain and doesn't need to be processed.
              return
  
          # We now know we are dealing with a complex object that may have fields
          grave.add(objekt._meta.object_name)
          fields = objekt._meta.get_all_field_names()
          for field in fields:
              # For every attribute of the field, create a new tuple in waiting
              try:
                  waiting.append((getattr(objekt,field),newprefix+field))
              except:
                  pass
  
          for field in fields:
              traverse(waiting, result, grave)
      except:
          # If objekt._meta doesn't exist, the thing is not a complex object and we can stop this chain.
          # add the fully qualified path to the result
          result.append(prefix)
      return result
  </code></pre>
  
  <p>This will successfully find all filter possibilities for a given model by following <code>ForeignKey</code>s, but will stop on reverse <code>ForeignKey</code>s and <code>ManyToManyField</code>s. </p>
  
  <p>How can I extend my algorithm to give me all possible filter options?</p>