MDL-10971 question type multianswer: Respect quiz shuffle option
[moodle.git] / availability / classes / tree.php
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/>.
17 /**
18  * Class that holds a tree of availability conditions.
19  *
20  * @package core_availability
21  * @copyright 2014 The Open University
22  * @license http://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
23  */
25 namespace core_availability;
27 defined('MOODLE_INTERNAL') || die();
29 /**
30  * Class that holds a tree of availability conditions.
31  *
32  * The structure of this tree in JSON input data is:
33  *
34  * { op:'&', c:[] }
35  *
36  * where 'op' is one of the OP_xx constants and 'c' is an array of children.
37  *
38  * At the root level one of the following additional values must be included:
39  *
40  * op '|' or '!&'
41  *   show:true
42  *   Boolean value controlling whether a failed match causes the item to
43  *   display to students with information, or be completely hidden.
44  * op '&' or '!|'
45  *   showc:[]
46  *   Array of same length as c with booleans corresponding to each child; you
47  *   can make it be hidden or shown depending on which one they fail. (Anything
48  *   with false takes precedence.)
49  *
50  * @package core_availability
51  * @copyright 2014 The Open University
52  * @license http://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
53  */
54 class tree extends tree_node {
55     /** @var int Operator: AND */
56     const OP_AND = '&';
57     /** @var int Operator: OR */
58     const OP_OR = '|';
59     /** @var int Operator: NOT(AND) */
60     const OP_NOT_AND = '!&';
61     /** @var int Operator: NOT(OR) */
62     const OP_NOT_OR = '!|';
64     /** @var bool True if this tree is at root level */
65     protected $root;
67     /** @var string Operator type (OP_xx constant) */
68     protected $op;
70     /** @var tree_node[] Children in this branch (may be empty array if needed) */
71     protected $children;
73     /**
74      * Array of 'show information or hide completely' options for each child.
75      * This array is only set for the root tree if it is in AND or NOT OR mode,
76      * otherwise it is null.
77      *
78      * @var bool[]
79      */
80     protected $showchildren;
82     /**
83      * Single 'show information or hide completely' option for tree. This option
84      * is only set for the root tree if it is in OR or NOT AND mode, otherwise
85      * it is true.
86      *
87      * @var bool
88      */
89     protected $show;
91     /**
92      * Display a representation of this tree (used for debugging).
93      *
94      * @return string Text representation of tree
95      */
96     public function __toString() {
97         $result = '';
98         if ($this->root && is_null($this->showchildren)) {
99             $result .= $this->show ? '+' : '-';
100         }
101         $result .= $this->op . '(';
102         $first = true;
103         foreach ($this->children as $index => $child) {
104             if ($first) {
105                 $first = false;
106             } else {
107                 $result .= ',';
108             }
109             if (!is_null($this->showchildren)) {
110                 $result .= $this->showchildren[$index] ? '+' : '-';
111             }
112             $result .= (string)$child;
113         }
114         $result .= ')';
115         return $result;
116     }
118     /**
119      * Decodes availability structure.
120      *
121      * This function also validates the retrieved data as follows:
122      * 1. Data that does not meet the API-defined structure causes a
123      *    coding_exception (this should be impossible unless there is
124      *    a system bug or somebody manually hacks the database).
125      * 2. Data that meets the structure but cannot be implemented (e.g.
126      *    reference to missing plugin or to module that doesn't exist) is
127      *    either silently discarded (if $lax is true) or causes a
128      *    coding_exception (if $lax is false).
129      *
130      * @see decode_availability
131      * @param \stdClass $structure Structure (decoded from JSON)
132      * @param boolean $lax If true, throw exceptions only for invalid structure
133      * @param boolean $root If true, this is the root tree
134      * @return tree Availability tree
135      * @throws \coding_exception If data is not valid structure
136      */
137     public function __construct($structure, $lax = false, $root = true) {
138         $this->root = $root;
140         // Check object.
141         if (!is_object($structure)) {
142             throw new \coding_exception('Invalid availability structure (not object)');
143         }
145         // Extract operator.
146         if (!isset($structure->op)) {
147             throw new \coding_exception('Invalid availability structure (missing ->op)');
148         }
149         $this->op = $structure->op;
150         if (!in_array($this->op, array(self::OP_AND, self::OP_OR,
151                 self::OP_NOT_AND, self::OP_NOT_OR), true)) {
152             throw new \coding_exception('Invalid availability structure (unknown ->op)');
153         }
155         // For root tree, get show options.
156         $this->show = true;
157         $this->showchildren = null;
158         if ($root) {
159             if ($this->op === self::OP_AND || $this->op === self::OP_NOT_OR) {
160                 // Per-child show options.
161                 if (!isset($structure->showc)) {
162                     throw new \coding_exception(
163                             'Invalid availability structure (missing ->showc)');
164                 }
165                 if (!is_array($structure->showc)) {
166                     throw new \coding_exception(
167                             'Invalid availability structure (->showc not array)');
168                 }
169                 foreach ($structure->showc as $value) {
170                     if (!is_bool($value)) {
171                         throw new \coding_exception(
172                                 'Invalid availability structure (->showc value not bool)');
173                     }
174                 }
175                 // Set it empty now - add corresponding ones later.
176                 $this->showchildren = array();
177             } else {
178                 // Entire tree show option. (Note: This is because when you use
179                 // OR mode, say you have A OR B, the user does not meet conditions
180                 // for either A or B. A is set to 'show' and B is set to 'hide'.
181                 // But they don't have either, so how do we know which one to do?
182                 // There might as well be only one value.)
183                 if (!isset($structure->show)) {
184                     throw new \coding_exception(
185                             'Invalid availability structure (missing ->show)');
186                 }
187                 if (!is_bool($structure->show)) {
188                     throw new \coding_exception(
189                             'Invalid availability structure (->show not bool)');
190                 }
191                 $this->show = $structure->show;
192             }
193         }
195         // Get list of enabled plugins.
196         $pluginmanager = \core_plugin_manager::instance();
197         $enabled = $pluginmanager->get_enabled_plugins('availability');
199         // For unit tests, also allow the mock plugin type (even though it
200         // isn't configured in the code as a proper plugin).
201         if (defined('PHPUNIT_TEST')) {
202             $enabled['mock'] = true;
203         }
205         // Get children.
206         if (!isset($structure->c)) {
207             throw new \coding_exception('Invalid availability structure (missing ->c)');
208         }
209         if (!is_array($structure->c)) {
210             throw new \coding_exception('Invalid availability structure (->c not array)');
211         }
212         if (is_array($this->showchildren) && count($structure->showc) != count($structure->c)) {
213             throw new \coding_exception('Invalid availability structure (->c, ->showc mismatch)');
214         }
215         $this->children = array();
216         foreach ($structure->c as $index => $child) {
217             if (!is_object($child)) {
218                 throw new \coding_exception('Invalid availability structure (child not object)');
219             }
221             // First see if it's a condition. These have a defined type.
222             if (isset($child->type)) {
223                 // Look for a plugin of this type.
224                 $classname = '\availability_' . $child->type . '\condition';
225                 if (!array_key_exists($child->type, $enabled)) {
226                     if ($lax) {
227                         // On load of existing settings, ignore if class
228                         // doesn't exist.
229                         continue;
230                     } else {
231                         throw new \coding_exception('Unknown condition type: ' . $child->type);
232                     }
233                 }
234                 $this->children[] = new $classname($child);
235             } else {
236                 // Not a condition. Must be a subtree.
237                 $this->children[] = new tree($child, $lax, false);
238             }
239             if (!is_null($this->showchildren)) {
240                 $this->showchildren[] = $structure->showc[$index];
241             }
242         }
243     }
245     public function check_available($not, info $info, $grabthelot, $userid) {
246         // If there are no children in this group, we just treat it as available.
247         $information = '';
248         if (!$this->children) {
249             return new result(true);
250         }
252         // Get logic flags from operator.
253         list($innernot, $andoperator) = $this->get_logic_flags($not);
255         if ($andoperator) {
256             $allow = true;
257         } else {
258             $allow = false;
259         }
260         $failedchildren = array();
261         $totallyhide = !$this->show;
262         foreach ($this->children as $index => $child) {
263             // Check available and get info.
264             $childresult = $child->check_available(
265                     $innernot, $info, $grabthelot, $userid);
266             $childyes = $childresult->is_available();
267             if (!$childyes) {
268                 $failedchildren[] = $childresult;
269                 if (!is_null($this->showchildren) && !$this->showchildren[$index]) {
270                     $totallyhide = true;
271                 }
272             }
274             if ($andoperator && !$childyes) {
275                 $allow = false;
276                 // Do not exit loop at this point, as we will still include other info.
277             } else if (!$andoperator && $childyes) {
278                 // Exit loop since we are going to allow access (from this tree at least).
279                 $allow = true;
280                 break;
281             }
282         }
284         if ($allow) {
285             return new result(true);
286         } else if ($totallyhide) {
287             return new result(false);
288         } else {
289             return new result(false, $this, $failedchildren);
290         }
291     }
293     public function is_applied_to_user_lists() {
294         return true;
295     }
297     /**
298      * Tests against a user list. Users who cannot access the activity due to
299      * availability restrictions will be removed from the list.
300      *
301      * This test ONLY includes conditions which are marked as being applied to
302      * user lists. For example, group conditions are included but date
303      * conditions are not included.
304      *
305      * The function operates reasonably efficiently i.e. should not do per-user
306      * database queries. It is however likely to be fairly slow.
307      *
308      * @param array $users Array of userid => object
309      * @param bool $not If tree's parent indicates it's being checked negatively
310      * @param info $info Info about current context
311      * @param capability_checker $checker Capability checker
312      * @return array Filtered version of input array
313      */
314     public function filter_user_list(array $users, $not, info $info,
315             capability_checker $checker) {
316         // Get logic flags from operator.
317         list($innernot, $andoperator) = $this->get_logic_flags($not);
319         if ($andoperator) {
320             // For AND, start with the whole result and whittle it down.
321             $result = $users;
322         } else {
323             // For OR, start with nothing.
324             $result = array();
325             $anyconditions = false;
326         }
328         // Loop through all valid children.
329         foreach ($this->children as $index => $child) {
330             if (!$child->is_applied_to_user_lists()) {
331                 continue;
332             }
333             $childresult = $child->filter_user_list($users, $innernot, $info, $checker);
334             if ($andoperator) {
335                 $result = array_intersect_key($result, $childresult);
336             } else {
337                 // Combine results into array.
338                 foreach ($childresult as $id => $user) {
339                     $result[$id] = $user;
340                 }
341                 $anyconditions = true;
342             }
343         }
345         // For OR operator, if there were no conditions just return input.
346         if (!$andoperator && !$anyconditions) {
347             return $users;
348         } else {
349             return $result;
350         }
351     }
353     public function get_user_list_sql($not, info $info, $onlyactive) {
354         global $DB;
355         // Get logic flags from operator.
356         list($innernot, $andoperator) = $this->get_logic_flags($not);
358         // Loop through all valid children, getting SQL for each.
359         $childresults = array();
360         foreach ($this->children as $index => $child) {
361             if (!$child->is_applied_to_user_lists()) {
362                 continue;
363             }
364             $childresult = $child->get_user_list_sql($innernot, $info, $onlyactive);
365             if ($childresult[0]) {
366                 $childresults[] = $childresult;
367             } else if (!$andoperator) {
368                 // When using OR operator, if any part doesn't have restrictions,
369                 // then nor does the whole thing.
370                 return array('', array());
371             }
372         }
374         // If there are no conditions, return null.
375         if (!$childresults) {
376             return array('', array());
377         }
378         // If there is a single condition, return it.
379         if (count($childresults) === 1) {
380             return $childresults[0];
381         }
383         // Combine results using INTERSECT or UNION.
384         $outsql = null;
385         $subsql = array();
386         $outparams = array();
387         foreach ($childresults as $childresult) {
388             $subsql[] = $childresult[0];
389             $outparams = array_merge($outparams, $childresult[1]);
390         }
391         if ($andoperator) {
392             $outsql = $DB->sql_intersect($subsql, 'id');
393         } else {
394             $outsql = '(' . join(') UNION (', $subsql) . ')';
395         }
396         return array($outsql, $outparams);
397     }
399     public function is_available_for_all($not = false) {
400         // Get logic flags.
401         list($innernot, $andoperator) = $this->get_logic_flags($not);
403         // No children = always available.
404         if (!$this->children) {
405             return true;
406         }
408         // Check children.
409         foreach ($this->children as $child) {
410             $innerall = $child->is_available_for_all($innernot);
411             if ($andoperator) {
412                 // When there is an AND operator, then any child that results
413                 // in unavailable status would cause the whole thing to be
414                 // unavailable.
415                 if (!$innerall) {
416                     return false;
417                 }
418             } else {
419                 // When there is an OR operator, then any child which must only
420                 // be available means the whole thing must be available.
421                 if ($innerall) {
422                     return true;
423                 }
424             }
425         }
427         // If we get to here then for an AND operator that means everything must
428         // be available. From OR it means that everything must be possibly
429         // not available.
430         return $andoperator;
431     }
433     /**
434      * Gets full information about this tree (including all children) as HTML
435      * for display to staff.
436      *
437      * @param info $info Information about location of condition tree
438      * @throws \coding_exception If you call on a non-root tree
439      * @return string HTML data (empty string if none)
440      */
441     public function get_full_information(info $info) {
442         if (!$this->root) {
443             throw new \coding_exception('Only supported on root item');
444         }
445         return $this->get_full_information_recursive(false, $info, null, true);
446     }
448     /**
449      * Gets information about this tree corresponding to the given result
450      * object. (In other words, only conditions which the student actually
451      * fails will be shown - and nothing if display is turned off.)
452      *
453      * @param info $info Information about location of condition tree
454      * @param result $result Result object
455      * @throws \coding_exception If you call on a non-root tree
456      * @return string HTML data (empty string if none)
457      */
458     public function get_result_information(info $info, result $result) {
459         if (!$this->root) {
460             throw new \coding_exception('Only supported on root item');
461         }
462         return $this->get_full_information_recursive(false, $info, $result, true);
463     }
465     /**
466      * Gets information about this tree (including all or selected children) as
467      * HTML for display to staff or student.
468      *
469      * @param bool $not True if there is a NOT in effect
470      * @param info $info Information about location of condition tree
471      * @param result $result Result object if this is a student display, else null
472      * @param bool $root True if this is the root item
473      * @param bool $hidden Staff display; true if this tree has show=false (from parent)
474      */
475     protected function get_full_information_recursive(
476             $not, info $info, result $result = null, $root, $hidden = false) {
477         global $PAGE;
479         // Get list of children - either full list, or those which are shown.
480         $children = $this->children;
481         $staff = true;
482         if ($result) {
483             $children = $result->filter_nodes($children);
484             $staff = false;
485         }
487         // If no children, return empty string.
488         if (!$children) {
489             return '';
490         }
492         list($innernot, $andoperator) = $this->get_logic_flags($not);
494         // If there is only one child, don't bother displaying this tree
495         // (AND and OR makes no difference). Recurse to the child if a tree,
496         // otherwise display directly.
497         if (count ($children) === 1) {
498             $child = reset($children);
499             if ($this->root && is_null($result)) {
500                 if (is_null($this->showchildren)) {
501                     $childhidden = !$this->show;
502                 } else {
503                     $childhidden = !$this->showchildren[0];
504                 }
505             } else {
506                 $childhidden = $hidden;
507             }
508             if ($child instanceof tree) {
509                 return $child->get_full_information_recursive(
510                         $innernot, $info, $result, $root, $childhidden);
511             } else {
512                 if ($root) {
513                     $result = $child->get_standalone_description($staff, $innernot, $info);
514                 } else {
515                     $result = $child->get_description($staff, $innernot, $info);
516                 }
517                 if ($childhidden) {
518                     $result .= ' ' . get_string('hidden_marker', 'availability');
519                 }
520                 return $result;
521             }
522         }
524         // Multiple children, so prepare child messages (recursive).
525         $items = array();
526         $index = 0;
527         foreach ($children as $child) {
528             // Work out if this node is hidden (staff view only).
529             $childhidden = $this->root && is_null($result) &&
530                     !is_null($this->showchildren) && !$this->showchildren[$index];
531             if ($child instanceof tree) {
532                 $items[] = $child->get_full_information_recursive(
533                         $innernot, $info, $result, false, $childhidden);
534             } else {
535                 $childdescription = $child->get_description($staff, $innernot, $info);
536                 if ($childhidden) {
537                     $childdescription .= ' ' . get_string('hidden_marker', 'availability');
538                 }
539                 $items[] = $childdescription;
540             }
541             $index++;
542         }
544         // If showing output to staff, and root is set to hide completely,
545         // then include this information in the message.
546         if ($this->root) {
547             $treehidden = !$this->show && is_null($result);
548         } else {
549             $treehidden = $hidden;
550         }
552         // Format output for display.
553         $renderer = $PAGE->get_renderer('core', 'availability');
554         return $renderer->multiple_messages($root, $andoperator, $treehidden, $items);
555     }
557     /**
558      * Converts the operator for the tree into two flags used for computing
559      * the result.
560      *
561      * The 2 flags are $innernot (whether to set $not when calling for children)
562      * and $andoperator (whether to use AND or OR operator to combine children).
563      *
564      * @param bool $not Not flag passed to this tree
565      * @return array Array of the 2 flags ($innernot, $andoperator)
566      */
567     public function get_logic_flags($not) {
568         // Work out which type of logic to use for the group.
569         switch($this->op) {
570             case self::OP_AND:
571             case self::OP_OR:
572                 $negative = false;
573                 break;
574             case self::OP_NOT_AND:
575             case self::OP_NOT_OR:
576                 $negative = true;
577                 break;
578             default:
579                 throw new \coding_exception('Unknown operator');
580         }
581         switch($this->op) {
582             case self::OP_AND:
583             case self::OP_NOT_AND:
584                 $andoperator = true;
585                 break;
586             case self::OP_OR:
587             case self::OP_NOT_OR:
588                 $andoperator = false;
589                 break;
590             default:
591                 throw new \coding_exception('Unknown operator');
592         }
594         // Select NOT (or not) for children. It flips if this is a 'not' group.
595         $innernot = $negative ? !$not : $not;
597         // Select operator to use for this group. If flips for negative, because:
598         // NOT (a AND b) = (NOT a) OR (NOT b)
599         // NOT (a OR b) = (NOT a) AND (NOT b).
600         if ($innernot) {
601             $andoperator = !$andoperator;
602         }
603         return array($innernot, $andoperator);
604     }
606     public function save() {
607         $result = new \stdClass();
608         $result->op = $this->op;
609         if ($this->op === self::OP_AND || $this->op === self::OP_NOT_OR) {
610             $result->showc = $this->showchildren;
611         } else {
612             $result->show = $this->show;
613         }
614         $result->c = array();
615         foreach ($this->children as $child) {
616             $result->c[] = $child->save();
617         }
618         return $result;
619     }
621     /**
622      * Recursively gets all children of a particular class (you can use a base
623      * class to get all conditions, or a specific class).
624      *
625      * @param string $classname Full class name e.g. core_availability\condition
626      * @return array Array of nodes of that type (flattened, not a tree any more)
627      */
628     public function get_all_children($classname) {
629         $result = array();
630         $this->recursive_get_all_children($classname, $result);
631         return $result;
632     }
634     /**
635      * Internal function that implements get_all_children efficiently.
636      *
637      * @param string $classname Full class name e.g. core_availability\condition
638      * @param array $result Output array of nodes
639      */
640     protected function recursive_get_all_children($classname, array &$result) {
641         foreach ($this->children as $child) {
642             if (is_a($child, $classname)) {
643                 $result[] = $child;
644             }
645             if ($child instanceof tree) {
646                 $child->recursive_get_all_children($classname, $result);
647             }
648         }
649     }
651     public function update_after_restore($restoreid, $courseid,
652             \base_logger $logger, $name) {
653         $changed = false;
654         foreach ($this->children as $child) {
655             $thischanged = $child->update_after_restore($restoreid, $courseid,
656                     $logger, $name);
657             $changed = $changed || $thischanged;
658         }
659         return $changed;
660     }
662     public function update_dependency_id($table, $oldid, $newid) {
663         $changed = false;
664         foreach ($this->children as $child) {
665             $thischanged = $child->update_dependency_id($table, $oldid, $newid);
666             $changed = $changed || $thischanged;
667         }
668         return $changed;
669     }
671     /**
672      * Returns a JSON object which corresponds to a tree.
673      *
674      * Intended for unit testing, as normally the JSON values are constructed
675      * by JavaScript code.
676      *
677      * This function generates 'nested' (i.e. not root-level) trees.
678      *
679      * @param array $children Array of JSON objects from component children
680      * @param string $op Operator (tree::OP_xx)
681      * @return stdClass JSON object
682      * @throws coding_exception If you get parameters wrong
683      */
684     public static function get_nested_json(array $children, $op = self::OP_AND) {
686         // Check $op and work out its type.
687         switch($op) {
688             case self::OP_AND:
689             case self::OP_NOT_OR:
690             case self::OP_OR:
691             case self::OP_NOT_AND:
692                 break;
693             default:
694                 throw new \coding_exception('Invalid $op');
695         }
697         // Do simple tree.
698         $result = new \stdClass();
699         $result->op = $op;
700         $result->c = $children;
701         return $result;
702     }
704     /**
705      * Returns a JSON object which corresponds to a tree at root level.
706      *
707      * Intended for unit testing, as normally the JSON values are constructed
708      * by JavaScript code.
709      *
710      * The $show parameter can be a boolean for all OP_xx options. For OP_AND
711      * and OP_NOT_OR where you have individual show options, you can specify
712      * a boolean (same for all) or an array.
713      *
714      * @param array $children Array of JSON objects from component children
715      * @param string $op Operator (tree::OP_xx)
716      * @param bool|array $show Whether 'show' option is turned on (see above)
717      * @return stdClass JSON object ready for encoding
718      * @throws coding_exception If you get parameters wrong
719      */
720     public static function get_root_json(array $children, $op = self::OP_AND, $show = true) {
722         // Get the basic object.
723         $result = self::get_nested_json($children, $op);
725         // Check $op type.
726         switch($op) {
727             case self::OP_AND:
728             case self::OP_NOT_OR:
729                 $multishow = true;
730                 break;
731             case self::OP_OR:
732             case self::OP_NOT_AND:
733                 $multishow = false;
734                 break;
735         }
737         // Add show options depending on operator.
738         if ($multishow) {
739             if (is_bool($show)) {
740                 $result->showc = array_pad(array(), count($result->c), $show);
741             } else if (is_array($show)) {
742                 // The JSON will break if anything isn't an actual bool, so check.
743                 foreach ($show as $item) {
744                     if (!is_bool($item)) {
745                         throw new \coding_exception('$show array members must be bool');
746                     }
747                 }
748                 // Check the size matches.
749                 if (count($show) != count($result->c)) {
750                     throw new \coding_exception('$show array size does not match $children');
751                 }
752                 $result->showc = $show;
753             } else {
754                 throw new \coding_exception('$show must be bool or array');
755             }
756         } else {
757             if (!is_bool($show)) {
758                 throw new \coding_exception('For this operator, $show must be bool');
759             }
760             $result->show = $show;
761         }
763         return $result;
764     }