| [ Index ] |
PHP Cross Reference of MantisBT |
[Summary view] [Print] [Text view]
1 <?php 2 # MantisBT - A PHP based bugtracking system 3 4 # MantisBT 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 2 of the License, or 7 # (at your option) any later version. 8 # 9 # MantisBT 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 MantisBT. If not, see <http://www.gnu.org/licenses/>. 16 17 /** 18 * Relationship Graph API 19 * 20 * This uses GraphViz utilities to generate relationship graphs for 21 * issues. Either GraphViz (for all OSs except Windows) or 22 * WinGraphviz (for Windows) must be installed in order to use this 23 * feature. 24 * 25 * Graphviz is available at: 26 * - http://www.graphviz.org/ 27 * - http://www.research.att.com/sw/tools/graphviz/ 28 * 29 * WinGraphviz is available at: 30 * - http://home.so-net.net.tw/oodtsen/wingraphviz/ 31 * 32 * Most Linux distributions already have a GraphViz package 33 * conveniently available for download and install. Refer to 34 * config_defaults_inc.php for how to enable this feature once 35 * GraphViz is installed. 36 * 37 * @package CoreAPI 38 * @subpackage RelationshipGraphAPI 39 * @author Juliano Ravasi Ferraz <jferraz at users sourceforge net> 40 * @copyright Copyright (C) 2000 - 2002 Kenzaburo Ito - kenito@300baud.org 41 * @copyright Copyright (C) 2002 - 2011 MantisBT Team - mantisbt-dev@lists.sourceforge.net 42 * @link http://www.mantisbt.org 43 * 44 * @uses access_api.php 45 * @uses bug_api.php 46 * @uses config_api.php 47 * @uses constant_inc.php 48 * @uses graphviz_api.php 49 * @uses helper_api.php 50 * @uses relationship_api.php 51 * @uses string_api.php 52 * @uses utility_api.php 53 */ 54 55 require_api( 'access_api.php' ); 56 require_api( 'bug_api.php' ); 57 require_api( 'config_api.php' ); 58 require_api( 'constant_inc.php' ); 59 require_api( 'graphviz_api.php' ); 60 require_api( 'helper_api.php' ); 61 require_api( 'relationship_api.php' ); 62 require_api( 'string_api.php' ); 63 require_api( 'utility_api.php' ); 64 65 /* 66 * Generate a pretty bug ID string that is safe to use in the DOT language 67 * defined at http://www.graphviz.org/doc/info/lang.html 68 * For now we allow formatted strings in these formats: 69 * - Containing only a-z, A-Z, 0-9 and _ where the first character is NOT an 70 * integer/digit. 71 * - Containing only digits 0-9. 72 * The fallback is to use the raw bug ID without any pretty formatting applied. 73 * @param int $p_bug_id ID of the bug to pretty format 74 * @return string Pretty formatted bug ID 75 */ 76 function relgraph_bug_format_id( $p_bug_id ) { 77 $t_pretty_bug_id = bug_format_id( $p_bug_id ); 78 if ( !preg_match( '/^(([a-zA-z_][0-9a-zA-Z_]*)|(\d+))$/', $t_pretty_bug_id ) ) { 79 $t_pretty_bug_id = $p_bug_id; 80 } 81 return $t_pretty_bug_id; 82 } 83 84 # Generate a relationship graph for the given issue. 85 function relgraph_generate_rel_graph( $p_bug_id, $p_bug = null ) { 86 87 # List of visited issues and their data. 88 $v_bug_list = array(); 89 $v_rel_list = array(); 90 91 # Queue for breadth-first 92 $v_queue = array(); 93 94 # Now we visit all related issues. 95 $t_max_depth = config_get( 'relationship_graph_max_depth' ); 96 97 # Put the first element into queue. 98 array_push( $v_queue, array( 0, $p_bug_id ) ); 99 100 # And now we proccess it 101 while( !empty( $v_queue ) ) { 102 list( $t_depth, $t_id ) = array_shift( $v_queue ); 103 104 if( isset( $v_bug_list[$t_id] ) ) { 105 continue; 106 } 107 108 if( !bug_exists( $t_id ) ) { 109 continue; 110 } 111 112 if( !access_has_bug_level( VIEWER, $t_id ) ) { 113 continue; 114 } 115 116 $v_bug_list[$t_id] = bug_get( $t_id, false ); 117 118 $t_relationships = relationship_get_all_src( $t_id ); 119 foreach( $t_relationships as $t_relationship ) { 120 $t_dst = $t_relationship->dest_bug_id; 121 if( BUG_DEPENDANT == $t_relationship->type ) { 122 $v_rel_list[$t_id][$t_dst] = BUG_DEPENDANT; 123 $v_rel_list[$t_dst][$t_id] = BUG_BLOCKS; 124 } else { 125 $v_rel_list[$t_id][$t_dst] = $t_relationship->type; 126 $v_rel_list[$t_dst][$t_id] = $t_relationship->type; 127 } 128 129 if( $t_depth < $t_max_depth ) { 130 array_push( $v_queue, array( $t_depth + 1, $t_dst ) ); 131 } 132 } 133 134 $t_relationships = relationship_get_all_dest( $t_id ); 135 foreach( $t_relationships as $t_relationship ) { 136 $t_dst = $t_relationship->src_bug_id; 137 if( BUG_DEPENDANT == $t_relationship->type ) { 138 $v_rel_list[$t_id][$t_dst] = BUG_BLOCKS; 139 $v_rel_list[$t_dst][$t_id] = BUG_DEPENDANT; 140 } else { 141 $v_rel_list[$t_id][$t_dst] = $t_relationship->type; 142 $v_rel_list[$t_dst][$t_id] = $t_relationship->type; 143 } 144 145 if( $t_depth < $t_max_depth ) { 146 array_push( $v_queue, array( $t_depth + 1, $t_dst ) ); 147 } 148 } 149 } 150 151 # We have already collected all the information we need to generate 152 # the graph. Now it is the matter to create a Digraph object and 153 # store the information there, along with graph formatting attributes. 154 $t_id_string = relgraph_bug_format_id( $p_bug_id ); 155 $t_graph_fontname = config_get( 'relationship_graph_fontname' ); 156 $t_graph_fontsize = config_get( 'relationship_graph_fontsize' ); 157 $t_graph_fontpath = get_font_path(); 158 $t_view_on_click = config_get( 'relationship_graph_view_on_click' ); 159 $t_neato_tool = config_get( 'neato_tool' ); 160 161 $t_graph_attributes = array(); 162 163 if( !empty( $t_graph_fontpath ) ) { 164 $t_graph_attributes['fontpath'] = $t_graph_fontpath; 165 } 166 167 $t_graph = new Graph( $t_id_string, $t_graph_attributes, $t_neato_tool ); 168 169 $t_graph->set_default_node_attr( array ( 170 'fontname' => $t_graph_fontname, 171 'fontsize' => $t_graph_fontsize, 172 'shape' => 'record', 173 'style' => 'filled', 174 'height' => '0.2', 175 'width' => '0.4' 176 ) ); 177 178 $t_graph->set_default_edge_attr( array ( 179 'style' => 'solid', 180 'color' => '#0000C0', 181 'dir' => 'none' 182 ) ); 183 184 # Add all issue nodes and edges to the graph. 185 ksort( $v_bug_list ); 186 foreach( $v_bug_list as $t_id => $t_bug ) { 187 $t_id_string = relgraph_bug_format_id( $t_id ); 188 189 if( $t_view_on_click ) { 190 $t_url = string_get_bug_view_url( $t_id ); 191 } else { 192 $t_url = "bug_relationship_graph.php?bug_id=$t_id&graph=relation"; 193 } 194 195 relgraph_add_bug_to_graph( $t_graph, $t_id_string, $t_bug, $t_url, $t_id == $p_bug_id ); 196 197 # Now add all relationship edges to the graph. 198 if( isset( $v_rel_list[$t_id] ) ) { 199 foreach( $v_rel_list[$t_id] as $t_dst => $t_relation ) { 200 201 # Do not create edges for unvisited bugs. 202 if( !isset( $v_bug_list[$t_dst] ) ) { 203 continue; 204 } 205 206 # avoid double links 207 if( $t_dst < $t_id ) { 208 continue; 209 } 210 211 $t_related_id = relgraph_bug_format_id( $t_dst ); 212 213 global $g_relationships; 214 if( isset( $g_relationships[$t_relation] ) && isset( $g_relationships[$t_relation]['#edge_style'] ) ) { 215 $t_edge_style = $g_relationships[$t_relation]['#edge_style']; 216 } else { 217 $t_edge_style = array(); 218 } 219 220 $t_graph->add_edge( $t_id_string, $t_related_id, $t_edge_style ); 221 } 222 } 223 } 224 225 return $t_graph; 226 } 227 228 # Generate a dependency relationship graph for the given issue. 229 function relgraph_generate_dep_graph( $p_bug_id, $p_bug = null, $p_horizontal = false ) { 230 231 # List of visited issues and their data. 232 $v_bug_list = array(); 233 234 # Firstly, we visit all ascendant issues and all descendant issues 235 # and collect all the necessary data in the $v_bug_list variable. 236 # We do not visit other descendants of our parents, neither other 237 # ascendants of our children, to avoid displaying too much unrelated 238 # issues. We still collect the information about those relationships, 239 # so, if these issues happen to be visited also, relationship links 240 # will be preserved. 241 # The first issue in the list is the one we are parting from. 242 if( null === $p_bug ) { 243 $p_bug = bug_get( $p_bug_id, true ); 244 } 245 246 $v_bug_list[$p_bug_id] = $p_bug; 247 $v_bug_list[$p_bug_id]->is_descendant = true; 248 $v_bug_list[$p_bug_id]->parents = array(); 249 $v_bug_list[$p_bug_id]->children = array(); 250 251 # Now we visit all ascendants of the root issue. 252 $t_relationships = relationship_get_all_dest( $p_bug_id ); 253 foreach( $t_relationships as $t_relationship ) { 254 if( $t_relationship->type != BUG_DEPENDANT ) { 255 continue; 256 } 257 258 $v_bug_list[$p_bug_id]->parents[] = $t_relationship->src_bug_id; 259 relgraph_add_parent( $v_bug_list, $t_relationship->src_bug_id ); 260 } 261 262 $t_relationships = relationship_get_all_src( $p_bug_id ); 263 foreach( $t_relationships as $t_relationship ) { 264 if( $t_relationship->type != BUG_DEPENDANT ) { 265 continue; 266 } 267 268 $v_bug_list[$p_bug_id]->children[] = $t_relationship->dest_bug_id; 269 relgraph_add_child( $v_bug_list, $t_relationship->dest_bug_id ); 270 } 271 272 # We have already collected all the information we need to generate 273 # the graph. Now it is the matter to create a Digraph object and 274 # store the information there, along with graph formatting attributes. 275 $t_id_string = relgraph_bug_format_id( $p_bug_id ); 276 $t_graph_fontname = config_get( 'relationship_graph_fontname' ); 277 $t_graph_fontsize = config_get( 'relationship_graph_fontsize' ); 278 $t_graph_fontpath = get_font_path(); 279 $t_view_on_click = config_get( 'relationship_graph_view_on_click' ); 280 $t_dot_tool = config_get( 'dot_tool' ); 281 282 $t_graph_attributes = array(); 283 284 if( !empty( $t_graph_fontpath ) ) { 285 $t_graph_attributes['fontpath'] = $t_graph_fontpath; 286 } 287 288 if( $p_horizontal ) { 289 $t_graph_attributes['rankdir'] = 'LR'; 290 $t_graph_orientation = 'horizontal'; 291 } else { 292 $t_graph_orientation = 'vertical'; 293 } 294 295 $t_graph = new Digraph( $t_id_string, $t_graph_attributes, $t_dot_tool ); 296 297 $t_graph->set_default_node_attr( array ( 298 'fontname' => $t_graph_fontname, 299 'fontsize' => $t_graph_fontsize, 300 'shape' => 'record', 301 'style' => 'filled', 302 'height' => '0.2', 303 'width' => '0.4' 304 ) ); 305 306 $t_graph->set_default_edge_attr( array ( 307 'style' => 'solid', 308 'color' => '#C00000', 309 'dir' => 'back' 310 ) ); 311 312 # Add all issue nodes and edges to the graph. 313 foreach( $v_bug_list as $t_related_bug_id => $t_related_bug ) { 314 $t_id_string = relgraph_bug_format_id( $t_related_bug_id ); 315 316 if( $t_view_on_click ) { 317 $t_url = string_get_bug_view_url( $t_related_bug_id ); 318 } else { 319 $t_url = "bug_relationship_graph.php?bug_id=$t_related_bug_id&graph=dependency&orientation=$t_graph_orientation"; 320 } 321 322 relgraph_add_bug_to_graph( $t_graph, $t_id_string, $t_related_bug, $t_url, $t_related_bug_id == $p_bug_id ); 323 324 # Now add all relationship edges to the graph. 325 foreach( $v_bug_list[$t_related_bug_id]->parents as $t_parent_id ) { 326 327 # Do not create edges for unvisited bugs. 328 if( !isset( $v_bug_list[$t_parent_id] ) ) { 329 continue; 330 } 331 332 $t_parent_node = relgraph_bug_format_id( $t_parent_id ); 333 $t_graph->add_edge( $t_parent_node, $t_id_string ); 334 } 335 } 336 337 return $t_graph; 338 } 339 340 # Internal function used to visit ascendant issues recursively. 341 function relgraph_add_parent( &$p_bug_list, $p_bug_id ) { 342 343 # If the issue is already in the list, we already visited it, just 344 # leave. 345 if( isset( $p_bug_list[$p_bug_id] ) ) { 346 return true; 347 } 348 349 # Check if the issue really exists and we have access to it. If not, 350 # it is like it didn't exist. 351 if( !bug_exists( $p_bug_id ) ) { 352 return false; 353 } 354 355 if( !access_has_bug_level( VIEWER, $p_bug_id ) ) { 356 return false; 357 } 358 359 # Add the issue to the list. 360 $p_bug_list[$p_bug_id] = bug_get( $p_bug_id, false ); 361 $p_bug_list[$p_bug_id]->is_descendant = false; 362 $p_bug_list[$p_bug_id]->parents = array(); 363 $p_bug_list[$p_bug_id]->children = array(); 364 365 # Add all parent issues to the list of parents and visit them 366 # recursively. 367 $t_relationships = relationship_get_all_dest( $p_bug_id ); 368 foreach( $t_relationships as $t_relationship ) { 369 if( $t_relationship->type != BUG_DEPENDANT ) { 370 continue; 371 } 372 373 $p_bug_list[$p_bug_id]->parents[] = $t_relationship->src_bug_id; 374 relgraph_add_parent( $p_bug_list, $t_relationship->src_bug_id ); 375 } 376 377 # Add all child issues to the list of children. Do not visit them 378 # since this will add too much data that is unrelated to the original 379 # issue, and has a potential to generate really huge graphs. 380 $t_relationships = relationship_get_all_src( $p_bug_id ); 381 foreach( $t_relationships as $t_relationship ) { 382 if( $t_relationship->type != BUG_DEPENDANT ) { 383 continue; 384 } 385 386 $p_bug_list[$p_bug_id]->children[] = $t_relationship->dest_bug_id; 387 } 388 389 return true; 390 } 391 392 # Internal function used to visit descendant issues recursively. 393 function relgraph_add_child( &$p_bug_list, $p_bug_id ) { 394 395 # Check if the issue is already in the issue list. 396 if( isset( $p_bug_list[$p_bug_id] ) ) { 397 398 # The issue is in the list, but we cannot discard it since it 399 # may be a parent issue (whose children were not visited). 400 401 if( !$p_bug_list[$p_bug_id]->is_descendant ) { 402 403 # Yes, we visited this issue as a parent... This is the case 404 # where someone set up a cyclic relationship (I really hope 405 # nobody ever do this, but should keep sanity) for this 406 # issue. We just have to finish the job, visiting all issues 407 # that were already listed by _add_parent(). 408 $p_bug_list[$p_bug_id]->is_descendant = true; 409 410 foreach( $p_bug_list[$p_bug_id]->children as $t_child ) { 411 relgraph_add_child( $p_bug_id, $t_child ); 412 } 413 } 414 } else { 415 # The issue is not in the list, proceed as usual. 416 # Check if the issue really exists and we have access to it. 417 # If not, it is like it didn't exist. 418 if( !bug_exists( $p_bug_id ) ) { 419 return false; 420 } 421 422 if( !access_has_bug_level( VIEWER, $p_bug_id ) ) { 423 return false; 424 } 425 426 # Add the issue to the list. 427 $p_bug_list[$p_bug_id] = bug_get( $p_bug_id, false ); 428 $p_bug_list[$p_bug_id]->is_descendant = true; 429 $p_bug_list[$p_bug_id]->parents = array(); 430 $p_bug_list[$p_bug_id]->children = array(); 431 432 # Add all parent issues to the list of parents. Do not visit them 433 # for the same reason we didn't visit the children of all 434 # ancestors. 435 $t_relationships = relationship_get_all_dest( $p_bug_id ); 436 foreach( $t_relationships as $t_relationship ) { 437 if( $t_relationship->type != BUG_DEPENDANT ) { 438 continue; 439 } 440 441 $p_bug_list[$p_bug_id]->parents[] = $t_relationship->src_bug_id; 442 } 443 444 # Add all child issues to the list of children and visit them 445 # recursively. 446 $t_relationships = relationship_get_all_src( $p_bug_id ); 447 foreach( $t_relationships as $t_relationship ) { 448 if( $t_relationship->type != BUG_DEPENDANT ) { 449 continue; 450 } 451 452 $p_bug_list[$p_bug_id]->children[] = $t_relationship->dest_bug_id; 453 relgraph_add_child( $p_bug_list, $t_relationship->dest_bug_id ); 454 } 455 } 456 457 return true; 458 } 459 460 # Outputs a png image for the given relationship graph, previously 461 # generated by relgraph_generate_graph_for_bug(). 462 function relgraph_output_image( $p_graph ) { 463 $p_graph->output( 'png', true ); 464 } 465 466 /** 467 * Outputs an image map in XHTML format using the <map> element for the given 468 * relationship graph. 469 * @param Graph $p_graph Relationship graph object generated from relgraph_generate_graph_for_bug() 470 * @param string $p_name The XHTML name attribute to apply to the containing <map> element 471 * @return null 472 */ 473 function relgraph_output_map( $p_graph, $p_name ) { 474 echo '<map name="' . $p_name . '">' . "\n"; 475 $p_graph->output( 'cmapx' ); 476 echo '</map>' . "\n"; 477 } 478 479 # Internal function used to add a bug to the given graph. 480 function relgraph_add_bug_to_graph( &$p_graph, $p_bug_id, $p_bug, $p_url = null, $p_highlight = false ) { 481 $t_node_attributes = array(); 482 $t_node_attributes['label'] = $p_bug_id; 483 484 if( $p_highlight ) { 485 $t_node_attributes['color'] = '#0000FF'; 486 $t_node_attributes['style'] = 'bold, filled'; 487 } else { 488 $t_node_attributes['color'] = 'black'; 489 $t_node_attributes['style'] = 'filled'; 490 } 491 492 $t_node_attributes['fillcolor'] = get_status_color( $p_bug->status ); 493 494 if( null !== $p_url ) { 495 $t_node_attributes['URL'] = $p_url; 496 } 497 498 $t_summary = string_display_line_links( $p_bug->summary ); 499 $t_status = get_enum_element( 'status', $p_bug->status ); 500 $t_node_attributes['tooltip'] = '[' . $t_status . '] ' . $t_summary; 501 502 $p_graph->add_node( $p_bug_id, $t_node_attributes ); 503 }
title
Description
Body
title
Description
Body
title
Description
Body
title
Body
| Generated: Thu Jul 28 15:48:31 2011 | Cross-referenced by PHPXref 0.7 |