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