Class: Gitgo::Repo::Graph

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/gitgo/repo/graph.rb

Overview

Graph performs the important and somewhat complicated task of deconvoluting document graphs. Graph and Node use signifant amounts of caching to make sure traversal of the document graph is as quick as possible. Graphs must be reset to detect any associations added after initialization.

See Gitgo::Repo for terminology used in this documentation.

Deconvolution

Deconvolution involves replacing each node in a DAG with the current versions of that node, and specifically reassigning parent and children links from updated nodes to their current versions.

a                              a
|                              |
b -> b1                        b1--+
|    |                         |   |
c    |             becomes     c   |
     |                             |
     d                             d

When multiple current versions exist for a node, a new fork in the graph is introduced:

a                              a
|                              |--+
b -> [b1, b2]                  b1 |
|                              |  |
c                 becomes      |  b2
                               |  |
                               c--+

These forks can happen anywhere (including the graph head), as can updates that merge multiple revisions:

a                              a
|                              |
b -> [b1, b2] -> b3            b3
|                              |
c                 becomes      c

Linkages for the convoluted graph is not directly available from Graph, although all nodes are (via nodes).

Notes

The possibility of multiple current versions is perhaps non-intuitive, but entirely possible if user A modifies a document while separately user B modifies the same document in a different way. When these changes are merged, you end up with multiple current versions.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(repo, head) ⇒ Graph

Creates a new Graph



70
71
72
73
74
 
# File 'lib/gitgo/repo/graph.rb', line 70

def initialize(repo, head)
  @repo = repo
  @head = head
  reset
end

Instance Attribute Details

#head ⇒ Object (readonly)

The graph head



64
65
66
 
# File 'lib/gitgo/repo/graph.rb', line 64

def head
  @head
end

#nodes ⇒ Object (readonly)

A hash of (sha, node) pairs identifying all accessible nodes



67
68
69
 
# File 'lib/gitgo/repo/graph.rb', line 67

def nodes
  @nodes
end

#repo ⇒ Object (readonly)

A back-reference to the repo where the documents are stored



61
62
63
 
# File 'lib/gitgo/repo/graph.rb', line 61

def repo
  @repo
end

Instance Method Details

#[](sha) ⇒ Object

Same as node.



83
84
85
 
# File 'lib/gitgo/repo/graph.rb', line 83

def [](sha)
  nodes[sha]
end

#draw(indent = 0) ⇒ Object

Draws the graph



192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
 
# File 'lib/gitgo/repo/graph.rb', line 192

def draw(indent=0)
  lines = []
  each do |(sha, slot, index, current_slots, transitions)|
    next if sha.nil?
    
    line = []
    transition = []
    
    transitions.each do |target|
      tstart = (slot * 2) + indent
      tend = (target * 2) + indent
      
      if tstart > tend
        tstart, tend = tend, tstart
      end
      
      tstart.upto(tend) {|i| transition[i] = '-'}
      transition[tstart] = '+'
      transition[tend] = '+'
    end
    
    if transitions.include?(slot)
      transition[(slot * 2) + indent] = '|'
    end
    
    current_slots.each do |cs|
      line[(cs * 2) + indent] = '|'
      transition[(cs * 2) + indent] = '|'
    end
    
    line[(slot * 2) + indent] = '*'
    
    lines << line.collect! {|obj| obj.nil? ? ' ' : obj }.join
    lines << transition.collect! {|obj| obj.nil? ? ' ' : obj }.join
  end
  
  lines.join("\n")
end

#each(head = nil) ⇒ Object

Yields each node in the deconvoluted graph to the block with coordinates for rendering linkages between the nodes. The nodes are ordered from head to tails and respect the order of children.

Each node is assigned a slot (x), and at each iteration (y), there is information regarding which slots are currently open, and which slots need to be linked to produce the graph. For example, a simple fork-merge could be graphed like this:

Graph    node  x  y  current transistions
*        :a    0  0  []      [0,1]
|--+
*  |     :b    0  1  [1]     [0]
|  |
|  *     :c    1  2  [0]     [0]
|--+
*        :d    0  3  []      []

Where the coordinates are the arguments yielded to the block:

sha::   the sha for the node
slot::  the slot where the node belongs (x-axis)
index:: a counter for the number of nodes yielded (y-axis)
current_slots:: slots currently open (|)
transitions:: the slots that this node should connect to (|,--+)



154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
 
# File 'lib/gitgo/repo/graph.rb', line 154

def each(head=nil) # :yields: sha, slot, index, current_slots, transitions
  slots = []
  slot = {head => 0}
  
  # visit walks each branch in the DAG and collects the visited nodes
  # in reverse; that way uniq + reverse_each will iterate the nodes in
  # order, with merges pushed down as far as necessary
  order = visit(links, head)
  order.uniq!
  
  index = 0
  order.reverse_each do |sha|
    children = links[sha]
    parent_slot  = slot[sha]
    
    # free the parent slot if possible - if no children exist then the
    # sha is an open tail; keep these slots occupied
    slots[parent_slot] = nil unless children.empty?
    
    # determine currently occupied slots - any slots with a non-nil,
    # non-false value; in this case a number
    current_slots = slots.select {|s| s }
    
    transitions = children.collect do |child|
      # determine the next open (ie nil) slot for the child and occupy
      child_slot = slot[child] ||= (slots.index(nil) || slots.length)
      slots[child_slot] = child_slot
      child_slot
    end
    
    yield(sha, slot[sha], index, current_slots, transitions)
    index += 1
  end
  
  self
end

#empty? ⇒ Boolean

Returns true if head is nil (implying that no meaningful nodes can be reached from this graph).

Returns:

  • (Boolean) 


78
79
80
 
# File 'lib/gitgo/repo/graph.rb', line 78

def empty?
  head.nil?
end

#inspect ⇒ Object

Returns a string like:

#<Gitgo::Repo::Graph:object_id head="sha">



262
263
264
 
# File 'lib/gitgo/repo/graph.rb', line 262

def inspect
  "#<#{self.class}:#{object_id} head=#{head.inspect}>"
end

#links ⇒ Object

Returns a hash of (node, children) pairs mapping linkages in the deconvoluted graph. Links does not contain updated or deleted nodes and typically serves as the basis for drawing graphs.



96
97
98
99
100
101
102
103
104
105
106
107
 
# File 'lib/gitgo/repo/graph.rb', line 96

def links
  @links ||= begin
    links = {}
    unless head.nil?
      versions = nodes[nodes[head].original].versions
      versions.each {|sha| collect_links(sha, links) }
      
      links[nil] = versions
    end
    links
  end
end

#node(sha) ⇒ Object

Retrieves the node for the sha, or nil if the node is inaccessible from this document graph.



89
90
91
 
# File 'lib/gitgo/repo/graph.rb', line 89

def node(sha)
  nodes[sha]
end

#reset ⇒ Object

Resets the graph, recollecting all nodes and links. Reset is required detect new nodes inserted after initialization.

–

Nodes are collected in an ambigous order by collect_nodes. As a result is not feasible to determine the relationships of previous and updated nodes in one pass. First collects all nodes, then deconvolute original nodes. Updates do not have to be deconvoluted directly because they will be deconvoluted from their original (indeed it will cause duplicates in the graph tree if updates are deconvoluted separately).



244
245
246
247
248
249
250
251
252
253
254
255
256
 
# File 'lib/gitgo/repo/graph.rb', line 244

def reset
  @nodes = {}
  collect_nodes(head)
  
  nodes.each_value do |node|
    if node.original?
      node.deconvolute
    end
  end
  
  @links = nil
  self
end

#sort(&block) ⇒ Object

Sorts each of the children in links, using the block if given.



121
122
123
124
125
126
 
# File 'lib/gitgo/repo/graph.rb', line 121

def sort(&block)
  links.each_value do |children|
    children.sort!(&block)
  end
  self
end

#tails ⇒ Object

Returns an array the tail nodes in the deconvoluted graph.



110
111
112
113
114
115
116
117
118
 
# File 'lib/gitgo/repo/graph.rb', line 110

def tails
  @tails ||= begin
    tails = []
    links.each_pair do |node, children|
      tails << node if children.empty?
    end
    tails
  end
end