Merge branch 'master' into backup-convert
[moodle.git] / backup / util / helper / convert_helper.class.php
1 <?php
3 // This file is part of Moodle - http://moodle.org/
4 //
5 // Moodle is free software: you can redistribute it and/or modify
6 // it under the terms of the GNU General Public License as published by
7 // the Free Software Foundation, either version 3 of the License, or
8 // (at your option) any later version.
9 //
10 // Moodle is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with Moodle.  If not, see <http://www.gnu.org/licenses/>.
18 /**
19  * Provides {@link convert_helper} and {@link convert_helper_exception} classes
20  *
21  * @package    core
22  * @subpackage backup-convert
23  * @copyright  2011 Mark Nielsen <mark@moodlerooms.com>
24  * @license    http://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
25  */
27 defined('MOODLE_INTERNAL') || die();
29 require_once($CFG->dirroot . '/backup/util/includes/convert_includes.php');
31 /**
32  * Provides various functionality via its static methods
33  */
34 abstract class convert_helper {
36     /**
37      * @param string $entropy
38      * @return string random identifier
39      */
40     public static function generate_id($entropy) {
41         return md5(time() . '-' . $entropy . '-' . random_string(20));
42     }
44     /**
45      * Returns the list of all available converters and loads their classes
46      *
47      * Converter must be installed as a directory in backup/converter/ and its
48      * method is_available() must return true to get to the list.
49      *
50      * @see base_converter::is_available()
51      * @return array of strings
52      */
53     public static function available_converters() {
54         global $CFG;
56         $converters = array();
57         $plugins    = get_list_of_plugins('backup/converter');
58         foreach ($plugins as $name) {
59             $classfile = "$CFG->dirroot/backup/converter/$name/lib.php";
60             $classname = "{$name}_converter";
62             if (!file_exists($classfile)) {
63                 throw new convert_helper_exception('converter_classfile_not_found', $classfile);
64             }
65             require_once($classfile);
67             if (!class_exists($classname)) {
68                 throw new convert_helper_exception('converter_classname_not_found', $classname);
69             }
71             if (call_user_func($classname .'::is_available')) {
72                 $converters[] = $name;
73             }
74         }
76         return $converters;
77     }
79     /**
80      * Detects if the given folder contains an unpacked moodle2 backup
81      *
82      * @param string $tempdir the name of the backup directory
83      * @return boolean true if moodle2 format detected, false otherwise
84      */
85     public static function detect_moodle2_format($tempdir) {
86         global $CFG;
88         $dirpath    = $CFG->dataroot . '/temp/backup/' . $tempdir;
89         $filepath   = $dirpath . '/moodle_backup.xml';
91         if (!is_dir($dirpath)) {
92             throw new converter_helper_exception('tmp_backup_directory_not_found', $dirpath);
93         }
95         if (!file_exists($filepath)) {
96             return false;
97         }
99         $handle     = fopen($filepath, 'r');
100         $firstchars = fread($handle, 200);
101         $status     = fclose($handle);
103         if (strpos($firstchars,'<?xml version="1.0" encoding="UTF-8"?>') !== false and
104             strpos($firstchars,'<moodle_backup>') !== false and
105             strpos($firstchars,'<information>') !== false) {
106                 return true;
107         }
109         return false;
110     }
112     /**
113      * Converts the given directory with the backup into moodle2 format
114      *
115      * @param string $tempdir The directory to convert
116      * @param string $format The current format, if already detected
117      * @throws convert_helper_exception
118      * @return bool false if unable to find the conversion path, true otherwise
119      */
120     public static function to_moodle2_format($tempdir, $format = null) {
122         if (is_null($format)) {
123             $format = backup_general_helper::detect_backup_format($tempdir);
124         }
126         // get the supported conversion paths from all available converters
127         $converters   = convert_factory::available_converters();
128         $descriptions = array();
129         foreach ($converters as $name) {
130             $classname = "{$name}_converter";
131             if (!class_exists($classname)) {
132                 throw new convert_helper_exception('class_not_loaded', $classname);
133             }
134             $descriptions[$name] = call_user_func($classname .'::description');
135         }
137         // choose the best conversion path for the given format
138         $path = self::choose_conversion_path($format, $descriptions);
140         if (empty($path)) {
141             // unable to convert
142             return false;
143         }
145         foreach ($path as $name) {
146             $converter = convert_factory::converter($name, $tempdir);
147             $converter->convert();
148         }
150         // make sure we ended with moodle2 format
151         if (!self::detect_moodle2_format($tempdir)) {
152             throw new convert_helper_exception('conversion_failed');
153         }
155         return true;
156     }
158    /**
159     * Inserts an inforef into the conversion temp table
160     */
161     public static function set_inforef($contextid) {
162         global $DB;
163     }
165     public static function get_inforef($contextid) {
166     }
168     /**
169      * Converts a plain old php object (popo?) into a string...
170      * Useful for debuging failed db inserts, or anything like that
171      */
172     public static function obj_to_readable($obj) {
173         $mapper = function($field, $value) { return "$field=$value"; };
174         $fields = get_object_vars($obj);
176         return implode(", ", array_map($mapper, array_keys($fields), array_values($fields)));
177     }
179     /// end of public API //////////////////////////////////////////////////////
181     /**
182      * Choose the best conversion path for the given format
183      *
184      * Given the source format and the list of available converters and their properties,
185      * this methods picks the most effective way how to convert the source format into
186      * the target moodle2 format. The method returns a list of converters that should be
187      * called, in order.
188      *
189      * This implementation uses Dijkstra's algorithm to find the shortest way through
190      * the oriented graph.
191      *
192      * @see http://en.wikipedia.org/wiki/Dijkstra's_algorithm
193      * @author David Mudrak <david@moodle.com>
194      * @param string $format the source backup format, one of backup::FORMAT_xxx
195      * @param array $descriptions list of {@link base_converter::description()} indexed by the converter name
196      * @return array ordered list of converter names to call (may be empty if not reachable)
197      */
198     protected static function choose_conversion_path($format, array $descriptions) {
200         // construct an oriented graph of conversion paths. backup formats are nodes
201         // and the the converters are edges of the graph.
202         $paths = array();   // [fromnode][tonode] => converter
203         foreach ($descriptions as $converter => $description) {
204             $from   = $description['from'];
205             $to     = $description['to'];
206             $cost   = $description['cost'];
208             if (is_null($from) or $from === backup::FORMAT_UNKNOWN or
209                 is_null($to) or $to === backup::FORMAT_UNKNOWN or
210                 is_null($cost) or $cost <= 0) {
211                     throw new convert_helper_exception('invalid_converter_description', $converter);
212             }
214             if (!isset($paths[$from][$to])) {
215                 $paths[$from][$to] = $converter;
216             } else {
217                 // if there are two converters available for the same conversion
218                 // path, choose the one with the lowest cost. if there are more
219                 // available converters with the same cost, the chosen one is
220                 // undefined (depends on the order of processing)
221                 if ($descriptions[$paths[$from][$to]]['cost'] > $cost) {
222                     $paths[$from][$to] = $converter;
223                 }
224             }
225         }
227         if (empty($paths)) {
228             // no conversion paths available
229             return array();
230         }
232         // now use Dijkstra's algorithm and find the shortest conversion path
234         $dist = array(); // list of nodes and their distances from the source format
235         $prev = array(); // list of previous nodes in optimal path from the source format
236         foreach ($paths as $fromnode => $tonodes) {
237             $dist[$fromnode] = null; // infinitive distance, can't be reached
238             $prev[$fromnode] = null; // unknown
239             foreach ($tonodes as $tonode => $converter) {
240                 $dist[$tonode] = null; // infinitive distance, can't be reached
241                 $prev[$tonode] = null; // unknown
242             }
243         }
245         if (!array_key_exists($format, $dist)) {
246             return array();
247         } else {
248             $dist[$format] = 0;
249         }
251         $queue = array_flip(array_keys($dist));
252         while (!empty($queue)) {
253             // find the node with the smallest distance from the source in the queue
254             // in the first iteration, this will find the original format node itself
255             $closest = null;
256             foreach ($queue as $node => $undefined) {
257                 if (is_null($dist[$node])) {
258                     continue;
259                 }
260                 if (is_null($closest) or ($dist[$node] < $dist[$closest])) {
261                     $closest = $node;
262                 }
263             }
265             if (is_null($closest) or is_null($dist[$closest])) {
266                 // all remaining nodes are inaccessible from source
267                 break;
268             }
270             if ($closest === backup::FORMAT_MOODLE) {
271                 // bingo we can break now
272                 break;
273             }
275             unset($queue[$closest]);
277             // visit all neighbors and update distances to them eventually
279             if (!isset($paths[$closest])) {
280                 continue;
281             }
282             $neighbors = array_keys($paths[$closest]);
283             // keep just neighbors that are in the queue yet
284             foreach ($neighbors as $ix => $neighbor) {
285                 if (!array_key_exists($neighbor, $queue)) {
286                     unset($neighbors[$ix]);
287                 }
288             }
290             foreach ($neighbors as $neighbor) {
291                 // the alternative distance to the neighbor if we went thru the
292                 // current $closest node
293                 $alt = $dist[$closest] + $descriptions[$paths[$closest][$neighbor]]['cost'];
295                 if (is_null($dist[$neighbor]) or $alt < $dist[$neighbor]) {
296                     // we found a shorter way to the $neighbor, remember it
297                     $dist[$neighbor] = $alt;
298                     $prev[$neighbor] = $closest;
299                 }
300             }
301         }
303         if (is_null($dist[backup::FORMAT_MOODLE])) {
304             // unable to find a conversion path, the target format not reachable
305             return array();
306         }
308         // reconstruct the optimal path from the source format to the target one
309         $conversionpath = array();
310         $target         = backup::FORMAT_MOODLE;
311         while (isset($prev[$target])) {
312             array_unshift($conversionpath, $paths[$prev[$target]][$target]);
313             $target = $prev[$target];
314         }
316         return $conversionpath;
317     }
320 /**
321  * General convert_helper related exception
322  *
323  * @author David Mudrak <david@moodle.com>
324  */
325 class convert_helper_exception extends moodle_exception {
327     /**
328      * Constructor
329      *
330      * @param string $errorcode key for the corresponding error string
331      * @param object $a extra words and phrases that might be required in the error string
332      * @param string $debuginfo optional debugging information
333      */
334     public function __construct($errorcode, $a = null, $debuginfo = null) {
335         parent::__construct($errorcode, '', '', $a, $debuginfo);
336     }