[Summary view]

Differences Between: [Versions 311 and 400] [Versions 311 and 401] [Versions 311 and 402] [Versions 311 and 403]

   1  <?php
   2  // This file is part of Moodle - http://moodle.org/
   3  //
   4  // Moodle is free software: you can redistribute it and/or modify
   5  // it under the terms of the GNU General Public License as published by
   6  // the Free Software Foundation, either version 3 of the License, or
   7  // (at your option) any later version.
   8  //
   9  // Moodle is distributed in the hope that it will be useful,
  10  // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  // GNU General Public License for more details.
  13  //
  14  // You should have received a copy of the GNU General Public License
  15  // along with Moodle.  If not, see <http://www.gnu.org/licenses/>.
  16  
  17  /**
  18   * Helper functions to implement the complex get_user_capability_course function.
  19   *
  20   * @package core
  21   * @copyright 2017 The Open University
  22   * @license http://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
  23   */
  24  
  25  namespace core\access;
  26  
  27  defined('MOODLE_INTERNAL') || die();
  28  
  29  /**
  30   * Helper functions to implement the complex get_user_capability_course function.
  31   *
  32   * @package core
  33   * @copyright 2017 The Open University
  34   * @license http://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
  35   */
  36  class get_user_capability_course_helper {
  37      /**
  38       * Based on the given user's access data (roles) and system role definitions, works out
  39       * an array of capability values at each relevant context for the given user and capability.
  40       *
  41       * This is organised by the effective context path (the one at which the capability takes
  42       * effect) and then by role id. Note, however, that the resulting array only has
  43       * the information that will be needed later. If there are Prohibits present in some
  44       * roles, then they cannot be overridden by other roles or role overrides in lower contexts,
  45       * therefore, such information, if any, is absent from the results.
  46       *
  47       * @param int $userid User id
  48       * @param string $capability Capability e.g. 'moodle/course:view'
  49       * @return array Array of capability constants, indexed by context path and role id
  50       */
  51      protected static function get_capability_info_at_each_context($userid, $capability) {
  52          // Get access data for user.
  53          $accessdata = get_user_accessdata($userid);
  54  
  55          // Get list of roles for user (any location) and information about these roles.
  56          $roleids = [];
  57          foreach ($accessdata['ra'] as $path => $roles) {
  58              foreach ($roles as $roleid) {
  59                  $roleids[$roleid] = true;
  60              }
  61          }
  62          $rdefs = get_role_definitions(array_keys($roleids));
  63  
  64          // A prohibit in any relevant role prevents the capability
  65          // in that context and all subcontexts. We need to track that.
  66          // Here, the array keys are the paths where there is a prohibit the values are the role id.
  67          $prohibitpaths = [];
  68  
  69          // Get data for required capability at each context path where the user has a role that can
  70          // affect it.
  71          $pathroleperms = [];
  72          foreach ($accessdata['ra'] as $rapath => $roles) {
  73  
  74              foreach ($roles as $roleid) {
  75                  // Get role definition for that role.
  76                  foreach ($rdefs[$roleid] as $rdefpath => $caps) {
  77                      // Ignore if this override/definition doesn't refer to the relevant cap.
  78                      if (!array_key_exists($capability, $caps)) {
  79                          continue;
  80                      }
  81  
  82                      // Check a role definition or override above ra.
  83                      if (self::path_is_above($rdefpath, $rapath)) {
  84                          // Note that $rdefs is sorted by path, so if a more specific override
  85                          // exists, it will be processed later and override this one.
  86                          $effectivepath = $rapath;
  87                      } else if (self::path_is_above($rapath, $rdefpath)) {
  88                          $effectivepath = $rdefpath;
  89                      } else {
  90                          // Not inside an area where the user has the role, so ignore.
  91                          continue;
  92                      }
  93  
  94                      // Check for already seen prohibits in higher context. Overrides can't change that.
  95                      if (self::any_path_is_above($prohibitpaths, $effectivepath)) {
  96                          continue;
  97                      }
  98  
  99                      // This is a releavant role assignment / permission combination. Save it.
 100                      if (!array_key_exists($effectivepath, $pathroleperms)) {
 101                          $pathroleperms[$effectivepath] = [];
 102                      }
 103                      $pathroleperms[$effectivepath][$roleid] = $caps[$capability];
 104  
 105                      // Update $prohibitpaths if necessary.
 106                      if ($caps[$capability] == CAP_PROHIBIT) {
 107                          // First remove any lower-context prohibits that might have come from other roles.
 108                          foreach ($prohibitpaths as $otherprohibitpath => $notused) {
 109                              if (self::path_is_above($effectivepath, $otherprohibitpath)) {
 110                                  unset($prohibitpaths[$otherprohibitpath]);
 111                              }
 112                          }
 113                          $prohibitpaths[$effectivepath] = $roleid;
 114                      }
 115                  }
 116              }
 117          }
 118  
 119          // Finally, if a later role had a higher-level prohibit that an earlier role,
 120          // there may be more bits we can prune - but don't prune the prohibits!
 121          foreach ($pathroleperms as $effectivepath => $roleperms) {
 122              if ($roleid = self::any_path_is_above($prohibitpaths, $effectivepath)) {
 123                  unset($pathroleperms[$effectivepath]);
 124                  $pathroleperms[$effectivepath][$roleid] = CAP_PROHIBIT;
 125              }
 126          }
 127  
 128          return $pathroleperms;
 129      }
 130  
 131      /**
 132       * Test if a context path $otherpath is the same as, or underneath, $parentpath.
 133       *
 134       * @param string $parentpath the path of the parent context.
 135       * @param string $otherpath the path of another context.
 136       * @return bool true if $otherpath is underneath (or equal to) $parentpath.
 137       */
 138      protected static function path_is_above($parentpath, $otherpath) {
 139          return preg_match('~^' . $parentpath . '($|/)~', $otherpath);
 140      }
 141  
 142      /**
 143       * Test if a context path $otherpath is the same as, or underneath, any of $prohibitpaths.
 144       *
 145       * @param array $prohibitpaths array keys are context paths.
 146       * @param string $otherpath the path of another context.
 147       * @return int releavant $roleid if $otherpath is underneath (or equal to)
 148       *      any of the $prohibitpaths, 0 otherwise (so, can be used as a bool).
 149       */
 150      protected static function any_path_is_above($prohibitpaths, $otherpath) {
 151          foreach ($prohibitpaths as $prohibitpath => $roleid) {
 152              if (self::path_is_above($prohibitpath, $otherpath)) {
 153                  return $roleid;
 154              }
 155          }
 156          return 0;
 157      }
 158  
 159      /**
 160       * Calculates a permission tree based on an array of information about role permissions.
 161       *
 162       * The input parameter must be in the format returned by get_capability_info_at_each_context.
 163       *
 164       * The output is the root of a tree of stdClass objects with the fields 'path' (a context path),
 165       * 'allow' (true or false), and 'children' (an array of similar objects).
 166       *
 167       * @param array $pathroleperms Array of permissions
 168       * @return \stdClass Root object of permission tree
 169       */
 170      protected static function calculate_permission_tree(array $pathroleperms) {
 171          // Considering each discovered context path as an inflection point, evaluate the user's
 172          // permission (based on all roles) at each point.
 173          $pathallows = [];
 174          $mindepth = 1000;
 175          $maxdepth = 0;
 176          foreach ($pathroleperms as $path => $roles) {
 177              $evaluatedroleperms = [];
 178  
 179              // Walk up the tree starting from this path.
 180              $innerpath = $path;
 181              while ($innerpath !== '') {
 182                  $roles = $pathroleperms[$innerpath];
 183  
 184                  // Evaluate roles at this path level.
 185                  foreach ($roles as $roleid => $perm) {
 186                      if (!array_key_exists($roleid, $evaluatedroleperms)) {
 187                          $evaluatedroleperms[$roleid] = $perm;
 188                      } else {
 189                          // The existing one is at a more specific level so it takes precedence
 190                          // UNLESS this is a prohibit.
 191                          if ($perm == CAP_PROHIBIT) {
 192                              $evaluatedroleperms[$roleid] = $perm;
 193                          }
 194                      }
 195                  }
 196  
 197                  // Go up to next path level (if any).
 198                  do {
 199                      $innerpath = substr($innerpath, 0, strrpos($innerpath, '/'));
 200                      if ($innerpath === '') {
 201                          // No higher level data.
 202                          break;
 203                      }
 204                  } while (!array_key_exists($innerpath, $pathroleperms));
 205              }
 206  
 207              // If we have an allow from any role, and no prohibits, then user can access this path,
 208              // else not.
 209              $allow = false;
 210              foreach ($evaluatedroleperms as $perm) {
 211                  if ($perm == CAP_ALLOW) {
 212                      $allow = true;
 213                  } else if ($perm == CAP_PROHIBIT) {
 214                      $allow = false;
 215                      break;
 216                  }
 217              }
 218  
 219              // Store the result based on path and depth so that we can process in depth order in
 220              // the next step.
 221              $depth = strlen(preg_replace('~[^/]~', '', $path));
 222              $mindepth = min($depth, $mindepth);
 223              $maxdepth = max($depth, $maxdepth);
 224              $pathallows[$depth][$path] = $allow;
 225          }
 226  
 227          // Organise into a tree structure, processing in depth order so that we have ancestors
 228          // set up before we encounter their children.
 229          $root = (object)['allow' => false, 'path' => null, 'children' => []];
 230          $nodesbypath = [];
 231          for ($depth = $mindepth; $depth <= $maxdepth; $depth++) {
 232              // Skip any missing depth levels.
 233              if (!array_key_exists($depth, $pathallows)) {
 234                  continue;
 235              }
 236              foreach ($pathallows[$depth] as $path => $allow) {
 237                  // Value for new tree node.
 238                  $leaf = (object)['allow' => $allow, 'path' => $path, 'children' => []];
 239  
 240                  // Try to find a place to join it on if there is one.
 241                  $ancestorpath = $path;
 242                  $found = false;
 243                  while ($ancestorpath) {
 244                      $ancestorpath = substr($ancestorpath, 0, strrpos($ancestorpath, '/'));
 245                      if (array_key_exists($ancestorpath, $nodesbypath)) {
 246                          $found = true;
 247                          break;
 248                      }
 249                  }
 250  
 251                  if ($found) {
 252                      $nodesbypath[$ancestorpath]->children[] = $leaf;
 253                  } else {
 254                      $root->children[] = $leaf;
 255                  }
 256                  $nodesbypath[$path] = $leaf;
 257              }
 258          }
 259  
 260          return $root;
 261      }
 262  
 263      /**
 264       * Given a permission tree (in calculate_permission_tree format), removes any subtrees that
 265       * are negative from the root. For example, if a top-level node of the permission tree has
 266       * 'false' permission then it is meaningless because the default permission is already false;
 267       * this function will remove it. However, if there is a child within that node that is positive,
 268       * then that will need to be kept.
 269       *
 270       * @param \stdClass $root Root object
 271       * @return \stdClass Filtered tree root
 272       */
 273      protected static function remove_negative_subtrees($root) {
 274          // If a node 'starts' negative, we don't need it (as negative is the default) - extract only
 275          // subtrees that start with a positive value.
 276          $positiveroot = (object)['allow' => false, 'path' => null, 'children' => []];
 277          $consider = [$root];
 278          while ($consider) {
 279              $first = array_shift($consider);
 280              foreach ($first->children as $node) {
 281                  if ($node->allow) {
 282                      // Add directly to new root.
 283                      $positiveroot->children[] = $node;
 284                  } else {
 285                      // Consider its children for adding to root (if there are any positive ones).
 286                      $consider[] = $node;
 287                  }
 288              }
 289          }
 290          return $positiveroot;
 291      }
 292  
 293      /**
 294       * Removes duplicate nodes of a tree - where a child node has the same permission as its
 295       * parent.
 296       *
 297       * @param \stdClass $parent Tree root node
 298       */
 299      protected static function remove_duplicate_nodes($parent) {
 300          $length = count($parent->children);
 301          $index = 0;
 302          while ($index < $length) {
 303              $child = $parent->children[$index];
 304              if ($child->allow === $parent->allow) {
 305                  // Remove child node, but add its children to this node instead.
 306                  array_splice($parent->children, $index, 1);
 307                  $length--;
 308                  $index--;
 309                  foreach ($child->children as $grandchild) {
 310                      $parent->children[] = $grandchild;
 311                      $length++;
 312                  }
 313              } else {
 314                  // Keep child node, but recurse to remove its unnecessary children.
 315                  self::remove_duplicate_nodes($child);
 316              }
 317              $index++;
 318          }
 319      }
 320  
 321      /**
 322       * Gets a permission tree for the given user and capability, representing the value of that
 323       * capability at different contexts across the system. The tree will be simplified as far as
 324       * possible.
 325       *
 326       * The output is the root of a tree of stdClass objects with the fields 'path' (a context path),
 327       * 'allow' (true or false), and 'children' (an array of similar objects).
 328       *
 329       * @param int $userid User id
 330       * @param string $capability Capability e.g. 'moodle/course:view'
 331       * @return \stdClass Root node of tree
 332       */
 333      protected static function get_tree($userid, $capability) {
 334          // Extract raw capability data for this user and capability.
 335          $pathroleperms = self::get_capability_info_at_each_context($userid, $capability);
 336  
 337          // Convert the raw data into a permission tree based on context.
 338          $root = self::calculate_permission_tree($pathroleperms);
 339          unset($pathroleperms);
 340  
 341          // Simplify the permission tree by removing unnecessary nodes.
 342          $root = self::remove_negative_subtrees($root);
 343          self::remove_duplicate_nodes($root);
 344  
 345          // Return the tree.
 346          return $root;
 347      }
 348  
 349      /**
 350       * Creates SQL suitable for restricting by contexts listed in the given permission tree.
 351       *
 352       * This function relies on the permission tree being in the format created by get_tree.
 353       * Specifically, all the children of the root element must be set to 'allow' permission,
 354       * children of those children must be 'not allow', children of those grandchildren 'allow', etc.
 355       *
 356       * @param \stdClass $parent Root node of permission tree
 357       * @return array Two-element array of SQL (containing ? placeholders) and then a params array
 358       */
 359      protected static function create_sql($parent) {
 360          global $DB;
 361  
 362          $sql = '';
 363          $params = [];
 364          if ($parent->path !== null) {
 365              // Except for the root element, create the condition that it applies to the context of
 366              // this element (or anything within it).
 367              $sql = ' (x.path = ? OR ' . $DB->sql_like('x.path', '?') .')';
 368              $params[] = $parent->path;
 369              $params[] = $parent->path . '/%';
 370              if ($parent->children) {
 371                  // When there are children, these are assumed to have the opposite sign i.e. if we
 372                  // are allowing the parent, we are not allowing the children, and vice versa. So
 373                  // the 'OR' clause for children will be inside this 'AND NOT'.
 374                  $sql .= ' AND NOT (';
 375              }
 376          } else if (count($parent->children) > 1) {
 377              // Place brackets in the query when it is going to be an OR of multiple conditions.
 378              $sql .= ' (';
 379          }
 380          if ($parent->children) {
 381              $first = true;
 382              foreach ($parent->children as $child) {
 383                  if ($first) {
 384                      $first = false;
 385                  } else {
 386                      $sql  .= ' OR';
 387                  }
 388  
 389                  // Recuse to get the child requirements - this will be the check that the context
 390                  // is within the child, plus possibly and 'AND NOT' for any different contexts
 391                  // within the child.
 392                  list ($childsql, $childparams) = self::create_sql($child);
 393                  $sql .= $childsql;
 394                  $params = array_merge($params, $childparams);
 395              }
 396              // Close brackets if opened above.
 397              if ($parent->path !== null || count($parent->children) > 1) {
 398                  $sql .= ')';
 399              }
 400          }
 401          return [$sql, $params];
 402      }
 403  
 404      /**
 405       * Gets SQL to restrict a query to contexts in which the user has a capability.
 406       *
 407       * This returns an array with two elements (SQL containing ? placeholders, and a params array).
 408       * The SQL is intended to be used as part of a WHERE clause. It relies on the prefix 'x' being
 409       * used for the Moodle context table.
 410       *
 411       * If the user does not have the permission anywhere at all (so that there is no point doing
 412       * the query) then the two returned values will both be false.
 413       *
 414       * @param int $userid User id
 415       * @param string $capability Capability e.g. 'moodle/course:view'
 416       * @return array Two-element array of SQL (containing ? placeholders) and then a params array
 417       */
 418      public static function get_sql($userid, $capability) {
 419          // Get a tree of capability permission at various contexts for current user.
 420          $root = self::get_tree($userid, $capability);
 421  
 422          // The root node always has permission false. If there are no child nodes then the user
 423          // cannot access anything.
 424          if (!$root->children) {
 425              return [false, false];
 426          }
 427  
 428          // Get SQL to limit contexts based on the permission tree.
 429          return self::create_sql($root);
 430  
 431      }
 432  }