SET xmloption = content;
SET client_min_messages = warning;
---
--- Name: plpgsql; Type: EXTENSION; Schema: -; Owner: -
---
-
-CREATE EXTENSION IF NOT EXISTS plpgsql WITH SCHEMA pg_catalog;
-
-
---
--- Name: EXTENSION plpgsql; Type: COMMENT; Schema: -; Owner: -
---
-
--- COMMENT ON EXTENSION plpgsql IS 'PL/pgSQL procedural language';
-
-
--
-- Name: pg_trgm; Type: EXTENSION; Schema: -; Owner: -
--
--
--- 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 $$
-/* perm_origin_uuid: The object that 'gets' or 'has' the permission.
+
+/* 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.
can_write, can_manage respectively, or 0 to revoke
permissions.
- This function is broken up into a number of clauses, described
- below.
-
- Note on query optimization:
-
- Each clause in a "with" statement is called a "common table
- expression" or CTE.
-
- In Postgres, they are evaluated in sequence and results of each CTE
- is stored in a temporary table. This means Postgres does not
- propagate constraints from later subqueries to earlier subqueries
- when they are CTEs.
-
- This is a problem if, for example, a later subquery chooses 10
- items out of a set of 1000000 defined by an earlier subquery,
- because it will always compute all 1000000 rows even if the query
- on the 1000000 rows could have been constrained. This is why
- permission_graph_edges is a view -- views are inlined so and can be
- optimized using external constraints.
-
- The query optimizer does sort the temporary tables for later use in
- joins.
-
- Final note, this query would have been almost impossible to write
- (and certainly impossible to read) without splitting it up using
- SQL "with" but unfortunately it also stumbles into a frustrating
- Postgres optimizer bug, see
- lib/refresh_permission_view.rb#update_permissions
- for details and a partial workaround.
+ 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
- /* Gets the initial set of objects potentially affected by the
- permission change, using search_permission_graph.
+ /* 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 (
union
(select traverse_graph.origin_uuid,
edges.head_uuid,
- least(edges.val,
- traverse_graph.val
- ,
- case (edges.tail_uuid = perm_origin_uuid AND
- edges.head_uuid = starting_uuid)
+ least(
+case (edges.edge_id = perm_edge_id)
when true then starting_perm
- else null
+ else edges.val
end
-),
+,
+ traverse_graph.val),
should_traverse_owned(edges.head_uuid, edges.val),
false
from permission_graph_edges as edges, traverse_graph
group by (traverse_graph.origin_uuid, target_uuid)
),
- /* Finds other inbound edges that grant permissions on the objects
- in perm_from_start, and computes permissions that originate from
- those. This is required to handle the case where there is 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.
+ /* 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 (
should_traverse_owned(edges.head_uuid, edges.val),
edges.head_uuid like '_____-j7d0g-_______________'
from permission_graph_edges as edges
- where (not (edges.tail_uuid = perm_origin_uuid and
- edges.head_uuid = starting_uuid)) and
+ 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(edges.val,
- traverse_graph.val
- ,
- case (edges.tail_uuid = perm_origin_uuid AND
- edges.head_uuid = starting_uuid)
+ least(
+case (edges.edge_id = perm_edge_id)
when true then starting_perm
- else null
+ else edges.val
end
-),
+,
+ traverse_graph.val),
should_traverse_owned(edges.head_uuid, edges.val),
false
from permission_graph_edges as edges, traverse_graph
group by (traverse_graph.origin_uuid, target_uuid)
),
- /* Combines the permissions computed in the first two phases. */
+ /* 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
Key insights:
- * Permissions are transitive (with some special cases involving
- users, this is controlled by the traverse_owned flag).
+ * For every group, the materialized_permissions lists all users
+ that can access to that group.
- * A user object can only gain permissions via an inbound edge,
- or appearing in the graph.
+ * The all_perms subquery has computed permissions on on a set of
+ objects for all inbound "origins", which are users or groups.
- * The materialized_permissions table includes the permission
- each user has on the tail end of each inbound edge.
+ * Permissions through groups are transitive.
- * The all_perms subquery has permissions for each object in the
- subgraph reachable from certain origin (tail end of an edge).
+ We can infer:
- * Therefore, for each user, we can compute user permissions on
- each object in subgraph by determining the permission the user
- has on each origin (tail end of an edge), joining that with the
- perm_origin_uuid column of all_perms, and taking the least() of
- the origin edge or all_perms val (because of the "least
- permission on the path" rule). If an object was reachable by
- more than one path (appears with more than one origin), we take
- the max() of the computed permissions.
+ 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
- * Finally, because users always have permission on themselves, the
- query also makes sure those permission rows are always
- returned.
+ 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,
$$;
---
--- 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 $$
-/* Helper function to populate trashed_groups table. This starts with
- each group owned by a user and computes the subtree under that
- group to find any groups that are trashed.
-*/
-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 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
+ 3 AS val,
+ ''::character varying AS edge_id
FROM public.users
UNION ALL
SELECT links.tail_uuid,
WHEN ((links.name)::text = 'can_write'::text) THEN 2
WHEN ((links.name)::text = 'can_manage'::text) THEN 3
ELSE 0
- END AS val
+ 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'),
+('20201103170213'),
+('20201105190435');