--
--- Name: compute_permission_subgraph(character varying, character varying, integer); Type: FUNCTION; Schema: public; Owner: -
+-- Name: compute_permission_subgraph(character varying, character varying, integer, character varying); Type: FUNCTION; Schema: public; Owner: -
--
-CREATE FUNCTION public.compute_permission_subgraph(perm_origin_uuid character varying, starting_uuid character varying, starting_perm integer) RETURNS TABLE(user_uuid character varying, target_uuid character varying, val integer, traverse_owned boolean)
+CREATE FUNCTION public.compute_permission_subgraph(perm_origin_uuid character varying, starting_uuid character varying, starting_perm integer, perm_edge_id character varying) RETURNS TABLE(user_uuid character varying, target_uuid character varying, val integer, traverse_owned boolean)
LANGUAGE sql STABLE
AS $$
+
+/* The purpose of this function is to compute the permissions for a
+ subgraph of the database, starting from a given edge. The newly
+ computed permissions are used to add and remove rows from the main
+ permissions table.
+
+ perm_origin_uuid: The object that 'gets' the permission.
+
+ starting_uuid: The starting object the permission applies to.
+
+ starting_perm: The permission that perm_origin_uuid 'has' on
+ starting_uuid One of 1, 2, 3 for can_read,
+ can_write, can_manage respectively, or 0 to revoke
+ permissions.
+
+ perm_edge_id: Identifies the permission edge that is being updated.
+ Changes of ownership, this is starting_uuid.
+ For links, this is the uuid of the link object.
+ This is used to override the edge value in the database
+ with starting_perm. This is necessary when revoking
+ permissions because the update happens before edge is
+ actually removed.
+*/
with
-perm_from_start(perm_origin_uuid, target_uuid, val, traverse_owned) as (
- select perm_origin_uuid, target_uuid, val, traverse_owned
- from search_permission_graph(starting_uuid, starting_perm)),
+ /* Starting from starting_uuid, determine the set of objects that
+ could be affected by this permission change.
+
+ Note: We don't traverse users unless it is an "identity"
+ permission (permission origin is self).
+ */
+ perm_from_start(perm_origin_uuid, target_uuid, val, traverse_owned) as (
+
+WITH RECURSIVE
+ traverse_graph(origin_uuid, target_uuid, val, traverse_owned, starting_set) as (
+
+ values (perm_origin_uuid, starting_uuid, starting_perm,
+ should_traverse_owned(starting_uuid, starting_perm),
+ (perm_origin_uuid = starting_uuid or starting_uuid not like '_____-tpzed-_______________'))
+ union
+ (select traverse_graph.origin_uuid,
+ edges.head_uuid,
+ least(
+case (edges.edge_id = perm_edge_id)
+ when true then starting_perm
+ else edges.val
+ end
+,
+ traverse_graph.val),
+ should_traverse_owned(edges.head_uuid, edges.val),
+ false
+ from permission_graph_edges as edges, traverse_graph
+ where traverse_graph.target_uuid = edges.tail_uuid
+ and (edges.tail_uuid like '_____-j7d0g-_______________' or
+ traverse_graph.starting_set)))
+ select traverse_graph.origin_uuid, target_uuid, max(val) as val, bool_or(traverse_owned) as traverse_owned from traverse_graph
+ group by (traverse_graph.origin_uuid, target_uuid)
+),
+
+ /* Find other inbound edges that grant permissions to 'targets' in
+ perm_from_start, and compute permissions that originate from
+ those.
+
+ This is necessary for two reasons:
+
+ 1) Other users may have access to a subset of the objects
+ through other permission links than the one we started from.
+ If we don't recompute them, their permission will get dropped.
+
+ 2) There may be more than one path through which a user gets
+ permission to an object. For example, a user owns a project
+ and also shares it can_read with a group the user belongs
+ to. adding the can_read link must not overwrite the existing
+ can_manage permission granted by ownership.
+ */
additional_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
- select edges.tail_uuid as perm_origin_uuid, ps.target_uuid, ps.val,
- should_traverse_owned(ps.target_uuid, ps.val)
- from permission_graph_edges as edges, lateral search_permission_graph(edges.head_uuid, edges.val) as ps
- where (not (edges.tail_uuid = perm_origin_uuid and
- edges.head_uuid = starting_uuid)) and
- edges.tail_uuid not in (select target_uuid from perm_from_start) and
- edges.head_uuid in (select target_uuid from perm_from_start)),
-
- partial_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
+
+WITH RECURSIVE
+ traverse_graph(origin_uuid, target_uuid, val, traverse_owned, starting_set) as (
+
+ select edges.tail_uuid as origin_uuid, edges.head_uuid as target_uuid, edges.val,
+ should_traverse_owned(edges.head_uuid, edges.val),
+ edges.head_uuid like '_____-j7d0g-_______________'
+ from permission_graph_edges as edges
+ where edges.edge_id != perm_edge_id and
+ edges.tail_uuid not in (select target_uuid from perm_from_start where target_uuid like '_____-j7d0g-_______________') and
+ edges.head_uuid in (select target_uuid from perm_from_start)
+
+ union
+ (select traverse_graph.origin_uuid,
+ edges.head_uuid,
+ least(
+case (edges.edge_id = perm_edge_id)
+ when true then starting_perm
+ else edges.val
+ end
+,
+ traverse_graph.val),
+ should_traverse_owned(edges.head_uuid, edges.val),
+ false
+ from permission_graph_edges as edges, traverse_graph
+ where traverse_graph.target_uuid = edges.tail_uuid
+ and (edges.tail_uuid like '_____-j7d0g-_______________' or
+ traverse_graph.starting_set)))
+ select traverse_graph.origin_uuid, target_uuid, max(val) as val, bool_or(traverse_owned) as traverse_owned from traverse_graph
+ group by (traverse_graph.origin_uuid, target_uuid)
+),
+
+ /* Combine the permissions computed in the first two phases. */
+ all_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
select * from perm_from_start
union all
select * from additional_perms
- ),
+ )
- user_identity_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
- select users.uuid as perm_origin_uuid, ps.target_uuid, ps.val, ps.traverse_owned
- from users, lateral search_permission_graph(users.uuid, 3) as ps
- where (users.owner_uuid not in (select target_uuid from partial_perms) or
- users.owner_uuid = users.uuid) and
- users.uuid in (select target_uuid from partial_perms)
- ),
+ /* The actual query that produces rows to be added or removed
+ from the materialized_permissions table. This is the clever
+ bit.
- all_perms(perm_origin_uuid, target_uuid, val, traverse_owned) as (
- select * from partial_perms
- union
- select * from user_identity_perms
- )
+ Key insights:
+
+ * For every group, the materialized_permissions lists all users
+ that can access to that group.
+
+ * The all_perms subquery has computed permissions on on a set of
+ objects for all inbound "origins", which are users or groups.
+ * Permissions through groups are transitive.
+
+ We can infer:
+
+ 1) The materialized_permissions table declares that user X has permission N on group Y
+ 2) The all_perms result has determined group Y has permission M on object Z
+ 3) Therefore, user X has permission min(N, M) on object Z
+
+ This allows us to efficiently determine the set of users that
+ have permissions on the subset of objects, without having to
+ follow the chain of permission back up to find those users.
+
+ In addition, because users always have permission on themselves, this
+ query also makes sure those permission rows are always
+ returned.
+ */
select v.user_uuid, v.target_uuid, max(v.perm_level), bool_or(v.traverse_owned) from
(select m.user_uuid,
u.target_uuid,
u.traverse_owned
from all_perms as u, materialized_permissions as m
where u.perm_origin_uuid = m.target_uuid AND m.traverse_owned
+ AND (m.user_uuid = m.target_uuid or m.target_uuid not like '_____-tpzed-_______________')
union all
- select perm_origin_uuid as user_uuid, target_uuid, val as perm_level, traverse_owned
+ select target_uuid as user_uuid, target_uuid, 3, true
from all_perms
- where all_perms.perm_origin_uuid like '_____-tpzed-_______________') as v
+ where all_perms.target_uuid like '_____-tpzed-_______________') as v
group by v.user_uuid, v.target_uuid
$$;
---
--- Name: compute_trashed(); Type: FUNCTION; Schema: public; Owner: -
---
-
-CREATE FUNCTION public.compute_trashed() RETURNS TABLE(uuid character varying, trash_at timestamp without time zone)
- LANGUAGE sql STABLE
- AS $$
-select ps.target_uuid as group_uuid, ps.trash_at from groups,
- lateral project_subtree_with_trash_at(groups.uuid, groups.trash_at) ps
- where groups.owner_uuid like '_____-tpzed-_______________'
-$$;
-
-
--
-- Name: project_subtree_with_trash_at(character varying, timestamp without time zone); Type: FUNCTION; Schema: public; Owner: -
--
CREATE FUNCTION public.project_subtree_with_trash_at(starting_uuid character varying, starting_trash_at timestamp without time zone) RETURNS TABLE(target_uuid character varying, trash_at timestamp without time zone)
LANGUAGE sql STABLE
AS $$
+/* Starting from a project, recursively traverse all the projects
+ underneath it and return a set of project uuids and trash_at times
+ (may be null). The initial trash_at can be a timestamp or null.
+ The trash_at time propagates downward to groups it owns, i.e. when a
+ group is trashed, everything underneath it in the ownership
+ hierarchy is also considered trashed. However, this is fact is
+ recorded in the trashed_groups table, not by updating trash_at field
+ in the groups table.
+*/
WITH RECURSIVE
project_subtree(uuid, trash_at) as (
values (starting_uuid, starting_trash_at)
$$;
---
--- Name: search_permission_graph(character varying, integer); Type: FUNCTION; Schema: public; Owner: -
---
-
-CREATE FUNCTION public.search_permission_graph(starting_uuid character varying, starting_perm integer) RETURNS TABLE(target_uuid character varying, val integer, traverse_owned boolean)
- LANGUAGE sql STABLE
- AS $$
-WITH RECURSIVE
- traverse_graph(target_uuid, val, traverse_owned) as (
- values (starting_uuid, starting_perm,
- should_traverse_owned(starting_uuid, starting_perm))
- union
- (select edges.head_uuid,
- least(edges.val, traverse_graph.val,
- case traverse_graph.traverse_owned
- when true then null
- else 0
- end),
- should_traverse_owned(edges.head_uuid, edges.val)
- from permission_graph_edges as edges, traverse_graph
- where traverse_graph.target_uuid = edges.tail_uuid))
- select target_uuid, max(val), bool_or(traverse_owned) from traverse_graph
- group by (target_uuid);
-$$;
-
-
--
-- Name: should_traverse_owned(character varying, integer); Type: FUNCTION; Schema: public; Owner: -
--
CREATE FUNCTION public.should_traverse_owned(starting_uuid character varying, starting_perm integer) RETURNS boolean
- LANGUAGE sql STABLE
+ LANGUAGE sql IMMUTABLE
AS $$
+/* Helper function. Determines if permission on an object implies
+ transitive permission to things the object owns. This is always
+ true for groups, but only true for users when the permission level
+ is can_manage.
+*/
select starting_uuid like '_____-j7d0g-_______________' or
(starting_uuid like '_____-tpzed-_______________' and starting_perm >= 3);
$$;
CREATE VIEW public.permission_graph_edges AS
SELECT groups.owner_uuid AS tail_uuid,
groups.uuid AS head_uuid,
- 3 AS val
+ 3 AS val,
+ groups.uuid AS edge_id
FROM public.groups
UNION ALL
SELECT users.owner_uuid AS tail_uuid,
users.uuid AS head_uuid,
- 3 AS val
+ 3 AS val,
+ users.uuid AS edge_id
+ FROM public.users
+UNION ALL
+ SELECT users.uuid AS tail_uuid,
+ users.uuid AS head_uuid,
+ 3 AS val,
+ ''::character varying AS edge_id
FROM public.users
UNION ALL
SELECT links.tail_uuid,
WHEN ((links.name)::text = 'can_login'::text) THEN 1
WHEN ((links.name)::text = 'can_write'::text) THEN 2
WHEN ((links.name)::text = 'can_manage'::text) THEN 3
- ELSE NULL::integer
- END AS val
+ ELSE 0
+ END AS val,
+ links.uuid AS edge_id
FROM public.links
WHERE ((links.link_class)::text = 'permission'::text);
('20190808145904'),
('20190809135453'),
('20190905151603'),
-('20200501150153');
+('20200501150153'),
+('20200602141328'),
+('20200914203202');
projects / arvados.git / blobdiff