GitDiagram.js

   1 /*
   2 Copyright (C) 2005, Artem Khodush <greenkaa@gmail.com>
   3
   4 This file is licensed under the GNU General Public License version 2.
   5 */
   6
   7 if( typeof( Motion )=="undefined" ) {
   8         alert( "javascript file is omitted (Motion.js) - this page will not work properly" );
   9 }
  10
  11 if( typeof( GitDiagram )=="undefined" ) {
  12 /* arg:
  13         container_element: diagram_div
  14         style: "by-date" or "by-commit"
  15         ui_handler: function( ui_handler_arg, event_name, rest of event args )
  16         ui_handler_arg: first argument to ui_handler
  17                 ui events with their arguments are:
  18                                                 "draw"  diagram "begin"|"end"
  19                                                 "place" diagram "begin"|"end"
  20                                                 "node_init"     diagram node node_div
  21 */
  22 GitDiagram=function( arg )
  23 {
  24         this.m_container_element=arg.container_element;
  25         this.m_style = ( arg.style == "by-commit" ) ? "by-commit" : "by-date";
  26         if( arg.ui_handler==null ) {
  27                 this.m_ui_handler=function() {};
  28         }else {
  29                 this.m_ui_handler=arg.ui_handler;
  30         }
  31         this.m_ui_handler_arg=arg.ui_handler_arg;
  32         this.m_diagram_id=++GitDiagram._g_diagram_id_counter; // for assigning unique ids to subelements
  33         this.m_background_htm=""; // date columns with dates and month names. The distinction between m_background_htm and m_diagram_htm is historical.
  34         this.m_diagram_htm=""; // everything else
  35         if( typeof( jsGraphics )!="undefined" ) {
  36                 this.m_jsg=new jsGraphics( "random" ); // use this nice 2D rasterizer into DIVs - for drawing slant lines and arrows
  37                 this.m_jsg.cnv=this.m_container_element; // force it to accept real element instead of id
  38         }
  39         this.m_window_offset={ x: 0, y: 0 }; // in pixels
  40         //large
  41         this.m_pixels_per_unit=22; // scale for absolute units: distance between two adjacent trunk (horizontal) lines on the diagram.
  42         // small
  43 //              this.m_pixels_per_unit=8; // scale for absolute units: distance between two adjacent trunk (horizontal) lines on the diagram.
  44
  45         this.m_nodes={}; /* hash: SHA1 id -> object
  46         initialized in add_node
  47                 repos: array of repositories this node belongs to.
  48                 committer_time, author_time: javascriptish time_t
  49                 time: javascriptish time_t, adjusted so that no (child) node has a date earlier than the date of its parent[0]
  50                 date: javascriptish time_t, == time without time part (date only)
  51                 author: as in commit
  52                 comment: as in commit
  53                 parents: array of nodes. add_node creates nodes in m_nodes with date==null for parents.
  54                 children: array of nodes.  elements are added to parent node's children arrays by add_node.
  55                 date_column: reference to appropriate element of m_date_columns. assigned by propagate_date_time. gives node absolute_x as date_column.absolute_x+node.offset_x.
  56         assigned later
  57                 offset_y: offset relative to parent[0]. assigned by _place_node_subtree.
  58                 absolute_y: absolute y coordinate, increases downwards (1 equals to conventional distance between two adjacent lines). assigned by _propagate_absolute_y_offset_x
  59                 offset_x: horizontal offset relative to the start of the date column, in the same units as offset_y and absolute_y, assigned by _propagate_absolute_y_offset_x
  60                 line_rightmost_node - rightmost node on the horizontal line starting from this node, or null if the node is not at the beginning of a line, assigned by _place_node_subtree
  61                 coalesced_nodes - array of child nodes placed at the same point with the node (having the same date and offset_x with the node)
  62                 coalesced_to - when not null, the node is in the coalesced_nodes array of coalesced_to, hence is not drawn
  63                 popup_id - kept so that for coalesced nodes, multiple node divs (bullets) have the same popup assigned
  64         used only in by-commit drawing
  65                 line_leftmost_node - first node on the line that goes through this node
  66                 */
  67         this.m_labels={}; /* hash: SHA1 id -> object, added by add_label
  68                 tags: array of { repo: repo_name, name: label name (tags) } assigned to the id
  69                 absolute_pos: { x, y }, used by  assign_offset_x to ensure that label divs do not overlap
  70         */
  71         this.m_master={}; /* hash: repo -> "master" branch, added by add_master */
  72         this.m_date_columns=[]; /* array of { date, width, absolute_x, lines, node }, sorted by date.
  73                 elements of m_date_columns are inserted by add_node as needed, with date and width initialized with node date and 0.
  74                 each element width is determined by _propagate_absolute_y_offset_x
  75                 each element absolute_x is assigned as sum of previous columns widths at the end of place_nodes.
  76                 lines - array of objects describing trunk and merge lines that go through that column
  77                 (assigned and used only in by-commit placement and drawing) {
  78                         start_node: leftmost node on the line
  79                 }
  80                 node - the node in this column (placement routines ensure that there is only one node in each column)
  81                 short_merge - the node in this column is merged with node from the previous column
  82         */
  83         this.m_start_more_ids=[]; /* ids and repos of nodes that were encountered as parents of added nodes,  but were never added themselves.
  84                 serve as starting point for loading more commits.
  85         */
  86         this.m_repos=[]; /* distinct repositories from which nodes and labels were added
  87         */
  88         // used in drawing
  89         this.m_container_origin={ x: 0, y: 0 };
  90         // used to keep the position of the first column the same after loading more commits
  91         this.m_prev_first_column=null;
  92         // if someone wants to see the status..
  93         this.m_node_count=0;
  94         // running index to assing different colors to branch lines (done only in by-commit placement)
  95         this.m_line_color_index=0;
  96         // to keep colors assigned for particular branches and assign the same colors to same branches again after load_more
  97         this.m_assigned_colors={}; // rightmost node id => color
  98
  99         // in  firefox, if diagram div in by-commit.html obscures log table, it steals mouse events, and log table rows become non-clickable.
 100         // contract diagram div to some minimum width, and preserve original width for use in clipping etc.
 101         if( this.m_style=="by-commit" ) {
 102                 this.m_container_width=this.m_container_element.clientWidth;
 103                 this.m_container_element.style.width=1+"px";
 104         }
 105 }
 106 }
 107 GitDiagram._g_diagram_id_counter=0;
 108 GitDiagram.prototype.add_node=function( id, committer_time, author_time, author, comment, parent_ids, repo )
 109 {
 110         GitDiagram._add_repo( this.m_repos, repo );
 111         var node=this.m_nodes[id];
 112         if( node==null ) {
 113                 node={ id: id, committer_time: committer_time, author_time: author_time, author: author, comment: comment, parents: [], children: [], repos: [repo] };
 114                 this.m_nodes[id]=node;
 115         }else if( node.author!=null ) { // it's already here, but may arrive from other repo as well (it must be identical in every repo, due to SHA...)
 116                 GitDiagram._add_repo( node.repos, repo );
 117                 return;
 118         }else { // it was a stub, created as some other node's parent
 119                 GitDiagram._add_repo( node.repos, repo );
 120                 node.committer_time=committer_time;
 121                 node.author_time=author_time;
 122                 node.author=author;
 123                 node.comment=comment;
 124         }
 125         var parent;
 126         for( var parent_i=0; parent_i!=parent_ids.length; ++parent_i ) {
 127                 parent=this.m_nodes[parent_ids[parent_i]];
 128                 if( parent==null ) {
 129                         parent={ id: parent_ids[parent_i], parents: [], children: [], repos: [repo] };
 130                         this.m_nodes[parent_ids[parent_i]]=parent;
 131                 }
 132                 node.parents.push( parent );
 133                 parent.children.push( node );
 134         }
 135 }
 136 GitDiagram.prototype.add_label=function( id, label, repo, type )
 137 {
 138         if( this.m_labels[id]==null ) {
 139                 this.m_labels[id]={ tags: [] };
 140         }
 141         this.m_labels[id].tags.push( { repo: repo, name: label, type: type } );
 142         GitDiagram._add_repo( this.m_repos, repo );
 143 }
 144 GitDiagram.prototype.add_master=function( repo, label )
 145 {
 146         this.m_master[repo] = label;
 147 }
 148 GitDiagram.prototype._assign_date=function( node )
 149 {
 150         if( this.m_style=="by-commit" ) {
 151                 node.date=node.time;
 152         }else {
 153                 var dt=new Date( node.time );
 154                 var y=dt.getFullYear();
 155                 var m=dt.getMonth();
 156                 var d=dt.getDate();
 157                 node.date=(new Date( y, m, d, 0, 0, 0, 0 )).getTime();
 158         }
 159         node.date_column=this._insert_date_column( this.m_date_columns, node.date, this.m_style );
 160         if( this.m_style=="by-commit" ) {
 161                 node.date_column.node=node;
 162         }
 163 }
 164 GitDiagram.prototype._check_date_time=function( node, parent_time )
 165 {
 166         // check and assign time (push children into the future if necessary)
 167         node.time=node.committer_time;
 168         if( node.time==null || node.time<=parent_time ) {
 169                 node.time=node.author_time;
 170         }
 171         if( node.time<=parent_time ) {
 172                 node.time=parent_time+1;
 173         }
 174         this._assign_date( node );
 175 }
 176 GitDiagram.prototype._propagate_date_time=function( start_node )
 177 {
 178         // make sure that time order does not contradict to parent-child order
 179         // for now, this matters only for primary parents
 180         var nodes=[start_node];
 181         while( nodes.length>0 ) {
 182                 var current_node=nodes[0];
 183                 nodes.splice( 0, 1 );
 184                 var primary_children=GitDiagram._get_node_primary_children( current_node );
 185                 for( var child_i=0; child_i<primary_children.length; ++child_i ) {
 186                         var child=primary_children[child_i];
 187                         this._check_date_time( child, current_node.time );
 188                         nodes.push( child );
 189                 }
 190         }
 191 }
 192 GitDiagram.prototype.place_nodes=function( keep_window_offset )
 193 {
 194         this.m_ui_handler( this.m_ui_handler_arg, "place", this, "begin" );
 195         this._reset_placement_data();
 196         // node for selecting best window offset value
 197         var rightmost_leaf=null;
 198         var last_y;
 199         var bottom_shape;
 200         this.m_start_more_ids=[];
 201         var node_count=0;
 202         // since placement depends on date and date_column, two passes are needed
 203         // first, assign nodes to date_columns
 204         for( var node_id in this.m_nodes ) {
 205                 var node=this.m_nodes[node_id];
 206                 if( node.author!=null ) {
 207                         if( node.parents[0]==null || node.parents[0].author==null ) {
 208                                 node.time=node.committer_time;
 209                                 if( node.time==null ) {
 210                                         node.time=node.author_time;
 211                                 }
 212                                 this._assign_date( node );
 213                                 this._propagate_date_time( node );
 214                         }
 215                 }else {
 216                         this.m_start_more_ids.push( { id: node.id, repos: node.repos } );
 217                 }
 218                 ++node_count;
 219         }
 220         this.m_node_count=node_count;
 221         // then. loop for each node and call _place_node_subtree for each root node
 222         for( var node_id in this.m_nodes ) {
 223                 var node=this.m_nodes[node_id];
 224                 if( node.author!=null ) {
 225                         if( node.parents[0]==null || node.parents[0].author==null ) {
 226                                 var node_shapes=this._place_node_subtree( node, { date: node.date, offset: 0 } );
 227                                 if( last_y==null ) {
 228                                         last_y=0;
 229                                         bottom_shape=node_shapes[1];
 230                                 }else {
 231                                         last_y=GitDiagram._determine_branch_offset( last_y, 1, node_shapes[-1], bottom_shape );
 232                                         bottom_shape=GitDiagram._expand_shape( last_y, node_shapes[1], bottom_shape );
 233                                 }
 234                                 node.absolute_y=last_y;
 235                                 node.offset_x=GitDiagram._g_step_x[this.m_style]/2;
 236                                 this._propagate_absolute_y_offset_x( node );
 237                                 if( node.line_rightmost_node!=null ) {
 238                                         var leaf=node.line_rightmost_node;
 239                                         if( rightmost_leaf==null
 240                                           || leaf.date>rightmost_leaf.date
 241                                           || (leaf.date==rightmost_leaf.date && leaf.offset_x>rightmost_leaf.offset_x) ) {
 242                                                 rightmost_leaf=leaf;
 243                                         }
 244                                 }
 245                         }
 246                 }
 247         }
 248         // set absolute_x for date_columns
 249         var current_x=0;
 250         for( var date_column_i=0; date_column_i<this.m_date_columns.length; ++date_column_i ) {
 251                 var date_column=this.m_date_columns[date_column_i];
 252                 date_column.absolute_x=current_x;
 253                 current_x+=date_column.width;
 254         }
 255         if( this.m_style=="by-date" ) { // for by-commit, window_offset is pegged to the log table scrollTop
 256                 // another nodes that affect best window offset value
 257                 var master=null;
 258                 var rightmost_label=null;
 259                 for( var label_i in this.m_labels ) {
 260                         var label_node=this.m_nodes[label_i];
 261                         if( label_node!=null ) {
 262                                 if( label_node.children.length==0 ) { // somewhat arbitrary condition
 263                                         if( this._is_label_master( this.m_labels[label_i] )  ) {
 264                                                 master=label_node;
 265                                         }else if( rightmost_label==null
 266                                                  || label_node.date>rightmost_label.date
 267                                                  || (label_node.date==rightmost_label.date && label_node.offset_x>rightmost_label.offset_x) ) {
 268                                                 rightmost_label=label_node;
 269                                         }
 270                                 }
 271                         }
 272                 }
 273                 if( keep_window_offset ) {
 274                         if( this.m_prev_first_column!=null ) {
 275                                 // make the former first column appear at the same offset
 276                                 this.m_window_offset.x+=this.m_pixels_per_unit*this.m_prev_first_column.absolute_x;
 277                         }
 278                 }else {
 279                         // set window offset to the best value, for some value of best
 280                         var guide_node= master!=null ? master : rightmost_label!=null ? rightmost_label : rightmost_leaf;
 281                         if( guide_node!=null ) {
 282                                 var label_text_width=0;
 283                                 if( this.m_labels[guide_node.id]!=null ) {
 284                                         label_text_width=GitDiagram._g_absolute_label_letter_width*this._label_text( this.m_labels[guide_node.id] ).length;
 285                                 }
 286                                 // for y, make guide_node appear in the center
 287                                 this.m_window_offset.y=this.m_pixels_per_unit*guide_node.absolute_y-this._diagram_height()/2;
 288                                 // for x, if diagram fits in the window, center it. Otherwise, make guide_node appear at the right side.
 289                                 if( (current_x+label_text_width)*this.m_pixels_per_unit<this._diagram_width() ) {
 290                                         this.m_window_offset.x=-Math.floor( this._diagram_width()-(current_x+label_text_width)*this.m_pixels_per_unit )/2;
 291                                 }else {
 292                                         var rightmost_x=guide_node.date_column.absolute_x+guide_node.offset_x+label_text_width;
 293                                         this.m_window_offset.x=this.m_pixels_per_unit*rightmost_x-this._diagram_width()+this.m_node_pixel_size;
 294                                 }
 295                         }
 296                 }
 297         }
 298         if( this.m_style=="by-commit" ) {
 299                 this._place_by_commit_finish();
 300         }
 301         this.m_ui_handler( this.m_ui_handler_arg, "place", this, "end" );
 302 }
 303 GitDiagram.prototype.clear=function()
 304 {
 305         this._reset_drawing_divs();
 306         this._reset_placement_data();
 307         for( var node_id in this.m_nodes ) {
 308                 var node=this.m_nodes[node_id];
 309                 delete node.date_column;
 310                 delete node.parents;
 311                 delete node.children;
 312         }
 313         this.m_nodes={};
 314         this.m_labels={};
 315         this.m_master={};
 316         delete this.m_prev_first_column;
 317         delete this.m_node_pixel_size;
 318         this.m_date_columns=[];
 319         this.m_repos=[];
 320         this.m_start_more_ids=[];
 321 }
 322 GitDiagram.prototype.get_start_more_ids=function()
 323 {
 324         return this.m_start_more_ids;
 325 }
 326 // the result is correct after place_nodes
 327 GitDiagram.prototype.get_commit_count=function()
 328 {
 329         return this.m_node_count;
 330 }
 331 GitDiagram.prototype.select_node=function( node_id, color )
 332 {
 333         var node=this.m_nodes[node_id];
 334         var border= color!=null ?
 335                 ("2px solid "+color)
 336                 : node.parents.length==0 ?
 337                         ("1px solid "+GitDiagram._g_color_node_background) // root nodes are special
 338                         : "none";
 339         var node_elements=this._node_elements_for_id( node_id );
 340         var i;
 341         for( i=0; i<node_elements.length; ++i ) {
 342                 node_elements[i].style.border=border;
 343         }
 344 }
 345 // helper functions
 346 GitDiagram._add_repo=function( repos, repo ) // returns true when added
 347 {
 348         for( var repo_i=0; repo_i<repos.length; ++repo_i ) {
 349                 if( repos[repo_i]==repo ) {
 350                         return false;
 351                 }
 352         }
 353         repos.push( repo );
 354         return true;
 355 }
 356 GitDiagram._get_node_primary_children=function( node, exclude_child )
 357 {
 358         var primary_children=[];
 359         if( node!=null ) {
 360                 for( var child_i=0; child_i!=node.children.length; ++child_i ) {
 361                         var child=node.children[child_i];
 362                         if( child.parents[0]==node && (exclude_child==null || exclude_child!=child)) {
 363                                 primary_children.push( child );
 364                         }
 365                 }
 366         }
 367         return primary_children;
 368 }
 369 GitDiagram.prototype._insert_date_column=function( date_columns, date, style )
 370 {
 371         // binary search sorted date_columns array, insert if not found
 372         var date_column;
 373         if( date_columns.length==0 ) {
 374                 date_column={ date: date, width: 0, lines: [] };
 375                 date_columns.push( date_column );
 376                 this.m_node_pixel_size=GitDiagram._g_node_pixel_size[this.m_style];
 377         }else {
 378                 var low=0;
 379                 var high=date_columns.length-1;
 380                 if( date<date_columns[low].date ) {
 381                         date_column={ date: date, width: 0, lines: [] };
 382                         date_columns.unshift( date_column );
 383                 }else if( date>date_columns[high].date ) {
 384                         date_column={ date: date, width: 0, lines: [] };
 385                         date_columns.push( date_column );
 386                 }else {
 387                         while( low!=high ) {
 388                                 var mid=Math.floor( (high+low)/2 );
 389                                 if( date<=date_columns[mid].date ) {
 390                                         high=mid;
 391                                 }else if( date>=date_columns[mid+1].date ) {
 392                                         low=mid+1;
 393                                 }else {
 394                                         date_column={ date: date, width: 0, lines: [] };
 395                                         date_columns.splice( mid+1, 0, date_column );
 396                                         break;
 397                                 }
 398                         }
 399                         if( low==high ) { // there were no break in the loop, and date_columns[low].date<=date<=date_columns[high].date
 400                                 if( style=="by-commit" ) { // each node gets its own column
 401                                         date_column={ date: date, width: 0, lines: [] };
 402                                         date_columns.splice( low+1, 0, date_column );
 403                                 }else {
 404                                         date_column=date_columns[low];
 405                                 }
 406                         }
 407                 }
 408         }
 409         return date_column;
 410 }
 411 GitDiagram._node_absolute_x=function( node )
 412 {
 413         return node.date_column.absolute_x+node.offset_x;
 414 }
 415 GitDiagram._line_absolute_y=function( line_i )
 416 {
 417         return (line_i+0.5)*GitDiagram._g_step_x["by-commit"];
 418 }
 419 GitDiagram.prototype._reset_drawing_divs=function()
 420 {
 421         // re-create line and node divs after each reset
 422         if( this.m_jsg ) {
 423                 this.m_jsg.clear();
 424         }
 425         this.m_diagram_htm="";
 426         this.m_background_htm="";
 427 }
 428 GitDiagram.prototype._reset_placement_data=function()
 429 {
 430         // clear things set by placement algorithm
 431         for( var label_id in this.m_labels ) {
 432                 delete this.m_labels[label_id].absolute_pos;
 433         }
 434         for( var node_id in this.m_nodes ) {
 435                 var node=this.m_nodes[node_id];
 436                 if( node.line_rightmost_node!=null ) {
 437                         delete node.line_rightmost_node;
 438                 }
 439                 if( node.coalesced_nodes!=null ) {
 440                         delete node.coalesced_nodes;
 441                 }
 442                 if( node.coalesced_to!=null ) {
 443                         delete node.coalesced_to;
 444                 }
 445         }
 446         this.m_date_columns=[];
 447 }
 448 GitDiagram.prototype._label_text=function( label )
 449 {
 450         var show_repo=this.m_repos.length>1;
 451         var text="";
 452         for( var tag_i=0; tag_i<label.tags.length; ++tag_i ) {
 453                 if( text.length!=0 ) {
 454                         text+=",";
 455                 }
 456                 var tag=label.tags[tag_i];
 457                 if( show_repo ) {
 458                         text+=tag.repo+":";
 459                 }
 460                 text+=tag.name;
 461         }
 462         return text;
 463 }
 464 GitDiagram.prototype._is_label_master=function( label )
 465 {
 466         if( label!=null ) {
 467                 for( var tag_i=0; tag_i<label.tags.length; ++tag_i ) {
 468                         var atag = label.tags[tag_i];
 469                         if( atag.type=="h" && atag.name==this.m_master[atag.repo] ) {
 470                                 return true;
 471                         }
 472                 }
 473         }
 474         return false;
 475 }
 476 // colors
 477 GitDiagram._g_color_month_bottom_line="#444";
 478 GitDiagram._g_color_month_right_line="#888";
 479 GitDiagram._g_color_odd_day_background="#f6f6ea";
 480 GitDiagram._g_color_even_day_background="#ffffff";
 481 GitDiagram._g_color_trunk_line="#420";
 482 GitDiagram._g_color_branch_line="#420";
 483 GitDiagram._g_color_merge_line="#bce";
 484 GitDiagram._g_color_merge_arrow="#bce";
 485 GitDiagram._g_color_root_node_background="#fefef0";
 486 GitDiagram._g_color_node_background="#330";
 487 GitDiagram._g_color_node_label="#0a8000";
 488 GitDiagram._g_color_line_label="#686868";
 489 // font for months, dates and labels
 490 GitDiagram._g_font="sans-serif";
 491 GitDiagram._g_font_size="11px";
 492 // dimensions in pixels, for drawing
 493 GitDiagram._g_month_height_pixels=12;
 494 GitDiagram._g_day_height_pixels=13;
 495
 496 // large
 497 GitDiagram._g_node_pixel_size={ "by-date": 7, "by-commit": 6 };
 498 GitDiagram._g_arrow_length=12;
 499 GitDiagram._g_arrow_width=9;
 500
 501 /* // small
 502 GitDiagram._g_node_pixel_size=4;
 503 GitDiagram._g_arrow_length=2;
 504 GitDiagram._g_arrow_width=3;
 505 */
 506 // absolute dimensions, for placement. Converted to pixels with m_pixels_per_unit member of the Diagram object.
 507 GitDiagram._g_step_x={ "by-date": 0.7, "by-commit": 1 }; // in proportion to step_y which is 1 (value for by-commit being 1 is essential since in pixels, distance between nodes on x axis must be equal to the log table line height)
 508 GitDiagram._g_branch_angle=0.27; // cosine
 509 GitDiagram._g_absolute_label_height=0.8; // values just vaguely resembling actual sizes, never related to anything in drawing, used only in node placement algorithm to ensure that labels do not overlap
 510 GitDiagram._g_absolute_label_letter_width=0.25;
 511
 512 GitDiagram._g_month_names=["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"];
 513
 514 GitDiagram._g_line_colors=[
 515 "#06ea3b", // green
 516 "#243aff", // blue
 517 "#ea2a2a", // red
 518 "#32fbfb", // light blue
 519 "#ccbb00", // dark yellow
 520 "#b535c1", // magenta
 521 "#444444", // grey
 522 "#ff817d", // pink
 523 "#c12279", // reddish-violet
 524 "#f98519" // orange
 525 ];
 526
 527 // drawing functions
 528 GitDiagram.prototype._find_container_origin=function()
 529 {
 530         var elm=this.m_container_element;
 531         var container_pos=Motion.get_page_coords( elm );
 532         var positioned_pos={ x: 0, y: 0 };
 533         var doc=this.m_container_element.ownerDocument;
 534         // find positioned element (relative to which everything in container is positioned)
 535         while( elm!=null && elm!=doc.body ) {
 536                 var position="";
 537                 if( elm.currentStyle!=null ) {
 538                         position=elm.currentStyle.position;
 539                 }else if( doc.defaultView!=null && doc.defaultView.getComputedStyle!=null ) {
 540                         position=doc.defaultView.getComputedStyle( elm, "" ).getPropertyValue( "position" );
 541                 }
 542                 if( position!="" && position!="static" ) {
 543                         positioned_pos=Motion.get_page_coords( elm );
 544                         break;
 545                 }
 546                 elm=elm.parentNode;
 547         }
 548         this.m_container_origin={ x: container_pos.x-positioned_pos.x, y: container_pos.y-positioned_pos.y };
 549 }
 550 GitDiagram.prototype._to_pixels_x=function( x )
 551 {
 552         return x*this.m_pixels_per_unit-this.m_window_offset.x;
 553 }
 554 GitDiagram.prototype._to_pixels_y=function( y )
 555 {
 556         return y*this.m_pixels_per_unit-this.m_window_offset.y;
 557 }
 558 // the only place where diagram_width and diagram_height are used in by-commit drawing
 559 // is in _div_htm, and there they must not be swapped
 560 GitDiagram.prototype._diagram_width=function()
 561 {
 562         if ( this.m_style=="by-commit" ) {
 563                 return this.m_container_width;
 564         }
 565         return this.m_container_element.clientWidth;
 566 }
 567 GitDiagram.prototype._diagram_height=function()
 568 {
 569         var header_height=this.m_style=="by-date" ? GitDiagram._g_month_height_pixels+GitDiagram._g_day_height_pixels : 0;
 570         return this.m_container_element.clientHeight-header_height;
 571 }
 572 GitDiagram.prototype._max_column_x=function()
 573 {
 574         return this.m_style=="by-date" ? this.m_container_element.clientWidth : this.m_container_element.clientHeight;
 575 }
 576 GitDiagram.prototype._make_id=function( tag, id )
 577 {
 578         return "gitdiagram"+this.m_diagram_id+"__"+tag+"__"+id;
 579 }
 580 GitDiagram.prototype._match_id=function( element_id )
 581 {
 582         if( element_id!=null && element_id.match( "^gitdiagram"+this.m_diagram_id+"__(\\w+)__(\\w+)$" ) ) {
 583                 return { tag: RegExp.$1, id: RegExp.$2 };
 584         }
 585         return null;
 586 }
 587 GitDiagram.prototype._div_htm=function( arg )
 588 {
 589         var x;
 590         var y;
 591         var clip_x;
 592         var clip_y;
 593         var s=' style="';
 594         var id="";
 595         var text="";
 596         var width_height={};
 597         for( var sn in arg ) {
 598                 var val=arg[sn];
 599                 if( sn=="id" ) {
 600                         id=' id="'+val+'"';
 601                 }else if( sn=="text" ) {
 602                         text=val;
 603                 }else if( sn=="clip_x" ) {
 604                         clip_x=true;
 605                 }else if( sn=="clip_y" ) {
 606                         clip_y=true;
 607                 }else if( sn=="clip" ) {
 608                         clip_x=true;
 609                         clip_y=true;
 610                 }else if( sn=="x" && val!=null ) {
 611                         x=Math.floor( val );
 612                 }else if( sn=="y" && val!=null ) {
 613                         y=Math.floor( val );
 614                 }else if( sn=="abs_x" && val!=null ) {
 615                         x=Math.floor( this._to_pixels_x( val ) );
 616                 }else if( sn=="abs_y" && val!=null ) {
 617                         y=Math.floor( this._to_pixels_y( val ) );
 618                 }else if( (sn=="width" || sn=="height") && val!=null ) {
 619                         width_height[sn]=Math.floor( val );
 620                 }else if( (sn=="abs_width" || sn=="abs_height") && val!=null ) {
 621                         width_height[sn.substring( 4 )]=Math.floor( val*this.m_pixels_per_unit );
 622                 }else {
 623                         s+=' '+sn+':'+val+';';
 624                 }
 625         }
 626         if( this.m_style=="by-commit" ) {
 627                 // undo x offset added in draw_by_commit, change x direction, and rotate
 628                 if( x!=null ) {
 629                         x=-(x-this.m_container_element.clientHeight);
 630                 }
 631                 var t=x;
 632                 x=y;
 633                 y=t;
 634                 t=width_height["width"];
 635                 width_height["width"]=width_height["height"];
 636                 width_height["height"]=t;
 637                 if( y!=null && width_height["height"]!=null ) {
 638                         y-=width_height["height"];
 639                 }
 640         }
 641
 642         if( width_height["width"]!=null ) {
 643                 s+=" width:"+width_height["width"]+"px;";
 644         }
 645         if( width_height["height"]!=null ) {
 646                 s+=" height:"+width_height["height"]+"px;";
 647         }
 648         if( x!=null ) {
 649                 s+=' left:'+x+'px;';
 650         }
 651         if( y!=null ) {
 652                 s+=' top:'+y+'px;';
 653         }
 654         if( x!=null && y!=null ) {
 655                 s+=' position: absolute;';
 656                 if( clip_x!=null || clip_y!=null ) {
 657                         var clip_rect={ top: 0, right: 10000, bottom: 1000, left: 0 };
 658                         if( clip_x!=null ) {
 659                                 clip_rect.left=-x;
 660                                 clip_rect.right=-x+this._diagram_width();
 661                         }
 662                         if( clip_y!=null ) {
 663                                 clip_rect.top=-y;
 664                                 clip_rect.bottom=-y+this._diagram_height();
 665                         }
 666                         s+=' clip: rect('+clip_rect.top+'px '+clip_rect.right+'px '+clip_rect.bottom+'px '+clip_rect.left+'px);';
 667                 }
 668         }
 669         s+='"';
 670         return '<div'+id+s+'>'+text+'</div>';
 671 }
 672 GitDiagram.prototype._draw_month_div=function( month, year, month_start_x, month_end_x, last )
 673 {
 674         this.m_background_htm+=this._div_htm( { "font-family": GitDiagram._g_font, "font-size": GitDiagram._g_font_size, overflow: "visible", "text-align": "center",
 675                 "border-bottom": "1px solid "+GitDiagram._g_color_month_bottom_line,
 676                 "border-right" : last ? "none" : "1px solid "+GitDiagram._g_color_month_right_line,
 677                 cursor: "move", overflow: "hidden",
 678                 width: month_end_x-month_start_x-1, height: GitDiagram._g_month_height_pixels,
 679                 x: month_start_x, y: -(this.m_container_element.clientHeight-this._diagram_height()),
 680                 text: GitDiagram._g_month_names[month]+" "+year
 681         } );
 682 }
 683 GitDiagram.prototype.by_commit_column_height=function( date_column )
 684 {
 685         return date_column.lines.length*this.m_pixels_per_unit;
 686 }
 687 GitDiagram.prototype._draw_date_column_divs=function( window_pixels )
 688 {
 689         var current_x=null;
 690         var odd=false;
 691         var prev_month;
 692         var prev_year;
 693         var prev_month_x;
 694         var prev_lines={}; // line rightmost node id => { y: line y pos, prev_x: first x where line y pos become y }
 695         for( var date_column_i=0; date_column_i<this.m_date_columns.length; ++date_column_i ) {
 696                 var date_column=this.m_date_columns[date_column_i];
 697                 var next_x=date_column.absolute_x+date_column.width;
 698                 next_x=this._to_pixels_x( next_x );
 699                 var last=false;
 700                 if( next_x>0 ) {
 701                         var dt=new Date( date_column.date );
 702                         var date=dt.getDate();
 703                         var month=dt.getMonth();
 704                         var year=dt.getFullYear();
 705                         if( current_x==null ) {
 706                                 current_x=Math.max( 1, next_x-(date_column.width*this.m_pixels_per_unit) );
 707                                 prev_month=month;
 708                                 prev_year=year;
 709                                 prev_month_x=current_x;
 710                         }
 711                         if( next_x>=this._max_column_x() ) {
 712                                 next_x=this._max_column_x();
 713                                 last=true;
 714                         }
 715                         // draw it
 716                         var y=this.m_style=="by-date" ? -(this.m_container_element.clientHeight-this._diagram_height())+GitDiagram._g_month_height_pixels
 717                                                         : 0;
 718                         var height=this.m_style=="by-date" ? this.m_container_element.clientHeight-GitDiagram._g_month_height_pixels
 719                                                         : this.by_commit_column_height( date_column );
 720                         var text=this.m_style=="by-date" ? date : "";
 721                         this.m_background_htm+=this._div_htm( { "font-family": GitDiagram._g_font, "font-size": GitDiagram._g_font_size,
 722                                 overflow: "hidden", "text-align": "center",
 723                                 "background-color" : odd ? GitDiagram._g_color_odd_day_background : GitDiagram._g_color_even_day_background,
 724                                 width: next_x-current_x, height: height, x: current_x, y: y,
 725                                 text: text
 726                         } );
 727                         if( this.m_style=="by-date" ) {
 728                                 if( month!=prev_month || year!=prev_year ) {
 729                                         this._draw_month_div( prev_month, prev_year, prev_month_x, current_x, false );
 730                                         prev_month=month;
 731                                         prev_year=year;
 732                                         prev_month_x=current_x;
 733                                 }
 734                                 if( last || date_column_i==this.m_date_columns.length-1 ) {
 735                                         this._draw_month_div( prev_month, prev_year, prev_month_x, next_x, true );
 736                                 }
 737                         }
 738                         if( this.m_style=="by-commit" ) { // each column has exactly one node, so draw it here
 739                                 this._draw_node_div( date_column.node );
 740                                 // draw trunk lines here too
 741                                 var new_lines={};
 742                                 this._draw_by_commit_lines( window_pixels, date_column, last, prev_lines, new_lines, date_column_i );
 743                                 prev_lines=new_lines;
 744                         }
 745                         if( last ) {
 746                                 break;
 747                         }
 748                         current_x=next_x;
 749                 }
 750                 odd=!odd;
 751         }
 752 }
 753 GitDiagram.prototype._draw_by_commit_lines=function( window_pixels, date_column, last, prev_lines, new_lines, date_column_i )
 754 {
 755         if( date_column.short_merge ) {
 756                 var start_node=this.m_date_columns[date_column_i-1].node;
 757                 var line_color=start_node.line_leftmost_node.line_rightmost_node.line_color;
 758                 this._clip_and_draw_line( { abs_start_x: GitDiagram._node_absolute_x( start_node ),
 759                                         abs_start_y: start_node.absolute_y,
 760                                         abs_end_x: GitDiagram._node_absolute_x( date_column.node ),
 761                                         abs_end_y: date_column.node.absolute_y
 762                                         }, window_pixels, line_color, 1 );
 763         }
 764         for( var line_i=0; line_i<date_column.lines.length; ++line_i ) {
 765                 var line_id=date_column.lines[line_i].start_node.id;
 766                 var line_kind=date_column.lines[line_i].kind;
 767                 var line_index=line_kind+line_id+date_column.lines[line_i].end_node.id;
 768                 new_lines[line_index]={ y: GitDiagram._line_absolute_y( line_i ),
 769                                         kind: line_kind,
 770                                         id: line_id
 771                                 };
 772                 if( prev_lines[line_index]==null ) {
 773                         new_lines[line_index].prev_x=GitDiagram._node_absolute_x( date_column.node );
 774                         if( line_kind=="trunk" ) {
 775                                 // draw branch line
 776                                 var branch_start_node=date_column.lines[line_i].start_node;
 777                                 if( branch_start_node!=null && branch_start_node.offset_y!=null && branch_start_node.offset_y!=0 ) {
 778                                         var branch_parent=branch_start_node.parents[0];
 779                                         if( branch_parent!=null ) {
 780                                                 var line_color=branch_start_node.line_rightmost_node.line_color;
 781                                                 this._clip_and_draw_line( { abs_start_x: GitDiagram._node_absolute_x( branch_parent ),
 782                                                                         start_y: this._to_pixels_y( branch_parent.absolute_y )-1,
 783                                                                         abs_end_x: GitDiagram._node_absolute_x( date_column.node ),
 784                                                                         end_y: this._to_pixels_y( GitDiagram._line_absolute_y( line_i ) )-1
 785                                                                         }, window_pixels, line_color, 3 );
 786                                         }
 787                                 }
 788                         }else if( line_kind=="merge" ) {
 789                                 // draw the beginning of a merge line
 790                                 var merge_start_node=date_column.lines[line_i].start_node;
 791                                 var line_color=merge_start_node.line_leftmost_node.line_rightmost_node.line_color;
 792                                 var end_x= date_column.node.id==date_column.lines[line_i].end_node.id ?
 793                                                                   date_column.absolute_x // merge line ends at this column
 794                                                                 : GitDiagram._node_absolute_x( date_column.node );
 795                                 this._clip_and_draw_line( { abs_start_x: GitDiagram._node_absolute_x( merge_start_node ),
 796                                                         start_y: this._to_pixels_y( merge_start_node.absolute_y )-1,
 797                                                         abs_end_x: end_x,
 798                                                         end_y: this._to_pixels_y( GitDiagram._line_absolute_y( line_i ) )-1
 799                                                         }, window_pixels, line_color );
 800                         }
 801                 }else {
 802                         if( prev_lines[line_index].y==new_lines[line_index].y ) {
 803                                 new_lines[line_index].prev_x=prev_lines[line_index].prev_x; // vertical line continues
 804                         }else {
 805                                 var new_x=GitDiagram._node_absolute_x( date_column.node );
 806                                 var line_color=date_column.lines[line_i].start_node.line_leftmost_node.line_rightmost_node.line_color;
 807                                 var line_width= line_kind=="trunk" ? 3 : 1;
 808                                 this._draw_by_commit_straight_line( prev_lines[line_index], new_x-date_column.width, line_color, line_width );
 809                                 this._clip_and_draw_line( { abs_start_x: new_x-date_column.width, abs_end_x: new_x,
 810                                                         start_y: this._to_pixels_y( prev_lines[line_index].y )-1,
 811                                                         end_y: this._to_pixels_y( new_lines[line_index].y )-1
 812                                                         }, window_pixels, line_color, line_width );
 813                                 new_lines[line_index].prev_x=new_x;
 814                         }
 815                 }
 816                 if( line_kind=="trunk"
 817                   && line_id==date_column.node.line_leftmost_node.id
 818                   && date_column.node.id==date_column.lines[line_i].start_node.line_rightmost_node.id ) {
 819                         new_lines[line_index].ended=true;
 820                 }
 821         }
 822         for( var prev_i in prev_lines ) {
 823                 if( new_lines[prev_i]==null ) {
 824                         var line_color=this.m_nodes[prev_lines[prev_i].id].line_leftmost_node.line_rightmost_node.line_color;
 825                         var new_x=GitDiagram._node_absolute_x( date_column.node )-date_column.width;
 826                         if( prev_lines[prev_i].kind=="trunk" ) {
 827                                 this._draw_by_commit_straight_line( prev_lines[prev_i], new_x, line_color, 3 );
 828                         }else if( prev_lines[prev_i].kind=="merge" ) {
 829                                 this._draw_by_commit_straight_line( prev_lines[prev_i], new_x, line_color, 1 );
 830                                 this._clip_and_draw_line( { abs_start_x: new_x,
 831                                                                 start_y: this._to_pixels_y( prev_lines[prev_i].y )-1,
 832                                                                 abs_end_x: GitDiagram._node_absolute_x( date_column.node ),
 833                                                                 end_y: this._to_pixels_y( date_column.node.absolute_y )-1
 834                                                         }, window_pixels, line_color );
 835
 836                         }
 837                 }
 838         }
 839         if( last ) {
 840                 for( var new_i in new_lines ) {
 841                         var new_x=GitDiagram._node_absolute_x( date_column.node );
 842                         if( !new_lines[new_i].ended ) {
 843                                 new_x+=date_column.width/2;
 844                         }
 845                         this._draw_by_commit_straight_line( new_lines[new_i], new_x,
 846                                                                         this.m_nodes[new_lines[new_i].id].line_leftmost_node.line_rightmost_node.line_color, new_lines[new_i].kind=="trunk" ? 3 : 1 );
 847                 }
 848         }
 849 }
 850 GitDiagram.prototype._draw_by_commit_straight_line=function( prev_pos, new_x, line_color, line_width )
 851 {
 852         if( new_x>prev_pos.prev_x ) {
 853                 // vertical line has non-zero length
 854                 this.m_diagram_htm+=this._div_htm( { "z-index": 3, "font-size": "1px", "border-left": line_width+"px solid "+line_color,
 855                         abs_x: prev_pos.prev_x, abs_width: new_x-prev_pos.prev_x,
 856                         y: this._to_pixels_y( prev_pos.y )-1, height: 1,
 857                         clip: true
 858                 } );
 859         }
 860 }
 861 GitDiagram.prototype._draw_by_date_line=function( line_start_x, line_end_x, line_y, line_label )
 862 {
 863         this.m_diagram_htm+=this._div_htm( { "z-index": 3, "font-size": "1px", "border-top": "1px solid "+GitDiagram._g_color_trunk_line,
 864                 abs_x: line_start_x, abs_y: line_y, abs_width: line_end_x-line_start_x, height: 1,
 865                 clip: true
 866         } );
 867         if( line_label!=null ) {
 868                 var label_width=GitDiagram._g_absolute_label_letter_width*line_label.length*this.m_pixels_per_unit;
 869                 this.m_diagram_htm+=this._div_htm( { "z-index": 3, x: this._diagram_width()-label_width, y: this._to_pixels_y( line_y )+4,
 870                         color: GitDiagram._g_color_line_label, "font-family": GitDiagram._g_font, "font-size": GitDiagram._g_font_size,
 871                         text: line_label
 872                 } );
 873         }
 874 }
 875 GitDiagram.prototype._draw_node_div=function( node )
 876 {
 877         var node_color= node.parents.length==0 ? GitDiagram._g_color_root_node_background : GitDiagram._g_color_node_background;
 878         var border= node.parents.length==0 ? "1px solid "+GitDiagram._g_color_node_background : "none";
 879         var size=this.m_node_pixel_size;
 880         var div_x=this._to_pixels_x( GitDiagram._node_absolute_x( node ) )-size/2;
 881         var div_y=this._to_pixels_y( node.absolute_y )-size/2;
 882         var htm_arg={ id: this._make_id( "node", node.id ), "z-index": 4, "background-color": node_color, "font-size": "1px", border: border,
 883                 x: div_x, y: div_y, width: size, height: size,
 884                 clip: true // clip exactly
 885         };
 886         this.m_diagram_htm+=this._div_htm( htm_arg );
 887         if( node.coalesced_nodes!=null ) {
 888                 htm_arg.id=this._make_id( "noded", node.id );
 889                 htm_arg.x=div_x+3*this.m_node_pixel_size/8;
 890                 htm_arg.y=div_y+3*this.m_node_pixel_size/8;
 891                 this.m_diagram_htm+=this._div_htm( htm_arg );
 892         }
 893         // draw label, if present
 894         if( this.m_style=="by-date" && this.m_labels[node.id]!=null ) {
 895                 var label_color=GitDiagram._g_color_node_label;
 896                 this.m_diagram_htm+=this._div_htm( { id: this._make_id( "label", node.id ), "z-index": 4,
 897                         color: label_color, "border-left": "1px solid "+label_color,
 898                         "padding-bottom": 0, "padding-left": "2px", "padding-top": 0,
 899                         "font-family": GitDiagram._g_font, "font-size": GitDiagram._g_font_size, overflow: "visible", x: div_x, y: div_y,
 900                         clip_x: true
 901                 } );
 902         }
 903 }
 904 GitDiagram.prototype._node_elements_for_id=function( id )
 905 {
 906         var elements=[];
 907         var node=this.m_nodes[id];
 908         if( node.coalesced_to!=null ) {
 909                 node=node.coalesced_to;
 910         }
 911         var element=this.m_container_element.ownerDocument.getElementById( this._make_id( "node", node.id ) );
 912         if( element!=null ) {
 913                 elements.push( element );
 914         }
 915         if( node.coalesced_nodes!=null ) {
 916                 element=this.m_container_element.ownerDocument.getElementById( this._make_id( "noded", node.id ) );
 917                 if( element!=null ) {
 918                         elements.push( element );
 919                 }
 920         }
 921         return elements;
 922 }
 923 GitDiagram._clip_line=function( line, window )
 924 {
 925         // silly, but obvious
 926         var new_start_x;
 927         var new_end_x;
 928         var new_start_y;
 929         var new_end_y;
 930         var x_direction=1;
 931         if( line.start_x<=line.end_x ) {
 932                 new_start_x=Math.max( line.start_x, window.left );
 933                 new_end_x=Math.min( line.end_x, window.right );
 934         }else {
 935                 x_direction=-1;
 936                 new_start_x=Math.min( line.start_x, window.right );
 937                 new_end_x=Math.max( line.end_x, window.left );
 938         }
 939         var dy=line.end_y-line.start_y;
 940         var dx=line.end_x-line.start_x;
 941         if( dx!=0 ) {
 942                 line.start_y+=(new_start_x-line.start_x)*dy/dx;
 943                 line.end_y-=(line.end_x-new_end_x)*dy/dx;
 944         }
 945         var y_direction=1;
 946         if( line.start_y<=line.end_y ) {
 947                 new_start_y=Math.max( line.start_y, window.top );
 948                 new_end_y=Math.min( line.end_y, window.bottom );
 949         }else {
 950                 y_direction=-1;
 951                 new_start_y=Math.min( line.start_y, window.bottom );
 952                 new_end_y=Math.max( line.end_y, window.top );
 953         }
 954         if( dy!=0 ) {
 955                 new_start_x+=(new_start_y-line.start_y)*dx/dy;
 956                 new_end_x-=(line.end_y-new_end_y)*dx/dy;
 957         }
 958         line.start_x=new_start_x;
 959         line.start_y=new_start_y;
 960         line.end_x=new_end_x;
 961         line.end_y=new_end_y;
 962         return line.start_x*x_direction<=line.end_x*x_direction && line.start_y*y_direction<=line.end_y*y_direction;
 963 }
 964 GitDiagram.prototype._clip_and_draw_line=function( line_rect, window_pixels, color, line_width )
 965 {
 966         if( line_rect.abs_start_x!=null ) {
 967                 line_rect.start_x=this._to_pixels_x( line_rect.abs_start_x );
 968         }
 969         if( line_rect.abs_end_x!=null ) {
 970                 line_rect.end_x=this._to_pixels_x( line_rect.abs_end_x );
 971         }
 972         if( line_rect.abs_start_y!=null ) {
 973                 line_rect.start_y=this._to_pixels_y( line_rect.abs_start_y );
 974         }
 975         if( line_rect.abs_end_y!=null ) {
 976                 line_rect.end_y=this._to_pixels_y( line_rect.abs_end_y );
 977         }
 978         if( this.m_style=="by-commit" ) {
 979                 // undo x offset added in draw_by_commit, change x direction, and rotate
 980                 line_rect.start_x=-(line_rect.start_x-this.m_container_element.clientHeight);
 981                 line_rect.end_x=-(line_rect.end_x-this.m_container_element.clientHeight);
 982                 var t=line_rect.start_x;
 983                 line_rect.start_x=line_rect.start_y;
 984                 line_rect.start_y=t;
 985                 t=line_rect.end_x;
 986                 line_rect.end_x=line_rect.end_y;
 987                 line_rect.end_y=t;
 988         }
 989         if( GitDiagram._clip_line( line_rect, window_pixels ) ) {
 990                 if( this.m_jsg!=null ) {
 991                         this.m_jsg.setColor( color );
 992                         var old_stroke;
 993                         if( line_width!=null ) {
 994                                 old_stroke=this.m_jsg.stroke;
 995                                 this.m_jsg.setStroke( line_width );
 996                         }
 997                         this.m_jsg.drawLine( Math.floor( line_rect.start_x ), Math.floor( line_rect.start_y ), Math.floor( line_rect.end_x ), Math.floor( line_rect.end_y ) );
 998                         if( line_width!=null ) {
 999                                 this.m_jsg.setStroke( old_stroke );
1000                         }
1001                 }
1002         }
1003 }
1004 GitDiagram.prototype._draw_middle_arrow=function( rect, window_rect, color )
1005 {
1006         var arrow_base={ x: (rect.start_x+rect.end_x)/2, y: (rect.start_y+rect.end_y)/2 };
1007         if( arrow_base.x>=window_rect.left && arrow_base.x<=window_rect.right && arrow_base.y>=window_rect.top && arrow_base.y<=window_rect.bottom ) {
1008                 var dx=rect.end_x-rect.start_x;
1009                 var dy=rect.end_y-rect.start_y;
1010                 var d=Math.sqrt( dx*dx+dy*dy );
1011                 if( d!=0 ) {
1012                         var arrow_tip={ x: arrow_base.x+GitDiagram._g_arrow_length*dx/d, y: arrow_base.y+GitDiagram._g_arrow_length*dy/d };
1013                         var arrow_left={ x: arrow_base.x-GitDiagram._g_arrow_width*dy/(d*2), y: arrow_base.y+GitDiagram._g_arrow_width*dx/(d*2) };
1014                         var arrow_right={ x: arrow_base.x+GitDiagram._g_arrow_width*dy/(d*2), y: arrow_base.y-GitDiagram._g_arrow_width*dx/(d*2) };
1015                         if( this.m_jsg!=null ) {
1016                                 this.m_jsg.setColor( color );
1017                                 this.m_jsg.fillPolygon( [arrow_tip.x, arrow_left.x, arrow_right.x], [arrow_tip.y, arrow_left.y, arrow_right.y] );
1018                         }
1019                 }
1020         }
1021 }
1022 GitDiagram.prototype._draw_by_date=function( window_pixels )
1023 {
1024         // keep the first column, if present, for preserving window_offset when requested
1025         this.m_prev_first_column= this.m_date_columns.length>0 ? this.m_date_columns[0] : null;
1026         // prepare htm
1027         var window_absolute_left=this.m_window_offset.x/this.m_pixels_per_unit;
1028         var window_absolute_top=this.m_window_offset.y/this.m_pixels_per_unit;
1029         var window_absolute_right=window_absolute_left+this._diagram_width()/this.m_pixels_per_unit;
1030         var window_absolute_bottom=window_absolute_top+this._diagram_height()/this.m_pixels_per_unit;
1031         var node_absolute_size=this.m_node_pixel_size/this.m_pixels_per_unit;
1032         for( var node_id in this.m_nodes ) {
1033                 var node=this.m_nodes[node_id];
1034                 if( node.date!=null ) {
1035                         // first, if there is horizontal line starting at the node, draw it.
1036                         var line_start_x=null;
1037                         var line_end_x=null;
1038                         if( node.parents[0]==null || node.parents[0].author==null ) {
1039                                 line_start_x=GitDiagram._node_absolute_x( node );
1040                                 line_end_x=GitDiagram._node_absolute_x( node.line_rightmost_node );
1041                         }else if( node.offset_y!=null && node.offset_y!=0 ) {
1042                                 line_start_x=GitDiagram._node_absolute_x( node.parents[0] )+GitDiagram._g_branch_angle*Math.abs( node.offset_y );
1043                                 line_end_x=GitDiagram._node_absolute_x( node.line_rightmost_node );
1044                         }
1045                         if( line_start_x!=null && line_end_x!=null ) {
1046                                 // clip it
1047                                 line_start_x=Math.max( line_start_x, window_absolute_left );
1048                                 line_end_x=Math.min( line_end_x, window_absolute_right );
1049                                 var line_start_y=Math.max( node.absolute_y, window_absolute_top );
1050                                 var line_end_y=Math.min( node.absolute_y, window_absolute_bottom );
1051                                 if( line_start_x<=line_end_x && line_start_y<=line_end_y ) {
1052                                         var label_text=null;
1053                                         var label_id=node.line_rightmost_node.id;
1054                                         if( this.m_labels[label_id]!=null && line_end_x<GitDiagram._node_absolute_x( node.line_rightmost_node ) ) {
1055                                                 label_text=this._label_text( this.m_labels[label_id] )+"&#160;>";
1056                                         }
1057                                         this._draw_by_date_line( line_start_x, line_end_x, node.absolute_y, label_text );
1058                                 }
1059                         }
1060                         // second, draw the node bullet
1061                         // roughly assume largest size for every node, exact clipping is done later in _draw_node_div
1062                         var node_start_x=GitDiagram._node_absolute_x( node )-node_absolute_size;
1063                         var node_end_x=node_start_x+2*node_absolute_size;
1064                         var node_start_y=node.absolute_y-node_absolute_size;
1065                         var node_end_y=node_start_y+2*node_absolute_size;
1066                         // clip roughly
1067                         node_start_x=Math.max( node_start_x, window_absolute_left );
1068                         node_end_x=Math.min( node_end_x, window_absolute_right );
1069                         node_start_y=Math.max( node_start_y, window_absolute_top );
1070                         node_end_y=Math.min( node_end_y, window_absolute_bottom );
1071                         if( node_start_x<=node_end_x && node_start_y<=node_end_y ) {
1072                                 if( node.coalesced_to==null ) {
1073                                         this._draw_node_div( node ); // clip exactly inside _draw_node_div
1074                                 }
1075                         }
1076                         // then draw branch and merge lines
1077                         var branch_end_node=null;
1078                         var child_i;
1079                         for( child_i=0; child_i<node.children.length; ++child_i ) {
1080                                 var child=node.children[child_i];
1081                                 if( node==child.parents[0] ) { // it's a branch or a trunk
1082                                         if( child.offset_y!=null && child.offset_y!=0 ) {
1083                                                 if( branch_end_node==null || Math.abs( child.offset_y )>Math.abs( branch_end_node.offset_y ) ) {
1084                                                         // it's a branch
1085                                                         branch_end_node=child;
1086                                                 }
1087                                         }
1088                                 }else { // it's a merge
1089                                         var merge_rect={ abs_start_x: GitDiagram._node_absolute_x( node ), abs_start_y: node.absolute_y,
1090                                                                 abs_end_x: GitDiagram._node_absolute_x( child ), abs_end_y: child.absolute_y
1091                                         };
1092                                         this._clip_and_draw_line( merge_rect, window_pixels, GitDiagram._g_color_merge_line );
1093                                         this._draw_middle_arrow( merge_rect, window_pixels, GitDiagram._g_color_merge_arrow );
1094                                 }
1095                         }
1096                         // draw branch line
1097                         if( branch_end_node!=null ) {
1098                                 var branch_rect={ abs_start_x: GitDiagram._node_absolute_x( node ),
1099                                                         abs_end_x: GitDiagram._node_absolute_x( node )+GitDiagram._g_branch_angle*Math.abs( branch_end_node.offset_y ),
1100                                                         abs_start_y: node.absolute_y,
1101                                                         abs_end_y: branch_end_node.absolute_y
1102                                 };
1103                                 this._clip_and_draw_line( branch_rect, window_pixels, GitDiagram._g_color_branch_line );
1104                         }
1105                 }
1106         }
1107         this._draw_date_column_divs();
1108         this._draw_finish( { width: this._diagram_width(), height: this._diagram_height(),
1109                         x: this.m_container_origin.x, y: this.m_container_origin.y+this.m_container_element.clientHeight-this._diagram_height() } );
1110 }
1111 GitDiagram.prototype._draw_by_commit=function( window_pixels, row_height, scroll_top )
1112 {
1113         this.m_pixels_per_unit=row_height;
1114         // for clipping in draw_date_column_divs to work, _to_pixels_x should return values
1115         // in the range 0..container_size for visible columns, that is -real_pixels+container_size.
1116         // conversion to real_pixels and rotation is done in div_htm().
1117         var last_column=this.m_date_columns[this.m_date_columns.length-1];
1118         this.m_window_offset={ x: (last_column.absolute_x+last_column.width)*this.m_pixels_per_unit-scroll_top-this.m_container_element.clientHeight, y: 0 };
1119         this._draw_date_column_divs( window_pixels );
1120         this._draw_finish( {} );
1121 }
1122 GitDiagram.prototype._draw_finish=function( arg )
1123 {
1124         if( this.m_jsg!=null ) {
1125                 var diagram_div_htm=this._div_htm( { width: arg.width, height: arg.height, x: arg.x, y: arg.y,
1126                         text: this.m_background_htm+this.m_diagram_htm+"<div>"+this.m_jsg.htm+"</div>" // extra div to contain all jsg graphics, to be easily removed to speed up dragging (see on_drag_mouse_move)
1127                 } );
1128                 this.m_jsg.htm=diagram_div_htm;
1129                 this.m_jsg.paint();
1130         }
1131         if( this.m_style!="by-commit" ) {
1132                 var diagram_div=this.m_container_element.firstChild;
1133                 // post-draw DOM manipulations
1134                 for( var cn=diagram_div.firstChild; cn!=null; cn=cn.nextSibling ) {
1135                         if( cn.id!=null ) {
1136                                 // add text for labels, bottom-align labels with node bullets
1137                                 var idtag=this._match_id( cn.id );
1138                                 if( idtag!=null ) {
1139                                         if( idtag.tag=="label" ) {
1140                                                 var label=this.m_labels[idtag.id];
1141                                                 if( label!=null ) {
1142                                                         cn.appendChild( cn.ownerDocument.createTextNode( this._label_text( label ) ) );
1143                                                 }
1144                                                 cn.style.top=(parseInt( cn.style.top )-cn.clientHeight+1)+"px";
1145                                                 if( this.m_style=="by-commit" ) {
1146                                                         cn.style.top=(parseInt( cn.style.top )-this.m_node_pixel_size+1)+"px";
1147                                                 }
1148                                         }
1149                                         // add popups for node bullets
1150                                         if( idtag.tag=="node" || idtag.tag=="noded" ) {
1151                                                 var node=this.m_nodes[idtag.id];
1152                                                 if( node!=null ) {
1153                                                         this.m_ui_handler( this.m_ui_handler_arg, "node_init", this, node, cn );
1154                                                 }
1155                                         }
1156                                 }
1157                         }
1158                 }
1159         }
1160 }
1161 GitDiagram.prototype.draw=function( row_height, scroll_top )
1162 {
1163         this.m_ui_handler( this.m_ui_handler_arg, "draw", this, "begin" );
1164         if( this.m_date_columns.length>0 ) {
1165                 this._reset_drawing_divs();
1166                 this._find_container_origin();
1167                 var window_pixels={ left: 0, top: 0, right: this._diagram_width(), bottom: this._diagram_height() };
1168                 if( this.m_style=="by-date" ) {
1169                         this._draw_by_date( window_pixels );
1170                 }else {
1171                         this._draw_by_commit( window_pixels, row_height, scroll_top );
1172                 }
1173         }
1174         this.m_ui_handler( this.m_ui_handler_arg, "draw", this, "end" );
1175 }
1176
1177 // dragging
1178 GitDiagram.prototype.begin_move=function()
1179 {
1180         // remove all jsg graphics to speed up dragging
1181         var jsg_div=this.m_container_element.firstChild.lastChild;
1182         jsg_div.innerHTML="";
1183 }
1184 GitDiagram.prototype.track_move=function( offset )
1185 {
1186         var container=this.m_container_element;
1187         var canvas=container.firstChild;
1188         if( container!=null && canvas!=null ) {
1189                 var original_pos=Motion.get_page_coords( container, true );
1190                 original_pos.y+=GitDiagram._g_month_height_pixels+GitDiagram._g_day_height_pixels;
1191                 Motion.set_page_coords( canvas, original_pos.x+offset.x, original_pos.y+offset.y, true );
1192         }
1193 }
1194 GitDiagram.prototype.end_move=function( offset )
1195 {
1196         var diagram=this;
1197         diagram.m_window_offset.x-=offset.x;
1198         diagram.m_window_offset.y-=offset.y;
1199         // without timeout, the mouse sometimes is left locked in selection mode
1200         setTimeout( function() { diagram.draw(); }, 0.1 );
1201 }
1202
1203 // placement functions
1204 GitDiagram.prototype._assign_offset_x=function( node, parent_node )
1205 {
1206         if( this.m_style=="by-commit" ) {
1207                 node.offset_x=GitDiagram._g_step_x[this.m_style]/2;
1208                 return;
1209         }
1210         if( node.date!=parent_node.date ) {
1211                 node.offset_x=GitDiagram._g_step_x[this.m_style]/2; // it's at the start of the new column
1212         }else {
1213                 if( node.offset_y==null || node.offset_y==0 ) { // node is on the trunk or branch line
1214                         node.offset_x=parent_node.offset_x;
1215                         if( this.m_labels[node.id]!=null || node.parents.length>1 || parent_node.parents.length>1
1216                            || node.children.length>1 || parent_node.children.length>1
1217                            || (node.children.length==1 && node.children[0].parents[0]!=node) ) {
1218                                 node.offset_x+=GitDiagram._g_step_x[this.m_style]; // separate
1219                         }else {
1220                                 // find the first parent in the same place, record this node in its coalesced_nodes
1221                                 var first_parent;
1222                                 while( parent_node!=null && parent_node.date==node.date && parent_node.absolute_y==node.absolute_y && parent_node.offset_x==node.offset_x
1223                                         && parent_node.line_rightmost_node==null && parent_node.children.length==1 && this.m_labels[parent_node.id]==null ) {
1224                                         first_parent=parent_node;
1225                                         parent_node=parent_node.parents[0];
1226                                 }
1227                                 if( first_parent==null ) {
1228                                         node.offset_x+=GitDiagram._g_step_x[this.m_style]; // separate
1229                                 }else {
1230                                         if( first_parent.coalesced_nodes==null ) {
1231                                                 first_parent.coalesced_nodes=[first_parent];
1232                                         }
1233                                         first_parent.coalesced_nodes.push( node );
1234                                         node.coalesced_to=first_parent;
1235                                 }
1236                         }
1237                 }else { // node is the first on a branch
1238                         node.offset_x=parent_node.offset_x+GitDiagram._g_branch_angle*Math.abs( node.offset_y );
1239                         if( node.children.length>1 ) {
1240                                 node.offset_x+=GitDiagram._g_step_x[this.m_style]; // move to the right, to separate branches sprawling from the node from ones from the parent
1241                         }
1242                 }
1243         }
1244         // make sure that labels do not overlap
1245         if( this.m_labels[node.id]!=null ) {
1246                 var this_label=this.m_labels[node.id];
1247                 // in theory, this will not work, since here not all date_colimn widths are calculated yet.
1248                 var this_label_x=0;
1249                 for( var date_column_i=0; date_column_i<this.m_date_columns.length; ++date_column_i ) {
1250                         if( this.m_date_columns[date_column_i].date==node.date ) {
1251                                 break;
1252                         }
1253                         this_label_x+=this.m_date_columns[date_column_i].width;
1254                 }
1255                 var node_absolute_size=this.m_node_pixel_size/this.m_pixels_per_unit;
1256                 this_label_x+=node.offset_x-node_absolute_size/2;
1257                 var this_label_y=node.absolute_y-node_absolute_size/2-GitDiagram._g_absolute_label_height;
1258                 for( var label_id in this.m_labels ) {
1259                         var label=this.m_labels[label_id];
1260                         if( label.absolute_pos!=null && Math.abs( label.absolute_pos.y-this_label_y )<=GitDiagram._g_absolute_label_height ) {
1261                                 var label_width=GitDiagram._g_absolute_label_letter_width*this._label_text( label ).length;
1262                                 var this_label_width=GitDiagram._g_absolute_label_letter_width*this._label_text( this_label ).length;
1263                                 var max_left=Math.max( label.absolute_pos.x, this_label_x );
1264                                 var min_right=Math.min( label.absolute_pos.x+label_width, this_label_x+this_label_width );
1265                                 if( max_left<=min_right ) {
1266                                         var this_label_offset=label.absolute_pos.x+label_width-this_label_x;
1267                                         this_label_x+=this_label_offset;
1268                                         node.offset_x+=this_label_offset;
1269                                 }
1270                         }
1271                 }
1272                 this_label.absolute_pos={ x: this_label_x, y: this_label_y };
1273         }
1274 }
1275 GitDiagram.prototype._get_new_line_color=function()
1276 {
1277         var new_color=GitDiagram._g_line_colors[this.m_line_color_index];
1278         ++this.m_line_color_index;
1279         if( this.m_line_color_index>=GitDiagram._g_line_colors.length ) {
1280                 this.m_line_color_index=0;
1281         }
1282         return new_color;
1283 }
1284 GitDiagram.prototype._place_by_commit_finish=function()
1285 {
1286         // propagate leftmost_node, assign line colors
1287         for( var column_i=0; column_i<this.m_date_columns.length; ++column_i ) {
1288                 var node=this.m_date_columns[column_i].node;
1289                 if( node.line_rightmost_node!=null ) { // _propagate_absolute_y_offset_x should have put this node into column.lines.
1290                         // propagate it to its primary children (assuming that they all belong to the columns with greater column_i)
1291                         node.line_leftmost_node=node;
1292                         var rightmost_node=node.line_rightmost_node; // node to assign line_color to
1293                         var parent_color;
1294                         if( node.parents[0]!=null && node.parents[0].line_leftmost_node!=null
1295                           && node.parents[0].line_leftmost_node.line_rightmost_node!=null
1296                           && node.parents[0].line_leftmost_node.line_rightmost_node.line_color!=null ) {
1297                                 // line_color is assigned only to the righmost node on each line
1298                                 parent_color=node.parents[0].line_leftmost_node.line_rightmost_node.line_color;
1299                         }
1300                         // if the branch had only one commit and lived shorter than one day, color it the same as its parent
1301                         var date_distance=node.line_rightmost_node.date-node.line_leftmost_node.date;
1302                         if( parent_color!=null && date_distance<1000*60*60*24 && rightmost_node.parents[0]==node.parents[0] ) {
1303                                 rightmost_node.line_color=parent_color;
1304                         }else {
1305                                 var new_color;
1306                                 if( this.m_assigned_colors[rightmost_node.id]!=null ) {
1307                                         new_color=this.m_assigned_colors[rightmost_node.id];
1308                                         if( parent_color!=null && new_color==parent_color ) {
1309                                                 new_color=this._get_new_line_color();
1310                                         }
1311                                 }else {
1312                                         new_color=this._get_new_line_color();
1313                                 }
1314                                 // make sure it's different from parent color
1315                                 if( parent_color!=null && new_color==parent_color ) {
1316                                         new_color=this._get_new_line_color();
1317                                 }
1318                                 rightmost_node.line_color=new_color;
1319                                 this.m_assigned_colors[rightmost_node.id]=new_color;
1320                         }
1321                 }else {
1322                         var parent=node.parents[0];
1323                         if( GitBrowser!=null && GitBrowser.error_show!=null ) { // XXX really, this code should not know a thing about GitBrowser
1324                                 if( parent==null ) {
1325                                         GitBrowser.error_show( "primary parent is null for non-leftmost node on the line" );
1326                                         return;
1327                                 }else if( parent.line_leftmost_node==null ) {
1328                                         GitBrowser.error_show( "GitDiagram._place_by_commit_finish bug: line_leftmost_node is unassigned for parent of "+node.id );
1329                                         return;
1330                                 }
1331                         }
1332                         node.line_leftmost_node=parent.line_leftmost_node;
1333                 }
1334         }
1335         // place merge lines
1336         var merge_lines={}; // start node id => { end node id => true } (multimap-like)
1337         for( var column_i=this.m_date_columns.length; column_i>0; --column_i ) {
1338                 var column=this.m_date_columns[column_i-1];
1339                 var node=column.node;
1340                 delete merge_lines[node.id]; // all straight merge lines with start_id==node.id will end at the previous column
1341                 for( var start_id in merge_lines ) {
1342                         for( var end_id in merge_lines[start_id] ) {
1343                                 column.lines.push( { kind: "merge", start_node: this.m_nodes[start_id], end_node: this.m_nodes[end_id] } );
1344                         }
1345                 }
1346                 for( var parent_i=1; parent_i<node.parents.length; ++parent_i ) {
1347                         var start_node=node.parents[parent_i];
1348                         if( start_node.date!=null ) {
1349                                 if( column_i>1 && this.m_date_columns[column_i-2].node.id==start_node.id ) {
1350                                         column.short_merge=true;
1351                                 }else {
1352                                         if( merge_lines[start_node.id]==null ) {
1353                                                 merge_lines[start_node.id]={};
1354                                         }
1355                                         merge_lines[start_node.id][node.id]=true;
1356                                 }
1357                         }
1358                 }
1359                 column.lines.sort( function( line1, line2 ) {
1360                         var r=line1.start_node.absolute_y-line2.start_node.absolute_y;
1361                         if( r==0 ) {
1362                                 r=line1.end_node.absolute_y-line2.end_node.absolute_y;
1363                         }
1364                         if( r==0 ) {
1365                                 r=line1.end_node.date-line2.end_node.date;
1366                         }
1367                         if( r==0 ) {
1368                                 r=line1.start_node.date-line2.start_node.date;
1369                         }
1370                         return r;
1371                 } );
1372         }
1373         // assign new absolute_y, shifted towards 0 as close as other lines allow
1374         for( var column_i=0; column_i<this.m_date_columns.length; ++column_i ) {
1375                 var column=this.m_date_columns[column_i];
1376                 if( column.node.line_leftmost_node!=null ) {
1377                         // find it and assign new absolute y according to the line position
1378                         for( var line_i=0; line_i<column.lines.length; ++line_i ) {
1379                                 var line=column.lines[line_i];
1380                                 if( line.kind=="trunk" && line.start_node.id==column.node.line_leftmost_node.id ) {
1381                                         column.node.absolute_y=GitDiagram._line_absolute_y( line_i );
1382                                         break;
1383                                 }
1384                         }
1385                 }
1386         }
1387 }
1388 GitDiagram.prototype._propagate_absolute_y_offset_x=function( node )
1389 {
1390         // if there is a line starting from this node, populate lines array for each date_column that line goes through
1391         if( node.line_rightmost_node!=null ) {
1392                 // the line will start one column before node parent, if it has any
1393                 var line_start_date=node.date;
1394                 if( node.parents[0]!=null && node.parents[0].date!=null ) {
1395                         line_start_date=node.parents[0].date+1;
1396                 }
1397                 for( var i=0; i<this.m_date_columns.length; ++i ) {
1398                         if( this.m_date_columns[i].date>=line_start_date && this.m_date_columns[i].date<=node.line_rightmost_node.date ) {
1399                                 this.m_date_columns[i].lines.push( { kind: "trunk", start_node: node, end_node: node.line_rightmost_node } );
1400                         }
1401                 }
1402         }
1403         var node_children=GitDiagram._get_node_primary_children( node );
1404         while( node_children.length==1 ) { // cut recursion down a bit - both IE and firefox can't handle it as is. (Opera 8 can).
1405                 var child_node=node_children[0];
1406                 child_node.absolute_y=node.absolute_y+child_node.offset_y;
1407                 this._assign_offset_x( child_node, node );
1408                 // node_children.length==1 <=> no branches
1409                 var required_width=node.offset_x+GitDiagram._g_step_x[this.m_style]/2;
1410                 if( required_width>node.date_column.width ) {
1411                         node.date_column.width=required_width;
1412                 }
1413                 node=child_node;
1414                 node_children=GitDiagram._get_node_primary_children( node );
1415         }
1416         var max_branch_span=0;
1417         for( var child_i=0; child_i<node_children.length; ++child_i ) {
1418                 var child_node=node_children[child_i];
1419                 child_node.absolute_y=node.absolute_y+child_node.offset_y;
1420                 this._assign_offset_x( child_node, node );
1421                 this._propagate_absolute_y_offset_x( child_node );
1422                 if( this.m_style=="by-date" ) {
1423                         max_branch_span=Math.max( max_branch_span, Math.abs( child_node.offset_y*GitDiagram._g_branch_angle ) );
1424                 }
1425         }
1426         var required_width=node.offset_x+Math.max( max_branch_span, GitDiagram._g_step_x[this.m_style]/2 );
1427         if( required_width>node.date_column.width ) {
1428                 node.date_column.width=required_width;
1429         }
1430 }
1431 GitDiagram.prototype._assign_tentative_offset_x=function( start_node, rightmost_node )
1432 // assign vaguely resembling reality offset_x for use in better branch placement on y axis
1433 // (real offset_x is determined after that placement is complete)
1434 {
1435         var current_node=rightmost_node;
1436         var path=[];
1437         while( current_node!=start_node ) {
1438                 path.push( current_node );
1439                 current_node=current_node.parents[0];
1440         }
1441         path.push( start_node );
1442         var parent_node=null;
1443         for( var path_i=path.length-1; path_i>=0; --path_i ) {
1444                 var node=path[path_i];
1445                 if( parent_node==null || parent_node.date!=node.date ) {
1446                         node.offset_x=GitDiagram._g_step_x[this.m_style]/2;
1447                 }else {
1448                         node.offset_x=parent_node.offset_x;
1449                         if( this.m_labels[node.id]!=null || node.parents.length>1 || parent_node.parents.length>1
1450                            || node.children.length>1 || parent_node.children.length>1
1451                            || (node.children.length==1 && node.children[0].parents[0]!=node) ) {
1452                                 node.offset_x+=GitDiagram._g_step_x[this.m_style]; // separate
1453                         }else {
1454                                 // find the first parent in the same place, record this node in its coalesced_nodes
1455                                 var first_parent;
1456                                 while( parent_node!=start_node && parent_node.date==node.date && parent_node.offset_x==node.offset_x
1457                                           && parent_node.children.length==1 && this.m_labels[parent_node.id]==null ) {
1458                                         first_parent=parent_node;
1459                                         parent_node=parent_node.parents[0];
1460                                 }
1461                                 if( first_parent==null ) {
1462                                         node.offset_x+=GitDiagram._g_step_x[this.m_style]; // separate
1463                                 }
1464                         }
1465                 }
1466                 parent_node=node;
1467         }
1468 }
1469 GitDiagram.prototype._place_node_subtree=function( root_node, leftmost_x )
1470 {
1471         // horizontal coordinates are dates, increasing to the right.
1472         // vertical coordinates are integers, relative to the node, increasing downards, with 1 = conventional distance between two adjacent parallel lines.
1473
1474         // determine structure and shape of a subtree originating from the root_node,
1475
1476         // The algorithm works like this:
1477
1478         // determine the rightmost node on the trunk (the trunk will be on the straight line).
1479
1480         // for each node on the trunk, starting from the rightmost, place other (non-trunk) branches originating from that node protruding in the same direction,
1481         // alternating that direction (up or down) for each node that has branches.
1482
1483                 // order child nodes somehow, the nearest to the trunk being the first.
1484                 // call place_node_subtree for each child node,
1485                 // shift the subtree to the current direction so as not to intersect with already placed shape
1486                 // the algorithm is guaranteed to work so that subtree can be shifted as far as required in the given direction,
1487                 // in other words, only the clearance given by the limiting shape from the opposite direction should be observed.
1488
1489                 // "shapes" object consists of two arrays, "upper shape" at index -1 and "lower shape" at index 1
1490                 // each array is a sequence of pairs: { x: { date: date, offset: offset within date column } , y: offset from the trunk }
1491
1492         // So...
1493         root_node.line_rightmost_node=this._find_trunk_rightmost_node( root_node );
1494         this._assign_tentative_offset_x( root_node, root_node.line_rightmost_node );
1495         var current_node=root_node.line_rightmost_node;
1496         var current_shapes={};
1497         current_shapes[-1]=[ {x: leftmost_x, y: 0}, {x: { date: current_node.date, offset: current_node.offset_x }, y: 0 } ]; // each shape starts as mere line
1498         current_shapes[1]=[ {x: leftmost_x, y: 0}, {x: { date: current_node.date, offset: current_node.offset_x }, y: 0 } ];
1499         while( current_node.id!=root_node.id ) { // walk left from the rightmost node
1500                 current_node.offset_y=0;
1501                 var parent_node=current_node.parents[0];
1502                 var branch_nodes=GitDiagram._get_node_primary_children( parent_node, current_node );
1503                 if( branch_nodes.length>0 ) {
1504                         var new_shapes={};
1505                         var branch_offsets={};
1506                         // try placing branches in both directions
1507                         for( var i=0; i<2; ++i ) {
1508                                 var direction=1-2*i;
1509                                 new_shapes[direction]=current_shapes[direction];
1510                                 branch_offsets[direction]=[];
1511                                 // for now, do not order branch_nodes in any way
1512                                 for( var branch_i=0; branch_i<branch_nodes.length; ++branch_i ) {
1513                                         var branch_node=branch_nodes[branch_i];
1514                                         var branch_shapes=this._place_node_subtree( branch_node, { date: parent_node.date, offset: parent_node.offset_x } );
1515                                         var branch_offset=GitDiagram._determine_branch_offset( branch_i, direction, branch_shapes[-1*direction], new_shapes[direction] );
1516                                         new_shapes[direction]=GitDiagram._expand_shape( branch_offset, branch_shapes[direction], new_shapes[direction] );
1517                                         branch_offsets[direction].push( branch_offset );
1518                                 }
1519                                 if( this.m_style=="by-commit" ) { // for by-commit, grow always down
1520                                         break;
1521                                 }
1522                         }
1523                         // pick one direction which gives narrower subtree
1524                         var best_direction=1;
1525                         if( this.m_style!="by-commit" ) {
1526                                 if( Math.abs( branch_offsets[-1*best_direction][branch_nodes.length-1] )<=Math.abs( branch_offsets[best_direction][branch_nodes.length-1] ) ) {
1527                                         best_direction=-1*best_direction;
1528                                 }
1529                         }
1530                         current_shapes[best_direction]=new_shapes[best_direction];
1531                         for( var branch_i=0; branch_i<branch_nodes.length; ++branch_i ) {
1532                                 branch_nodes[branch_i].offset_y=branch_offsets[best_direction][branch_i];
1533                         }
1534                 }
1535                 current_node=parent_node;
1536         }
1537         return current_shapes;
1538 }
1539 // Determine the trunk, and the rightmost node on it.
1540 // Gather all leaf nodes. If there is one labeled 'master', thats it. Otherwise, pick the leaf with the with the latest date among labeled ones. Otherwise (all leafs are unlabeled), just pick one with the latest date.
1541 GitDiagram.prototype._find_trunk_rightmost_node=function( node )
1542 {
1543         var subtree_nodes=[node];
1544         var master_leaf=null;
1545         var latest_labeled_leaf=null;
1546         var latest_leaf=null;
1547         while( subtree_nodes.length>0 ) {
1548                 var current_node=subtree_nodes[0];
1549                 if( current_node.date==null ) { // there is a gap. pretend we weren't there
1550                         return node;
1551                 }
1552                 subtree_nodes.splice( 0, 1 );
1553                 var primary_children=GitDiagram._get_node_primary_children( current_node );
1554                 if( primary_children.length==0 ) { // it's a leaf
1555                         if( this.m_labels[current_node.id]!=null ) {
1556                                 if( this._is_label_master( this.m_labels[current_node.id] ) ) {
1557                                         master_leaf=current_node;
1558                                 }else {
1559                                         if( latest_labeled_leaf==null || current_node.date>latest_labeled_leaf.date ) {
1560                                                 latest_labeled_leaf=current_node;
1561                                         }
1562                                 }
1563                         }else {
1564                                 if( latest_leaf==null || current_node.date>latest_leaf.date ) {
1565                                         latest_leaf=current_node;
1566                                 }
1567                         }
1568                 }else {
1569                         for( var child_i=0; child_i<primary_children.length; ++child_i ) {
1570                                 subtree_nodes.push( primary_children[child_i] );
1571                         }
1572                 }
1573         }
1574         return master_leaf!=null ? master_leaf : latest_labeled_leaf!=null ? latest_labeled_leaf : latest_leaf;
1575 }
1576 GitDiagram._determine_branch_offset=function( tentative_abs_offset, direction, branch_shape, trunk_shape )
1577 {
1578         // return modified tentative_offset so that branch_shape placed at that offset does not intersect with trunk_shape
1579         // direction is required for determining the sign, since tentative_abs_offset may be 0
1580         var tentative_offset=tentative_abs_offset*direction;
1581         var branch_i=0;
1582         var branch_y=direction*(tentative_offset+branch_shape[0].y);
1583         var trunk_i=0;
1584         var trunk_y=direction*trunk_shape[0].y;
1585         if( GitDiagram._shape_x_less( branch_shape[0].x, trunk_shape[0].x ) ) {
1586                 while( branch_i<branch_shape.length && GitDiagram._shape_x_less( branch_shape[branch_i].x, trunk_shape[0].x ) ) {
1587                         branch_y=direction*(tentative_offset+branch_shape[branch_i].y);
1588                         ++branch_i;
1589                 }
1590         }else if( GitDiagram._shape_x_less( trunk_shape[0].x, branch_shape[0].x ) ) {
1591                 while( trunk_i<trunk_shape.length && GitDiagram._shape_x_less( trunk_shape[trunk_i].x, branch_shape[0].x ) ) {
1592                         trunk_y=direction*trunk_shape[trunk_i].y;
1593                         ++trunk_i;
1594                 }
1595         }
1596         // when direction ==1 (down), branch_y>trunk_y is ok, branch_y<=trunk_y is bad.
1597         // when direction == -1 (up), branch_y<trunk_y is ok, branch_y>=trunk_y is bad.
1598         // when multiplied by the direction, both cases can be treated in the same way.
1599         var clearance=0;
1600         while( branch_i<branch_shape.length && trunk_i<trunk_shape.length ) {
1601                 if( branch_y<=trunk_y ) {
1602                         clearance=Math.max( clearance, trunk_y-branch_y );
1603                 }
1604                 var branch_x=branch_shape[branch_i].x
1605                 var trunk_x=trunk_shape[trunk_i].x;
1606                 if( GitDiagram._shape_x_less( branch_x, trunk_x ) ) {
1607                         branch_y=direction*(tentative_offset+branch_shape[branch_i].y);
1608                         ++branch_i;
1609                 }else if( GitDiagram._shape_x_less( trunk_x, branch_x ) ) {
1610                         trunk_y=direction*trunk_shape[trunk_i].y;
1611                         ++trunk_i;
1612                 }else { // handle simultaneous variations over single point
1613                         var max_trunk_y=trunk_y; // max for trunk, min for branch - increase badness
1614                         while( trunk_i<trunk_shape.length && GitDiagram._shape_x_eq( trunk_shape[trunk_i].x, trunk_x ) ) {
1615                                 trunk_y=direction*trunk_shape[trunk_i].y;
1616                                 max_trunk_y=Math.max( max_trunk_y, trunk_y );
1617                                 ++trunk_i;
1618                         }
1619                         var min_branch_y=branch_y;
1620                         while( branch_i<branch_shape.length && GitDiagram._shape_x_eq( branch_shape[branch_i].x, branch_x ) ) {
1621                                 branch_y=direction*(tentative_offset+branch_shape[branch_i].y);
1622                                 min_branch_y=Math.min( min_branch_y, branch_y );
1623                                 ++branch_i;
1624                         }
1625                         if( min_branch_y<=max_trunk_y ) {
1626                                 clearance=Math.max( clearance, max_trunk_y-min_branch_y );
1627                         }
1628                 }
1629         }
1630         ++clearance;
1631         return (tentative_abs_offset+clearance)*direction;
1632 }
1633 GitDiagram._expand_shape=function( branch_offset, branch_shape, trunk_shape )
1634 {
1635         // returns trunk_shape expanded with branch_shape placed at branch_offset
1636         // it's assumed that branch_offset always has the same sign as y coords in branch_shape.
1637         var result=[];
1638         var branch_y=null;
1639         var trunk_y=null;
1640         var branch_i=0;
1641         var trunk_i=0;
1642         var prev_result_y=null;
1643         while( branch_i<branch_shape.length || trunk_i<trunk_shape.length ) {
1644                 var result_x;
1645                 var result_y;
1646                 var max_result_y;
1647                 if( trunk_i==trunk_shape.length ) {
1648                         result_x=branch_shape[branch_i].x;
1649                         result_y=branch_offset+branch_shape[branch_i].y;
1650                         max_result_y=result_y;
1651                         ++branch_i;
1652                 }else if( branch_i==branch_shape.length ) {
1653                         result_x=trunk_shape[trunk_i].x;
1654                         result_y=trunk_shape[trunk_i].y;
1655                         max_result_y=result_y;
1656                         ++trunk_i;
1657                 }else {
1658                         var branch_x=branch_shape[branch_i].x;
1659                         var trunk_x=trunk_shape[trunk_i].x;
1660                         result_x=GitDiagram._shape_x_min( branch_x, trunk_x );
1661
1662                         var max_branch_y=null;
1663                         while( !GitDiagram._shape_x_less( trunk_x, branch_x ) && branch_i<branch_shape.length && GitDiagram._shape_x_eq( branch_x, branch_shape[branch_i].x ) ) {
1664                                 if( max_branch_y==null || Math.abs( branch_offset+branch_shape[branch_i].y )>Math.abs( max_branch_y ) ) {
1665                                         max_branch_y=branch_offset+branch_shape[branch_i].y;
1666                                 }
1667                                 branch_y=branch_offset+branch_shape[branch_i].y;
1668                                 ++branch_i;
1669                         }
1670                         if( max_branch_y==null ) { // if the value has not changed - take previous one
1671                                 max_branch_y=branch_y;
1672                         }
1673
1674                         var max_trunk_y=null;
1675                         while( !GitDiagram._shape_x_less( branch_x, trunk_x ) && trunk_i<trunk_shape.length && GitDiagram._shape_x_eq( trunk_x, trunk_shape[trunk_i].x ) ) {
1676                                 if( max_trunk_y==null || Math.abs( trunk_shape[trunk_i].y )>Math.abs( max_trunk_y ) ) {
1677                                         max_trunk_y=trunk_shape[trunk_i].y;
1678                                 }
1679                                 trunk_y=trunk_shape[trunk_i].y;
1680                                 ++trunk_i;
1681                         }
1682                         if( max_trunk_y==null ) {
1683                                 max_trunk_y=trunk_y;
1684                         }
1685
1686                         if( max_branch_y==null ) {
1687                                 max_result_y=max_trunk_y;
1688                         }else if( max_trunk_y==null ) {
1689                                 max_result_y=max_branch_y;
1690                         }else if( Math.abs( max_branch_y )>Math.abs( max_trunk_y ) ) {
1691                                 max_result_y=max_branch_y;
1692                         }else {
1693                                 max_result_y=max_trunk_y;
1694                         }
1695
1696                         if( branch_y==null ) {
1697                                 result_y=trunk_y;
1698                         }else if( trunk_y==null ) {
1699                                 result_y=branch_y;
1700                         }else if( branch_i==branch_shape.length && trunk_i!=trunk_shape.length ) { // last point on the branch - the rest of result should repeat trunk
1701                                 result_y=trunk_y;
1702                         }else if( trunk_i==trunk_shape.length && branch_i!=branch_shape.length ) { // last point on the trunk - the rest of result should repeat branch
1703                                 result_y=branch_y;
1704                         }else {
1705                                 if( Math.abs( branch_y )>Math.abs( trunk_y ) ) {
1706                                         result_y=branch_y;
1707                                 }else {
1708                                         result_y=trunk_y;
1709                                 }
1710                         }
1711                 }
1712                 if( result_y!=prev_result_y || max_result_y!=prev_result_y
1713                     || (trunk_i==trunk_shape.length && branch_i==branch_shape.length) ) { // always add the last point
1714                         if( max_result_y!=result_y && max_result_y!=prev_result_y ) {
1715                                 result.push( { x: result_x, y: max_result_y } );
1716                         }
1717                         result.push( { x: result_x, y: result_y } );
1718                         prev_result_y=result_y;
1719                 }
1720         }
1721         return result;
1722 }
1723 GitDiagram._shape_x_less=function( x1, x2 )
1724 {
1725         return x1.date<x2.date ? true
1726                 : x2.date<x1.date ? false
1727                 : x1.offset<x2.offset
1728         ;
1729 }
1730 GitDiagram._shape_x_eq=function( x1, x2 )
1731 {
1732         return x1.date==x2.date && x1.offset==x2.offset;
1733 }
1734 GitDiagram._shape_x_min=function( x1, x2 )
1735 {
1736         return x1.date<x2.date ? x1
1737                 : x2.date<x1.date ? x2
1738                 : x1.offset<x2.offset ? x1
1739                 : x2
1740         ;
1741 }
1742 // might be useful for debugging
1743 GitDiagram._shape_point_to_string=function( p )
1744 {
1745         var x=p.x.date;
1746         if( x>10000 ) {
1747                 var dt=new Date( x );
1748                 var d=dt.getDate();
1749                 var m=dt.getMonth();
1750                 x=d+"."+(m+1);
1751         }
1752         x+="."+p.x.offset;
1753         return "{x: "+x+", y: "+p.y+"}";
1754 }
1755 GitDiagram._shape_to_string=function( shape )
1756 {
1757         var s="[";
1758         for( var shape_i=0; shape_i<shape.length; ++shape_i ) {
1759                 if( s.length>1 ) {
1760                         s+=",";
1761                 }
1762                 s+=GitDiagram._shape_point_to_string( shape[shape_i] );
1763         }
1764         s+="]";
1765         return s;
1766 }
1767
1768