def get_lineage(context, request, location):

    # [TODO] Move these function calls out to caller.

    user = get_user(request)

    settings = navigation_settings()

    show_hidden = asbool(
            settings['{0}_show_hidden_while_logged_in'.format(location)])
    content_types_to_include = \
            settings['{0}_include_content_types'.format(location)]
    content_types_to_exclude = \
            settings['{0}_exclude_content_types'.format(location)]

    if show_hidden and user:
        if content_types_to_include:
            items = [item for item in list(lineage(context))
                 if item.__class__ not in content_types_to_exclude
                 and item.__class__ in content_types_to_include]
        else:
            items = [item for item in list(lineage(context))
                 if item.__class__ not in content_types_to_exclude]
    else:
        if content_types_to_include:
            items = [item for item in list(lineage(context))
                 if item.__class__ in content_types_to_include
                 and item.in_navigation
                 and item.__class__ not in content_types_to_exclude]
        else:
            items = [item for item in list(lineage(context))
                 if item.in_navigation
                 and item.__class__ not in content_types_to_exclude]

    return items

 def __init__(self, *a, **k):
     SecuredObject.__init__(self, *a, **k)
     self.rproject = [a for a in lineage(self) if isinstance(a, ProjectResource)][0]
     self.project = self.rproject.context
     self.service = self.context
     self.rserver = [a for a in lineage(self) if isinstance(a, ServerResource)][0]
     self.server = self.rserver.context

def get_lineage(context, request):

    settings = navigation_settings()
    user = get_user(request)
    show_hidden = asbool(settings['show_hidden_while_logged_in'])
    ex_cts = settings['exclude_content_types']

    if show_hidden and user:
        items = [item for item in list(lineage(context))
                 if item.__class__ not in ex_cts]
    else:
        items = [item for item in list(lineage(context))
                 if item.in_navigation and item.__class__ not in ex_cts]

    return items

    def breadcrumbs(self):
        request = self.request
        context = self.context
        breadcrumbs = []
        for resource in lineage(context):
            
            if has_any_roles(roles=('Anonymous',), ignore_superiors=True):
                return {'breadcrumbs':[]}

            if isinstance(resource, Entity):
                url = request.resource_url(resource, '@@index')
            else:
                url = request.resource_url(resource)

            name = getattr(resource, 'title', None)
            if name is None:
                name = resource.__name__ or 'Home'

            icon = request.registry.content.metadata(resource, 'icon')
            content_type = request.registry.content.typeof(resource)
            active = resource is request.context and 'active' or None
            bcinfo = {
                'url':url,
                'name':name,
                'active':active,
                'icon':icon,
                'content_type':content_type,
                }
            breadcrumbs.insert(0, bcinfo)
            if resource is request.virtual_root:
                break

        return {'breadcrumbs':breadcrumbs}

def get_local_roles(userid, request=None,
                    context=None, get_cfg_storage=config.get_cfg_storage):
    """ calculates local roles for userid """
    if context is None:
        context = getattr(request, 'context', None)
        if context is None:
            context = getattr(request, 'root', None)

    roles = OrderedDict()

    if IOwnersAware.providedBy(context):
        if userid == context.__owner__:
            roles[Owner.id] = Allow

    for location in lineage(context):
        if ILocalRolesAware.providedBy(location):
            local_roles = location.__local_roles__
            if local_roles:
                for r in local_roles.get(userid, ()):
                    if r not in roles:
                        roles[r] = Allow

    data = []
    for r, val in roles.items():
        if val is Allow:
            data.append(r)

    registry = get_current_registry()
    for provider in get_cfg_storage(ID_ROLES_PROVIDER, registry).values():
        data.extend(provider(context, userid, registry))

    return data

    def principals_allowed_by_permission(self, context, permission):
        allowed = set()

        for location in reversed(list(lineage(context))):
            # NB: we're walking *up* the object graph from the root
            try:
                acl = location.__acl__
            except AttributeError:
                continue

            allowed_here = set()
            denied_here = set()

            if acl and callable(acl):
                acl = acl(request=context.request)

            for ace_action, ace_principal, ace_permissions in acl:
                if not is_nonstr_iter(ace_permissions):
                    ace_permissions = [ace_permissions]
                if (ace_action == Allow) and (permission in ace_permissions):
                    if ace_principal not in denied_here:
                        allowed_here.add(ace_principal)
                if (ace_action == Deny) and (permission in ace_permissions):
                    denied_here.add(ace_principal)
                    if ace_principal == Everyone:
                        # clear the entire allowed set, as we've hit a
                        # deny of Everyone ala (Deny, Everyone, ALL)
                        allowed = set()
                        break
                    elif ace_principal in allowed:
                        allowed.remove(ace_principal)

            allowed.update(allowed_here)

        return allowed

    def permits(self, context, principals, permission):
        acl = '<No ACL found on any object in resource lineage>'
        for location in lineage(context):
            try:
                acl = location.__acl__
            except AttributeError:
                continue

            if acl and callable(acl):
                acl = acl(request=context.request)

            for ace in acl:
                ace_action, ace_principal, ace_permissions = ace
                if ace_principal in principals:
                    if not is_nonstr_iter(ace_permissions):
                        ace_permissions = [ace_permissions]
                    if permission in ace_permissions:
                        if ace_action == Allow:
                            return ACLAllowed(ace, acl, permission,
                                              principals, location)
                        return ACLDenied(
                            ace, acl, permission, principals, location)

        return ACLDenied(
            '<default deny>',
            acl,
            permission,
            principals,
            context)

def _resource_path_list(resource, *elements):
    """ Implementation detail shared by resource_path and
    resource_path_tuple"""
    path = [loc.__name__ or '' for loc in lineage(resource)]
    path.reverse()
    path.extend(elements)
    return path

def _add_changed_descendants_to_all_parents(registry, resource):
    for parent in lineage(resource.__parent__):
        changed_descendants_is_changed = _add_changelog(registry, parent, key="changed_descendants", value=True)
        if changed_descendants_is_changed:
            _increment_changed_descendants_counter(parent)
        else:
            break

def jsonimagefolderlisting(context, request):

    items = [
        {
            'description': item.description,
            'icon': None,
            'id': item.name,
            'is_folderish': item.type not in ("file", "image", ),
            'normalized_type': item.type,
            'portal_type': item.type_info.title,
            'title': item.title,
            'uid': str(item.id),
            'url': request.resource_url(item),
        } for item in context.values()
    ]
    if context.__parent__ is None:
        parent_url = ""
    else:
        parent_url = request.resource_url(context.__parent__)

    path = [{
        "title": i.title,
        "url": request.resource_url(i),
        "icon": "", } for i in reversed(list(lineage(context)))]

    upload_allowed = True

    listing = {
        "items": items,
        "parent_url": parent_url,
        "path": path,
        "upload_allowed": upload_allowed,
    }

    return listing

    def fill_slot(self, index, value):
        """
        Fill the `index`th slot of the URL with `value`
        """
        fragments = list(reversed(list(lineage(self))))
        fillers = self.slot_fillers

        assert index < len(fillers)

        # Index into the path for filling the `index`th slot and a function
        # which fills it
        to_fill = self.ordering[index]
        filler_index, filler_function = fillers[to_fill]

        # Get the (as yet incomplete) resource with the slot filled
        filled_traverser = filler_function(fragments[filler_index], value)
        assert filled_traverser

        # Get the path which needs to be appended to this traverser
        remaining_fragments = [f.__name__ for f in fragments[filler_index + 1:]]
        remaining_fragments = transpose_fragments_fixup(remaining_fragments, to_fill)

        # Traverse any remaining parts of the path, if they exist
        remaining_path = "/".join(remaining_fragments)
        if remaining_path:
            filled_traverser = traverse(filled_traverser, remaining_path)["context"]

        return filled_traverser

 def _getPath(self, model):
     rpath = []
     for location in lineage(model):
         if location.__name__ is None:
             break
         rpath.insert(0, location.__name__)
     return tuple(rpath)

def merged_local_principals(context, principals):
    # XXX Possibly limit to prefix like 'role.'
    set_principals = frozenset(principals)
    local_principals = set()
    block = False
    for location in lineage(context):
        if block:
            break

        block = getattr(location, '__ac_local_roles_block__', False)
        local_roles = getattr(location, '__ac_local_roles__', None)

        if local_roles and callable(local_roles):
            local_roles = local_roles()

        if not local_roles:
            continue

        for principal, roles in local_roles.iteritems():
            if not is_nonstr_iter(roles):
                roles = [roles]
            if not set_principals.isdisjoint(roles):
                local_principals.add(principal)

    if not local_principals:
        return principals

    local_principals.update(principals)
    return list(local_principals)

def _set_path_for_new_parent(target, value, oldvalue, initiator):
    """Triggered whenever the Node's 'parent' attribute is set.
    """
    if value is None:
        # The parent is about to be set to 'None', so skip.
        return

    if target.__name__ is None:
        # The object's name is still 'None', so skip.
        return

    if value.__parent__ is None and value.__name__ != u'':
        # Our parent doesn't have a parent, and it's not root either.
        return

    old_path = target.path
    line = tuple(reversed(tuple(lineage(value))))
    names = [node.__name__ for node in line]
    if None in names:
        # If any of our parents don't have a name yet, skip
        return

    target_path = u'/'.join(node.__name__ for node in line)
    target_path += u'/{0}/'.format(target.__name__)
    target.path = target_path

    if old_path and target.id is not None:
        _update_children_paths(old_path, target_path)
    else:
        # We might not have had a path before, but we might still have
        # children.  This is the case when we create an object with
        # children before we assign the object itself to a parent.
        for child in _all_children(target):
            child.path = u'{0}{1}/'.format(child.__parent__.path,
                                           child.__name__)

 def render_pathbar(self):
     response = {}
     response['resource_url'] = resource_url
     path = list(lineage(self.context))
     path.reverse()
     response['path'] = tuple(path)
     return render('templates/snippets/pathbar.pt', response, request=self.request)

def local_principals(context, principals):
    local_principals = set()

    block = False
    for location in lineage(context):
        if block:
            break

        block = getattr(location, '__ac_local_roles_block__', False)
        local_roles = getattr(location, '__ac_local_roles__', None)

        if local_roles and callable(local_roles):
            local_roles = local_roles()

        if not local_roles:
            continue

        for principal in principals:
            try:
                roles = local_roles[principal]
            except KeyError:
                pass
            else:
                if not is_nonstr_iter(roles):
                    roles = [roles]
                local_principals.update(roles)

    if not local_principals:
        return principals

    local_principals.update(principals)
    return local_principals

def list_groups_ext(name, context=None, _seen=None, _inherited=None):
    name = name
    groups = set()
    recursing = _inherited is not None
    _inherited = _inherited or set()

    # Add groups from principal db:
    principal = get_principals().get(name)
    if principal is not None:
        groups.update(principal.groups)
        if context is not None or (context is None and _seen is not None):
            _inherited.update(principal.groups)

    if _seen is None:
        _seen = {name}

    # Add local groups:
    if context is not None:
        items = lineage(context)
        for idx, item in enumerate(items):
            group_names = [i for i in list_groups_raw(name, item)
                           if i not in _seen]
            groups.update(group_names)
            if recursing or idx != 0:
                _inherited.update(group_names)

    new_groups = groups - _seen
    _seen.update(new_groups)
    for group_name in new_groups:
        g, i = list_groups_ext(
            group_name, context, _seen=_seen, _inherited=_inherited)
        groups.update(g)
        _inherited.update(i)

    return list(groups), list(_inherited)

 def find(self, resource, content_type):
     """ Return the first object in the :term:`lineage` of the
     ``resource`` that supplies the ``content_type`` or ``None`` if no
     such object can be found."""
     for location in lineage(resource):
         if self.typeof(location) == content_type:
             return location

    def permits(self, context, principals, permission):
        """ Return an instance of
        :class:`pyramid.security.ACLAllowed` instance if the policy
        permits access, return an instance of
        :class:`pyramid.security.ACLDenied` if not."""

        acl = '<No ACL found on any object in resource lineage>'
        
        for location in lineage(context):
            try:
                acl = location.__acl__
            except AttributeError:
                continue

            for ace in acl:
                ace_action, ace_principal, ace_permissions = ace
                if ace_principal in principals:
                    if not hasattr(ace_permissions, '__iter__'):
                        ace_permissions = [ace_permissions]
                    if permission in ace_permissions:
                        if ace_action == Allow:
                            return ACLAllowed(ace, acl, permission,
                                              principals, location)
                        else:
                            return ACLDenied(ace, acl, permission,
                                             principals, location)

        # default deny (if no ACL in lineage at all, or if none of the
        # principals were mentioned in any ACE we found)
        return ACLDenied(
            '<default deny>',
            acl,
            permission,
            principals,
            context)

def get_local_roles(userid, request=None, context=None):
    """ calculates local roles for userid """
    if context is None:
        context = getattr(request, "context", None)
        if context is None:
            context = getattr(request, "root", None)

    roles = OrderedDict()

    if IOwnersAware.providedBy(context):
        if userid == context.__owner__:
            roles[Owner.id] = Allow

    for location in lineage(context):
        if ILocalRolesAware.providedBy(location):
            local_roles = location.__local_roles__
            if local_roles:
                for r in local_roles.get(userid, ()):
                    if r not in roles:
                        roles[r] = Allow

    data = []
    for r, val in roles.items():
        if val is Allow:
            data.append(r)

    return data