1<?php
2
3require_once(dirname(__FILE__).'/plugins.php');
4require_once(dirname(__FILE__).'/tools.php');
5require_once(dirname(__FILE__).'/project_file.php');
6
7class MakeNode {
8	protected $name = NULL;
9	// points the nodes that depend on this node
10	private $links = array();
11	// all nodes that will be affected if this node is updated
12	private $affect = array();
13	public $valid = true;
14	public $ref = 0;
15	public $unconditional = false;
16	private $is_target = NULL;
17
18	public function name() { return $this->name; }
19	public function affect() { return $this->affect; }
20	public function is_target() { return $this->is_target; }
21
22	public function link($node) {
23		if (!in_array($node->name(), array_keys($this->links)))
24			$this->links[$node->name()] = $node;
25	}
26
27	public function __construct($name, $is_target) {
28		$this->name = $name;
29		$this->is_target = $is_target;
30	}
31
32	// returns an array of loops
33	public function find_affected(&$errors, $path = array()) {
34		// if already found
35		if ($this->loops != NULL || $this->affect != NULL) return;
36		// check for loops
37		if (in_array($this->name, $path)) {
38			$loop = array($this->name);
39			$next = array_pop($path);
40			while ($next != $name) {
41				$loop[] = $next;
42				$next = array_pop($path);
43			}
44			add_error($errors, $this->name, array('loop' => $loop));
45			return;
46		}
47		$loops = array();
48		$affect = array();
49		$path[] = $this->name;
50		foreach ($this->links as $link) {
51			$link->find_affected($errors, $path);
52			$new_affect = $link->affect();
53			if ($new_affect) $affect = array_merge($affect, $new_affect);
54			$affect[] = $link->name();
55		}
56		if ($affect)
57			$this->affect = array_keys(array_flip($affect));
58		else $this->affect = array();
59	}
60
61	public function mark_invalid(&$errors) {
62		if (!$this->valid) return;
63		$this->valid = false;
64		foreach ($this->links as $link) {
65			add_error($errors, $link->name(),
66				array('dependency' => $this->name));
67			if ($link->valid) $link->mark_invalid($errors);
68		}
69	}
70
71	public function mark_unconditional() {
72		$this->unconditional = true;
73		if ($this->is_target) return;
74		foreach ($this->links as $link) $link->mark_unconditional();
75	}
76
77	public function ref() {
78		if ($this->ref == 0)
79			foreach ($this->links as $link) $link->ref();
80		$this->ref++;
81	}
82
83	public function unref(&$node_refs = array()) {
84		foreach ($this->links as $link) {
85			$link->ref--;
86			if ($node_refs && isset($node_refs[$link->name()]))
87				$node_refs[$link->name()] = $link->ref;
88		}
89		if ($node_refs)
90			asort($node_refs);
91	}
92}
93
94class Maker {
95	private $nodes = NULL;
96	private $project;
97	private $rules = NULL;
98	private $errors = array();
99	private $files = NULL;
100	private $parallel = false;
101	private $intermediate_files = array();
102	private $plugins = NULL;
103
104	public function __construct($project) {
105		$this->project = $project;
106		$this->plugins = new Plugins(PROJECTS_PLUGINS_TARGET_DIR);
107		$this->construct($project->files());
108		$this->parallel = function_exists('pcntl_fork');
109	}
110
111	public function errors() { return $this->errors; }
112
113	public function default_rule($file) {
114		$handlers = $this->plugins->handlers($this->project, $file);
115		if (!$handlers) return NULL;
116		reset($handlers);
117		$handler = current($handlers);
118		$default = $handler->handle($this->project, $file);
119		return $default;
120	}
121
122	// construct a dependency tree
123	private function construct(&$files) {
124		// the root node
125		$this->nodes = array();
126		$this->intermediate_files = array();
127		$this->errors = array();
128		foreach ($files as $name => $file)
129			$this->files[$name] = &$file;
130		$this->files = $files;
131		$filenames = array_keys($files);
132		$no_rules = array();
133		foreach ($this->files as $name => $file) {
134			if (!$file->makable()) {
135				$default = $this->default_rule($file);
136//					wiki_debug("default $name", $default);
137				if ($default === NULL)
138					$this->add_error($name, "undefined");
139				else {
140					$file = $default;
141					$this->files[$name] =  $file;
142				}
143			}
144			$this->nodes[$name] = new MakeNode($name, $file->is_target());
145		}
146		// link nodes reversly with dependency, i.e, if one node changed,
147		// which other nodes need to be upated
148		while ((list($name, $node) = each($this->nodes)) != false) {
149			$deps = $this->files[$name]->dependency();
150			if ($deps) foreach ($deps as $dep) {
151				if (!isset($this->nodes[$dep])) {
152					$missing = ProjectFile::create($this->project,
153						new TargetDefinition(array(
154						'name' => $dep, 'type' => TARGET)));
155					$default = $this->default_rule($missing);
156//					wiki_debug("default $dep", $default);
157					if ($default == NULL) {
158						$this->add_error($name, array('dependency' => $dep));
159						continue;
160					}
161					$this->intermediate_files[] = $dep;
162					$this->files[$dep] = $default;
163					$dep_node = new MakeNode($dep, true);
164					$this->nodes[$dep] = $dep_node;
165				}
166				else $dep_node = $this->nodes[$dep];
167				$dep_node->link($node);
168			}
169		}
170		foreach ($this->nodes as $node) $node->find_affected($this->errors);
171		// find those which are affected by the error nodes
172		$errors = array_intersect(array_keys($this->errors),
173			array_keys($this->nodes));
174		foreach ($errors as $name)
175			$this->nodes[$name]->mark_invalid($this->errors);
176		$invalid = array_keys($this->errors);
177		// drop the invalid nodes
178		$nodes = array();
179		// relink valid nodes
180		foreach ($this->nodes as $name => $node)
181			if ($node->valid)
182				$nodes[$name] = new MakeNode($name, $node->is_target());
183		foreach ($nodes as $name => $node) {
184			$deps = array_diff($this->files[$name]->dependency(), $invalid);
185			foreach ($deps as $dep) $nodes[$dep]->link($node);
186		}
187		$this->nodes = $nodes;
188	}
189
190	public function update($changes) {
191		$changes = array_merge($changes, $this->intermediate_files);
192		$changes = array_keys(array_flip($changes));
193		if (!$changes) return array();
194		$root = new MakeNode(NULL, false);
195		foreach ($changes as $key => $change) {
196			$node = $this->nodes[$change];
197			if ($node) {
198				$root->link($node);
199				$node->mark_unconditional();
200			}
201			else unset($changes[$key]);
202		}
203		$root->ref();
204		$nodes = array();
205		foreach ($this->nodes as $name => $node)
206			if ($node->ref > 0)
207				$nodes[$name] = $node->ref;
208			else $node->ref = -1;
209		if (!$nodes) return array();
210		$root->unref($nodes);
211		asort($nodes);
212        $this->make($nodes);
213		// remove stale files
214		foreach ($this->errors as $name => $error)
215			if (isset($this->files[$name])) {
216				$file = $this->files[$name];
217				if ($file->is_target())
218					$file->delete($this->project->path());
219			}
220		return array_keys($nodes);
221	}
222
223	// make the files with ref >=0 one by one
224	private function make($nodes) {
225		$this->pid = array();
226		$this->running = array();
227		while ($nodes) {
228			reset($nodes);
229			$name = key($nodes);
230			$ref = current($nodes);
231			$node = $this->nodes[$name];
232			if (!$node->valid || $node->ref < 0) {
233				unset($nodes[$name]);
234				continue;
235			}
236			if ($ref === 0) {
237				unset($nodes[$name]);
238				// if all dependency are up to date, do not need to
239				// make unless it is requested
240				$file = $this->files[$name];
241				if (!$node->unconditional) {
242					$deps = $file->dependency();
243					$drop = true;
244					foreach ($deps as $dep)
245						if ($this->nodes[$dep]->ref !== -1 ) {
246							$drop = false;
247							break;
248						}
249					if ($drop) {
250						$node->ref = -1;
251						$node->unref($nodes);
252						continue;
253					}
254				}
255				// drop source file
256				if (!$file->is_target()) {
257					$node->unref($nodes);
258					continue;
259				}
260				$this->pid[$name] = $this->make_target($file);
261				if (!$this->parallel || count($this->pid) == MAX_PARALLEL_JOBS)
262					$this->wait($nodes);
263			}
264			else {
265				if (count($this->pid) > 0)
266					$this->wait($nodes);
267				else {
268					wiki_debug('error', "maker not counting correctly");
269					wiki_debug('nodes', $nodes);
270//					wiki_debug('nodes', $this->nodes);
271					break;
272				}
273			}
274		}
275	}
276
277	private function wait(&$nodes) {
278		if ($this->parallel)
279			$pid = pcntl_wait($result);
280		else {
281			$result = current($this->pid);
282			$pid = $result;
283		}
284		$name = array_search($pid, $this->pid);
285		unset($this->pid[$name]);
286		$time = $this->times[$name];
287		unset($this->times[$name]);
288		$node = $this->nodes[$name];
289		$node->unref($nodes);
290		// check for error
291		if ($result != 0) {
292			$this->add_error($name, array("failure" => $result));
293			$node->mark_invalid($this->errors);
294			return;
295		}
296		// success, check if the node is not really updated
297		if ($time != NULL &&
298			$time == $this->files[$name]->time($this->project->path()))
299			$node->ref = -1;
300	}
301
302	private function make_target($file) {
303		$name = $file->name();
304		$this->times[$name] = $file->time($this->project->path());
305		// if all the dependent files are up-to-date, no need to make unless
306		// requested for unconditional remake.
307		if ($this->parallel) {
308			$pid = pcntl_fork();
309			// check if cannot fork
310			if ($pid == -1) $this->parallel = false;
311		}
312		if ($this->parallel && $pid > 0) return;
313		$result = $file->make($this->project->path());
314		if ($this->parallel) exit($result);
315		return $result;
316	}
317
318	private function add_error($name, $error) {
319		add_error($this->errors, $name, $error);
320	}
321
322	public function dependency_order() {
323		$order = array();
324		$errors = array();
325		foreach ($this->nodes as $node)
326			$order = array_merge($order, $node->affect($errors));
327		return array_keys(array_flip($order));
328	}
329}
330
331function add_error(&$errors, $name, $error) {
332	if (!isset($errors[$name]))
333		$errors[$name] = array($error);
334	else
335		$errors[$name][] = $error;
336}
337
338?>