def _get_type_ancestors(type, type_hrchy, type_ancestry):
  """Compute the ancestors of a type with memorization."""
  if type in type_ancestry:
    return type_ancestry[type]
  else:
    parents = type_hrchy[type]
    result = parents[:]
    for p in parents:
      ancestors = _get_type_ancestors(p, type_hrchy, type_ancestry)
      for a in ancestors:
        if a not in result:
          result.append(a)
    type_ancestry[type] = result
    return result