+ package pijul
+
+ import (
+ "fmt"
+ "io"
+ )
+
+ // topologicalSort returns a slice of b and its children, sorted
+ // topologically.
+ // It uses the algorithm from
+ // https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search,
+ // except that cycles are treated like the end of a branch of the
+ // graph instead of causing the search to abort.
+ func topologicalSort(b *Block) []*Block {
+ var list []*Block
+ visited := make(map[*Block]bool)
+
+ var visit func(*Block)
+ visit = func(n *Block) {
+ if visited[n] {
+ return
+ }
+ visited[n] = true
+ for _, e := range n.Edges {
+ visit(e.To)
+ }
+ list = append(list, n)
+ }
+
+ visit(b)
+
+ // Reverse the list.
+ for i, j := 0, len(list)-1; i < j; i, j = i+1, j-1 {
+ list[i], list[j] = list[j], list[i]
+ }
+
+ return list
+ }
+
+ func OutputFile(dest io.Writer, inode *Block) error {
+ blocks := topologicalSort(inode)
+ index := make(map[*Block]int, len(blocks))
+ deleted := make([]bool, len(blocks))
+ for i, b := range blocks {
+ index[b] = i
+ if b.ReverseEdges[0].Flag&EdgeFlagsDeleted != 0 {
+ deleted[i] = true
+ }
+ }
+
+ // These maps tell us how many conflicts begin (etc.) directly before the
+ // specified index of blocks.
+ conflictStart := make(map[int]int)
+ conflictCenter := make(map[int]int)
+ conflictEnd := make(map[int]int)
+
+ for i, b := range blocks {
+ if i == 0 {
+ continue
+ }
+
+ hasEdge := false
+ for _, e := range blocks[i-1].Edges {
+ if e.To == b {
+ hasEdge = true
+ break
+ }
+ }
+ if !hasEdge {
+ // If this block is not a child of the previous block, the order between
+ // them is undetermined, and therefore we have a conflict.
+
+ // The conflict begins just after the closest parent of b.
+ closestParent := -1
+ for _, e := range b.ReverseEdges {
+ parent := index[e.From]
+ if parent > closestParent {
+ closestParent = parent
+ }
+ }
+
+ // The conflict ends just before the closest child of the previous block.
+ closestChild := len(blocks)
+ for _, e := range blocks[i-1].Edges {
+ child := index[e.To]
+ if child < closestChild {
+ closestChild = child
+ }
+ }
+
+ // If either side of the conflict consists entirely of deleted vertices,
+ // it's not really a conflict.
+ aliveBefore := false
+ for j := closestParent + 1; j < i; j++ {
+ if !deleted[j] {
+ aliveBefore = true
+ break
+ }
+ }
+ aliveAfter := false
+ for j := i; j < closestChild; j++ {
+ if !deleted[j] {
+ aliveAfter = true
+ break
+ }
+ }
+
+ if aliveBefore && aliveAfter {
+ conflictStart[closestParent+1]++
+ conflictCenter[i]++
+ conflictEnd[closestChild]++
+ }
+ }
+ }
+
+ for i, b := range blocks {
+ for j := 0; j < conflictEnd[i]; j++ {
+ fmt.Fprintf(dest, ">>>>>>>\n")
+ }
+ for j := 0; j < conflictCenter[i]; j++ {
+ fmt.Fprintf(dest, "======= %v\n", b.Change)
+ }
+ for j := 0; j < conflictStart[i]; j++ {
+ fmt.Fprintf(dest, "<<<<<<< %v\n", b.Change)
+ }
+
+ if deleted[i] {
+ continue
+ }
+
+ _, err := dest.Write(b.Content)
+ if err != nil {
+ return err
+ }
+ }
+
+ return nil
+ }