Commits

ZyX_I committed e5c74aa

@aurum/log: Added port of git graphing algorithm. Port of mercurial graphing algorithm is still used

Comments (0)

Files changed (4)

 labeltypes :: [ String ]                               *aurum-repo.labeltypes*
     List of label types supported by |aurum-rf-label|. First type will be 
     default used by |:AuName|.
+requires_sort :: Bool                               *aurum-repo.requires_sort*
+    Determines whether it is necessary to run sort_in_topological_order 
+    function on commit list returned by |aurum-rf-revrange| when it is about 
+    to be displayed in |aurum://log| buffer. If it is false, then this list 
+    will only be reversed (|reverse()|).
+    This key is optional, default value: true.
+has_octopus_merges :: Bool                     *aurum-repo.has_octopus_merges*
+    Determines whether repository has merges containing more then two parents. 
+    In this case slower, but more universal algorithm will be used.
+    This key is optional, default value: true.
 functions :: {String : FRef}                            *aurum-repo.functions*
     Dictionary that contains all driver-specific functions. All functions 
     except |aurum-rf-repo|, |aurum-rf-checkdir| and |aurum-rf-checkremote| 

plugin/aurum/drivers/mercurial.vim

     " TODO remove bookmark label type if it is not available
     let repo={'path': a:path, 'changesets': {}, 'cslist': [],
                 \'local': (stridx(a:path, '://')==-1),
-                \'labeltypes': ['tag', 'bookmark'],}
+                \'labeltypes': ['tag', 'bookmark'],
+                \'has_octopus_merges': 0, 'requires_sort': 0}
     return repo
 endfunction
 endif

plugin/aurum/log.vim

     finish
 endif
 let s:F.glog={}
+let s:F.graph={}
 let s:F.temp={}
 let s:_options={
             \'ignorefiles': {'default': [],
             \'2multl': 'Two multiline statements on one line',
             \'argmis': 'Missing argument #%u for keyword %s',
         \}
+"▶1 graph
+"▶2 graph.update_state :: graph, gstate → + graph
+function s:F.graph.update_state(s)
+    let self.prev_state=self.state
+    let self.state=a:s
+endfunction
+"▶2 graph.ensure_capacity :: graph, num_columns → + graph
+function s:F.graph.ensure_capacity(num_columns)
+    let mdiff=(a:num_columns*2)-len(self.mapping)
+    if mdiff>0
+        let plist=repeat([-1], mdiff)
+        let self.mapping+=plist
+        let self.new_mapping+=plist
+    endif
+endfunction
+"▶2 graph.is_interesting_hex :: graph, hex → Bool
+function s:F.graph.is_interesting_hex(hex)
+    return has_key(self.addchangesets, a:hex)
+endfunction
+"▶2 graph.next_interesting_parent :: graph, [hex] → Maybe [hex]
+function s:F.graph.next_interesting_parent(orig)
+    for i in range(1, len(a:orig)-1)
+        if self.is_interesting_hex(a:orig[i])
+            return a:orig[(i):]
+        endif
+    endfor
+    return []
+endfunction
+"▶2 graph.first_interesting_parent :: graph → Maybe [hex]
+function s:F.graph.first_interesting_parent()
+    let parents=self.cs.parents
+    if empty(parents)
+        return []
+    elseif self.is_interesting_hex(parents[0])
+        return parents
+    else
+        return self.next_interesting_parent(parents)
+    endif
+endfunction
+"▶2 graph.insert_into_new_columns :: graph, cs, mapindex → mapindex + graph
+function s:F.graph.insert_into_new_columns(cs, mapindex)
+    let i=0
+    for column in self.new_columns
+        if column.hex is# a:cs.hex
+            let self.mapping[a:mapindex]=i
+            return a:mapindex+2
+        endif
+        let i+=1
+    endfor
+    let self.mapping[a:mapindex]=len(self.new_columns)
+    call add(self.new_columns, {'hex': a:cs.hex})
+    return a:mapindex+2
+endfunction
+"▶2 graph.update_width :: graph, is_cs_in_existing_columns → + graph
+function s:F.graph.update_width(is_cs_in_existing_columns)
+    let maxcols=len(self.columns)+self.num_parents
+    if self.num_parents<1
+        let maxcols+=1
+    endif
+    if a:is_cs_in_existing_columns
+        let maxcols-=1
+    endif
+    let self.width=maxcols*2
+endfunction
+"▶2 graph.update_columns :: graph → + graph
+function s:F.graph.update_columns()
+    let self.columns=self.new_columns
+    let self.new_columns=[]
+    let max_new_columns=len(self.columns)+self.num_parents
+    call self.ensure_capacity(max_new_columns)
+    let self.mapping_size=2*max_new_columns
+    if !empty(self.mapping)
+        call remove(self.mapping, 0, self.mapping_size-1)
+    endif
+    call extend(self.mapping, repeat([-1], self.mapping_size), 0)
+    let seen=0
+    let midx=0
+    let is_cs_in_columns=1
+    let num_columns=len(self.columns)
+    for i in range(num_columns+1)
+        if i==num_columns
+            if seen
+                break
+            endif
+            let is_cs_in_columns=0
+            let ccshex=self.cs.hex
+        else
+            let ccshex=self.columns[i].hex
+        endif
+        if ccshex is# self.cs.hex
+            let oldmidx=midx
+            let seen=1
+            let self.commit_index=i
+            let parents=self.first_interesting_parent()
+            while !empty(parents)
+                let midx=self.insert_into_new_columns(
+                            \            self.repo.changesets[parents[0]], midx)
+                let parents=self.next_interesting_parent(parents)
+            endwhile
+            if midx==oldmidx
+                let midx+=2
+            endif
+        else
+            let midx=self.insert_into_new_columns(self.repo.changesets[ccshex],
+                        \                         midx)
+        endif
+    endfor
+    while self.mapping_size>1 && self.mapping[self.mapping_size-1]==-1
+        let self.mapping_size-=1
+    endwhile
+    call self.update_width(is_cs_in_columns)
+endfunction
+"▶2 graph.update :: graph, cs → + graph
+function s:F.graph.update(cs)
+    let self.cs=a:cs
+    let self.num_parents=len(filter(copy(a:cs.parents),
+                \               'self.is_interesting_hex(v:val)'))
+    let self.prev_commit_index=self.commit_index
+    call self.update_columns()
+    let self.expansion_row=0
+    if self.state isnot# 'padding'
+        let self.state='skip'
+    elseif self.num_parents>2 &&
+                \self.commit_index<(len(self.columns)-1)
+        let self.state='precommit'
+    else
+        let self.state='commit'
+    endif
+endfunction
+"▶2 graph.is_mapping_correct :: graph → Bool
+function s:F.graph.is_mapping_correct()
+    return empty(filter(self.mapping[:(self.mapping_size-1)],
+                \       '!(v:val==-1 || v:val==v:key/2)'))
+endfunction
+"▶2 graph.pad_horizontally :: graph, chars_written → String
+" XXX Replace somehow?
+function s:F.graph.pad_horizontally(chars_written)
+    if a:chars_written>=self.width
+        return ''
+    endif
+    return repeat(' ', self.width-a:chars_written)
+endfunction
+"▶2 graph.output_padding_line :: graph → String
+function s:F.graph.output_padding_line()
+    let lnc=len(self.new_columns)
+    return repeat('| ', lnc).self.pad_horizontally(lnc*2)
+endfunction
+"▶2 graph.output_skip_line :: graph → String
+function s:F.graph.output_skip_line()
+    call self.update_state(((self.num_parents>2 &&
+                \            self.commit_index<(len(self.columns)-1))?
+                \               ('precommit'):
+                \               ('commit')))
+    return '...'.self.pad_horizontally(3)
+endfunction
+"▶2 graph.output_pre_commit_line :: graph → String
+function s:F.graph.output_pre_commit_line()
+    let num_expansion_rows=(self.num_parents-2)*2
+    let seen=0
+    let r=''
+    let i=-1
+    for column in self.columns
+        let i+=1
+        if column.hex is# self.cs.hex
+            let seen=1
+            let r.='|'.repeat(' ', self.expansion_row)
+        elseif seen && self.expansion_row==0
+            let r.='|\'[self.prev_state is# 'postmerge' &&
+                        \self.prev_commit_index<i]
+        elseif seen && self.expansion_row>0
+            let r.='\'
+        else
+            let r.='|'
+        endif
+        let r.=' '
+    endfor
+    let r.=self.pad_horizontally(len(r))
+    let self.expansion_row+=1
+    if self.expansion_row>num_expansion_rows
+        call self.update_state('commit')
+    endif
+    return r
+endfunction
+"▶2 graph.output_commit_char :: graph → String
+function s:F.graph.output_commit_char()
+    return '@o'[index(self.workcss, self.cs.hex)==-1]
+endfunction
+"▶2 graph.draw_octopus_merge :: graph → String
+function s:F.graph.draw_octopus_merge()
+    let r=''
+    for i in range(((self.num_parents-2)*2)-1)
+        let r.='-'
+    endfor
+    let r.='.'
+    return r
+endfunction
+"▶2 graph.output_commit_line :: graph → String
+function s:F.graph.output_commit_line()
+    let seen=0
+    let r=''
+    for i in range(len(self.columns)+1)
+        if i==len(self.columns)
+            if seen
+                break
+            endif
+            let ccshex=self.cs.hex
+        else
+            let ccshex=self.columns[i].hex
+        endif
+        if ccshex is# self.cs.hex
+            let seen=1
+            let r.=self.output_commit_char()
+            if self.num_parents>2
+                let r.=self.draw_octopus_merge()
+            endif
+        elseif seen && self.num_parents>2
+            let r.='\'
+        elseif seen && self.num_parents==2
+            let r.='|\'[self.prev_state is# 'postmerge' &&
+                        \self.prev_commit_index<i]
+        else
+            let r.='|'
+        endif
+        let r.=' '
+    endfor
+    let r.=self.pad_horizontally(len(r))
+    call self.update_state(((self.num_parents>1)?
+                \             ('postmerge'):
+                \          ((self.is_mapping_correct())?
+                \             ('padding')
+                \          :
+                \             ('collapsing'))))
+    return r
+endfunction
+"▶2 graph.output_post_merge_line :: graph → String
+function s:F.graph.output_post_merge_line()
+    let seen=0
+    let r=''
+    for i in range(len(self.columns)+1)
+        if i==len(self.columns)
+            if seen
+                break
+            endif
+            let ccshex=self.cs.hex
+        else
+            let ccshex=self.columns[i].hex
+        endif
+        if ccshex is# self.cs.hex
+            let seen=1
+            let parents=self.first_interesting_parent()
+            let r.='|'.repeat('\ ', self.num_parents-1)
+        else
+            let r.='|\'[seen].' '
+        endif
+    endfor
+    let r.=self.pad_horizontally(len(r))
+    call self.update_state(((self.is_mapping_correct())?
+                \               ('padding'):
+                \               ('collapsing')))
+    return r
+endfunction
+"▶2 graph.output_collapsing_line :: graph → String
+function s:F.graph.output_collapsing_line()
+    let used_horizontal=0
+    let horizontal_edge=-1
+    let horizontal_edge_target=-1
+    let self.new_mapping=repeat([-1], self.mapping_size)
+    for [i, target] in map(self.mapping[:(self.mapping_size-1)],
+                \          '[v:key, v:val]')
+        if target==-1
+            continue
+        elseif i==target*2
+            let self.new_mapping[i]=target
+        elseif self.new_mapping[i-1]==-1
+            let self.new_mapping[i-1]=target
+            if horizontal_edge==-1
+                let horizontal_edge=i
+                let horizontal_edge_target=target
+                let j=(target*2)+3
+                while j<i-2
+                    let self.new_mapping[j]=target
+                    let j+=2
+                endwhile
+            endif
+        elseif self.new_mapping[i-1]==target
+        else
+            let self.new_mapping[i-2]=target
+            if horizontal_edge==-1
+                let horizontal_edge=1
+            endif
+        endif
+    endfor
+    if self.mapping[self.mapping_size-1]==-1
+        let self.mapping_size-=1
+    endif
+    let r=''
+    for [i, target] in map(self.new_mapping[:(self.mapping_size-1)],
+                \          '[v:key, v:val]')
+        if target==-1
+            let r.=' '
+        elseif target*2==i
+            let r.='|'
+        elseif target==horizontal_edge_target && i!=horizontal_edge-1
+            if i!=(target*2)+3
+                let self.new_mapping[i]=-1
+            endif
+            let used_horizontal=1
+            let r.='_'
+        else
+            if used_horizontal && i<horizontal_edge
+                let self.new_mapping[i]=-1
+            endif
+            let r.='/'
+        endif
+    endfor
+    let r.=self.pad_horizontally(len(r))
+    let [self.mapping, self.new_mapping]=
+                \[self.new_mapping, self.mapping]
+    if self.is_mapping_correct()
+        call self.update_state('padding')
+    endif
+    return r
+endfunction
+"▶2 graph.next_line :: graph → String
+let s:gstatesfmap={
+            \'padding':    s:F.graph.output_padding_line,
+            \'skip':       s:F.graph.output_skip_line,
+            \'precommit':  s:F.graph.output_pre_commit_line,
+            \'commit':     s:F.graph.output_commit_line,
+            \'postmerge':  s:F.graph.output_post_merge_line,
+            \'collapsing': s:F.graph.output_collapsing_line,
+        \}
+function s:F.graph.next_line()
+    return call(s:gstatesfmap[self.state], [], self)
+endfunction
+"▶2 graph.padding_line :: graph → String
+function s:F.graph.padding_line()
+    if self.state isnot# 'commit'
+        return self.next_line()
+    endif
+    let r=''
+    for column in self.columns
+        let ccshex=column.hex
+        let r.='|'.repeat(' ', ((ccshex isnot# self.cs.hex ||
+                    \            self.num_parents<3)?
+                    \               (1):
+                    \               ((self.num_parents-2)*2)))
+    endfor
+    let r.=self.pad_horizontally(len(self.columns))
+    let self.prev_state='padding'
+    return r
+endfunction
+"▶2 graph.is_commit_finished :: graph → Bool
+function s:F.graph.is_commit_finished()
+    return (self.state is# 'padding')
+endfunction
+"▶2 graph.show_commit :: graph → [String]
+function s:F.graph.show_commit()
+    let r=[]
+    while 1
+        try
+            if self.state is# 'commit'
+                break
+            endif
+        finally
+            " XXX We need at least one iteration. :finally makes sure it will be 
+            " done
+            let r+=[self.next_line()]
+        endtry
+    endwhile
+    return r
+endfunction
+"▶2 graph.show_remainder :: graph → [String]
+function s:F.graph.show_remainder()
+    let r=[]
+    while !self.is_commit_finished()
+        let r+=[self.next_line()]
+    endwhile
+    return r
+endfunction
 "▶1 glog
 "▶2 glog.utfedges
 function s:F.glog.utfedges(seen, hex, parents)
     endfor
     return r
 endfunction
+"▶2 glog.graph_init :: repo, [cs] → graph
+let s:defgraph={
+            \'cs':                0,
+            \'num_parents':       0,
+            \'expansion_row':     0,
+            \'state':             'padding',
+            \'prev_state':        'padding',
+            \'commit_index':      0,
+            \'prev_commit_index': 0,
+            \'columns':           [],
+            \'new_columns':       [],
+            \'mapping':           [],
+            \'new_mapping':       [],
+            \'mapping_size':      0,
+            \'addchangesets':     {},
+        \}
+function s:F.glog.graph_init(css, showparents, opts)
+    let graph=deepcopy(s:defgraph)
+    let graph.repo=a:opts.repo
+    let graph.workcss=a:showparents
+    call map(copy(a:css),
+                \'((has_key(a:opts.skipchangesets, v:val.hex))?(0):'.
+                \   '(extend(graph.addchangesets, {v:val.hex : v:val})))')
+    call extend(graph, s:F.graph)
+    return graph
+endfunction
+"▶2 glog.show_log :: graph, cs, Text → Text
+function s:F.glog.show_log(graph, cs, text)
+    let lines=((a:graph.cs is 0)?([]):(a:graph.show_remainder()))
+    call a:graph.update(a:cs)
+    let lines+=a:graph.show_commit()
+    let collen=len(lines[-1])
+    let a:text.block_r[0][1]+=collen
+    let a:text.block_r[1][1]+=collen
+    let lines[-1].=get(a:text.text, 0, '')
+    let cchar=a:graph.output_commit_char()
+    let bidx=stridx(lines[-1], cchar)
+    if bidx!=-1
+        let a:text.special.bullet=[0, bidx, cchar]
+    endif
+    for line in a:text.text[1:]
+        let lines+=[a:graph.next_line().line]
+    endfor
+    let a:text.text=lines
+    return a:text
+endfunction
+"▶2 glog.log_show_all :: [cs], showparents, opts → Log
+function s:F.glog.log_show_all(css, showparents, opts)
+    let graph=s:F.glog.graph_init(a:css, a:showparents, a:opts)
+    let show_header=1
+    let r={'text': [], 'specials': {}, 'rectangles': [], 'csstarts': {}}
+    for cs in a:css
+        let skip=has_key(a:opts.skipchangesets, cs.hex)
+        if skip
+            let text={'text': [], 'special': {}, 'block_r': [[0, 0], [0, 0]]}
+        else
+            let text=a:opts.templatefunc(cs, a:opts)
+            let text.block_r=[[0, 0],
+                        \     [len(text.text)-1,
+                        \      max(map(copy(text.text), 'len(v:val)'))]]
+        endif
+        let text=s:F.glog.show_log(graph, cs, text)
+        let r.text+=text.text
+        if !skip
+            let text.block_r[0][0]+=len(r.text)
+            let text.block_r[1][0]+=len(r.text)
+            let r.specials[cs.hex]=text.special
+            let r.rectangles+=[text.block_r+[cs.hex]]
+            let r.csstarts[cs.hex]=text.block_r[0][0]
+        endif
+    endfor
+    return r
+endfunction
+"▶2 s:DateCmp :: cs, cs → -1|0|1
+function s:DateCmp(a, b)
+    let a=a:a.time
+    let b=a:b.time
+    return ((a==b)?(0):((a>b)?(-1):(1)))
+endfunction
+let s:_functions+=['s:DateCmp']
+"▶2 glog.sort_in_topological_order :: [cs] → [cs]
+function s:F.glog.sort_in_topological_order(repo, css)
+    call map(copy(a:css), 'extend(v:val, {"indegree": 1})')
+    for parents in map(copy(a:css), 'v:val.parents')
+        for parent in filter(map(filter(copy(parents),
+                    \                   'has_key(a:repo.changesets, v:val)'),
+                    \            'a:repo.changesets[v:val]'),
+                    \        'get(v:val, "indegree", 0)')
+            let parent.indegree+=1
+        endfor
+    endfor
+    let work=[]
+    call map(copy(a:css), 'v:val.indegree==1 && add(work, v:val) is 0')
+    call sort(work, 's:DateCmp')
+    let r=[]
+    while !empty(work)
+        let cs=remove(work, 0)
+        for parent in filter(map(filter(copy(cs.parents),
+                    \                   'has_key(a:repo.changesets, v:val)'),
+                    \            'a:repo.changesets[v:val]'),
+                    \        'get(v:val, "indegree", 0)')
+            let parent.indegree-=1
+            if parent.indegree==1
+                let j=0
+                let lwork=len(work)
+                while j<lwork && work[j].time<parent.time
+                    let j+=1
+                endwhile
+                call insert(work, parent, j)
+            endif
+        endfor
+        let cs.indegree=0
+        call add(r, cs)
+    endwhile
+    call map(copy(a:css), 'remove(v:val, "indegree")')
+    return r
+endfunction
 "▶2 glog.graphlog
 function s:F.glog.graphlog(repo, opts, css)
-    let css=reverse(copy(a:css))
     let a:opts.repo=a:repo
-    return s:F.glog.generate(css, [a:repo.functions.getworkhex(a:repo)], a:opts)
+    if get(a:repo, 'requires_sort', 1)
+        let css=s:F.glog.sort_in_topological_order(a:repo, a:css)
+    else
+        let css=reverse(copy(a:css))
+    endif
+    let d={}
+    if get(a:repo, 'has_octopus_merges', 1)
+        let d.func=s:F.glog.log_show_all
+    else
+        let d.func=s:F.glog.generate
+    endif
+    return d.func(css, [a:repo.functions.getworkhex(a:repo)], a:opts)
 endfunction
 "▶1 temp
 "▶2 s:templates
         let hex=a:repo.functions.getrevhex(a:repo, opts.revision)
         let cs=a:repo.changesets[hex]
         if type(cs.rev)==type(0) && cs.rev<opts.revs[1]
-            let opts.revs[1]=cs.rev
+            let opts.revs[1]=cs.hex
         endif
         let opts.revisions={}
         let addrevs=[cs]
     try:
         repo=g_repo(path)
         # TODO remove bookmark label type if it is not available
-        vim_repo={
-            'changesets': {},
-                'cslist': [],
-                 'local': 1 if repo.local() else 0,
-            'labeltypes': ['tag', 'bookmark'],
+        vim_repo={'has_octopus_merges': 0,
+                       'requires_sort': 0,
+                          'changesets': {},
+                              'cslist': [],
+                               'local': 1 if repo.local() else 0,
+                          'labeltypes': ['tag', 'bookmark'],
                  }
         if hasattr(repo, '__len__'):
             vim_repo['csnum']=len(repo)+1