More accurate conflict detection

andybalholm

Apr 12, 2023, 12:01 AM

CHI2WRPHAI5ZDFO4NMUBNMQ5HIHBZBAZD4XV7OUSSZEDDMN4YGSAC

Dependencies

• [2] 4JR6O4JT Try a new approach to deletion
• [3] Z6CD2LYK Add tijo-conflicts command
• [4] AYLFNM5C Add the ability to output the contents of a file.

Change contents

• edit in output.go at line 56
  [3.148]

  [4.1090]
  +

  + // prev is the most recent non-deleted block.

  + var prev *Block

  +

  + // reachable is the set of blocks that are reachable from prev.

  + reachable := map[*Block]bool{

  + blocks[0]: true,

  + }
• replacement in output.go at line 66
  [4.1333]→[4.1333:1363](∅→∅)
  − if i == 0 {

  − continue

  − }
  [4.1333]

  [4.1363]
  + // We only check for conflicts when the current block is not one that

  + // has been deleted.

  + if len(b.DeletedBy) == 0 {

  + if !reachable[b] {

  + // If this block is not reachable from the previous block, the order between

  + // them is undetermined, and therefore we have a conflict.
• replacement in output.go at line 73
  [4.1364]→[4.1364:1845](∅→∅)
  − 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
  [4.1364]

  [4.1845]
  + // To find the start of the conflict, we need to look back for the most recent

  + // block from which b is reachable.

  + var start int

  + connected := map[*Block]bool{

  + b: true,

  + }

  + for j := i; j >= 0; j-- {

  + if j < i && len(blocks[j].DeletedBy) == 0 && connected[blocks[j]] {

  + start = j + 1

  + break

  + }

  + if connected[blocks[j]] {

  + for _, e := range blocks[j].ReverseEdges {

  + connected[e.From] = true

  + }

  + }
• edit in output.go at line 90
  [4.1851]→[4.1851:1856](∅→∅)
  − }
• replacement in output.go at line 91
  [4.1857]→[4.1857:2087](∅→∅)
  − // 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
  [4.1857]

  [4.2087]
  + // Skip deleted blocks at the start of the conflict.

  + for len(blocks[start].DeletedBy) > 0 {

  + start++
• edit in output.go at line 95
  [4.2093]→[4.2093:2098](∅→∅)
  − }
• replacement in output.go at line 96
  [4.2099]→[4.2099:2277](∅→∅),[4.2277]→[2.1254:1293](∅→∅),[2.1293]→[4.2298:2333](∅→∅),[4.2298]→[4.2298:2333](∅→∅)
  − // 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 len(blocks[j].DeletedBy) == 0 {

  − aliveBefore = true

  − break
  [4.2099]

  [4.2333]
  + // Rather than making a new map of blocks reachable from prev,

  + // we can reuse our work from the outer loop.

  + // The reachable map will be replaced at the end of the outer loop anyway.

  +

  + end := len(blocks)

  + for j := i + 1; j < len(blocks); j++ {

  + if len(blocks[j].DeletedBy) == 0 && reachable[blocks[j]] {

  + end = j

  + break

  + }

  + if reachable[blocks[j]] {

  + for _, e := range blocks[j].Edges {

  + reachable[e.To] = true

  + }

  + }
• replacement in output.go at line 112
  [4.2339]→[4.2339:2406](∅→∅),[4.2406]→[2.1294:1333](∅→∅),[2.1333]→[4.2427:2461](∅→∅),[4.2427]→[4.2427:2461](∅→∅)
  − }

  − aliveAfter := false

  − for j := i; j < closestChild; j++ {

  − if len(blocks[j].DeletedBy) == 0 {

  − aliveAfter = true

  − break
  [4.2339]

  [4.2461]
  +

  + // skip deleted blocks at the end of the conflict.

  + for len(blocks[end-1].DeletedBy) > 0 {

  + end--
• edit in output.go at line 117
  [4.2467]→[4.2467:2472](∅→∅)
  − }
• edit in output.go at line 118
  [4.2473]→[4.2473:2507](∅→∅)
  − if aliveBefore && aliveAfter {
• replacement in output.go at line 119
  [3.193]→[3.193:225](∅→∅)
  − Start: closestParent + 1,
  [3.193]

  [3.225]
  + Start: start,
• replacement in output.go at line 121
  [3.241]→[3.241:268](∅→∅)
  − End: closestChild,
  [3.241]

  [3.268]
  + End: end,
• edit in output.go at line 124
  [4.2605]

  [4.2605]
  +

  + prev = b

  + reachable = map[*Block]bool{

  + prev: true,

  + }
• edit in output.go at line 130
  [4.2609]

  [3.276]
  +

  + if reachable[b] {

  + for _, e := range b.Edges {

  + reachable[e.To] = true

  + }

  + }