Code duplication is detected, but proposed fix replaces the segment with the location of the ducplicate

[werner291]

Hello,

thank you for a very good IntelliJ plugin!

There appears to be a bug in a proposed code duplication change.

This is the source file that I was editing (please ignore the mess, it's what I was in the process of fixing)

module MonotoneTriangulate (triangulate) where

  import HalfEdgeDS

  import qualified Data.Map.Lazy as Map

  compareByXy (V2 x1 y1) (V2 x2 y2)
      | x1 < x2 = LT
      | x1 > x2 = GT
      | y1 < y2 = LT
      | y1 > y2 = GT
      | otherwise = EQ

  yAtX :: (Floating a) -> Edge a -> a
  yAtX atX (vA, vB) = let t = (atX - x vA) / (x vB - x vA)
                        in t * (y vB - y vA) + y vA

  interiorInsidePolygon v = crossZ (prev v - v) (next v - v) >= 0 -- TODO check if the sign on this is right

  data VertexType = Normal | Split | Merge | Start | End

  vertexType v
     | v > prev v && v > next v = if interiorInsidePolygon v
       then Start -- TODO check if the sign on this is right
       else Merge -- Mouth to the right
     | v < prev v && v < next v = if interiorInsidePolygon v
       then Split -- TODO check the sign here
       else End -- Mouth to the left
     | otherwise = Normal

  monotoneSplit :: HalfEdgeDS a vT eT fT -> Face -> (HalfEdgeDS a vT eT fT, [Face])
  monotoneSplit heds face = let
        sorted = sortBy (orderByXY) (outerEdges heds face) -- TODO deal with holes (should be easy enough)
        diagonals = evalState (performSweep sorted) (Map.empty, [])
        in splitFace heds face diagonals

  type SweepState a vT eT fT = (Map (YOrderedEdge a vT eT fT) HalfEdge, [(HalfEdgeDS, HalfEdgeDS)])

  data YOrderedEdge a vT eT fT = YOrderedEdge { heds :: HalfEdgeDS a vT eT fT , edge :: HalfEdge a eT}

  instance Eq (YOrderedEdge a vT eT fT) where
    a == b = edge a == edge b 

  instance (Floating a) => Ord (YOrderedEdge a vT eT fT) where
    compare (YOrderedEdge heds edgeA) (YOrderedEdge _ edgeB) =
      let xA = x (coordinates heds $ origin heds edgeA)
          xB = x (coordinates heds $ target heds edgeA)
          xC = x (coordinates heds $ origin heds edgeB)
          xD = x (coordinates heds $ target heds edgeB)
          cdXMin = min xC xD
          cdXMax = max xC xD
          compareAtX = yAtX (clamp cdXMin cdXMax ((xA + xB) / 2))
          in compare (yAtX (Edge (vert a, vert b))) (yAtX (Edge (vert c, vert d)))



  performMonotoneSplitSweep :: HalfEdgeDS a vT eT fT -> [HalfEdge a] -> SweepState

  performMonotoneSplitSweep heds [] = do
    (_, linesAdded) <- get
    return linesAdded

  performMonotoneSplitSweep heds (current:halfEdges) = do
    (edgesAndHelpers, _) <- get

    case vertexType vertex of
      Start -> do
        setHelper vertex vertex

      End -> do
        Combine with /home/werner/workspace/HaskyMcDrawface/src/MonotoneTriangulate.hs:84:9
        when (vertexType oldHelper == Merge)
          insertDiagonal (Edge oldHelper vertex)
        deleteHelper (incomingEdge vertex)

      Split -> do
        let (edgeBelow, helper) = fromJust $ Map.lookupLE (YOrderedEdge heds vertex) edgesAndHelpers
        insertDiagonal helper vertex
        setHelper (edgeBelow vertex) vertex
        setHelper (outgoingEdge vertex) vertex

      Merge -> do
        let oldHelper = edgesAndHelpers ! (incomingEdge vertex)
        when (vertexType oldHelper == Merge)
          insertDiagonal (Edge oldHelper vertex)
        deleteHelper (incomingEdge vertex)
        let (edgeBelow, leftOldHelper) = fromJust $ Map.lookupLE (outgoingEdge vertex)
        when (vertexType leftOldHelper == Merge)
          insertDiagonal (Edge leftOldHelper vertex)
        setHelper edgeBelow vertex

      Normal ->
        if (interiorInsidePolygon vertex)
          then do
            when (vertexType oldHelper == Merge)
              insertDiagonal (Edge oldHelper vertex)
            deleteHelper (incomingEdge vertex)
            setHelper (outgoingEdge vertex) vertex
          else do
            let (edgeBelow, helper) = fromJust $ Map.lookupLE (outgoingEdge vertex)
            setHelper edgeBelow vertex

    return (performSweep vertices)

  -- Set the helper vertex for a certain edge
  setHelper :: HalfEdgeDS a vT eT fT -> HalfEdge -> HalfEdge -> SweepState
  setHelper heds edge helper = do
    (edgesAndHelpers, linesAdded) <- get
    put ( insert (YOrderedEdge heds edge) helper edgesAndHelpers , linesAdded )

  -- Set the helper vertex for a certain edge
  deleteHelper :: HalfEdgeDS a vT eT fT -> HalfEdge -> HalfEdge -> SweepState
  deleteHelper edge helper = do
    (edgesAndHelpers, linesAdded) <- get
    put ( delete edge edgesAndHelpers , linesAdded )

  insertDiagonal :: HalfEdge -> HalfEdge -> SweepState
  insertDiagonal from to =
    state (\(edgesAndHelpers, linesAdded) -> (edgesAndHelpers, (from,to) : linesAdded))

  triangulateMonotone :: HalfEdgeDS a vT eT fT -> Face -> (HalfEdgeDS a vT eT fT, [Face])
  triangulateMonotone heds fp = let
    sortedEdges = sortBy compareByXy $ outerEdges heds fp
    triangulateFoldStep (above,below,diagonals) currentEdge =
      if above == previousId currentEdge
        then (currentEdge, below, (below, currentEdge) : diagonals)
        else (above, currentEdge, (currentEdge, above) : diagonals)
    (_,_,diagonals) = foldl triangulateFoldStep (sortedEdges ! 0, sortedEdges ! 1, []) sortedEdges
    in splitFace heds fp diagonals


  triangulate :: HalfEdgeDS a vT eT fT -> Face -> (HalfEdgeDS a vT eT fT, [Face])
  triangulate heds face = let
    (hedsMonotone, monotoneFaces) = monotoneSplit heds face
    triangulateFoldStep (heds,triangles) = let
      (newHeds,newTriangles) = expression
      in (newHeds,newTriangles ++ triangles) -- TODO check whether this gives O(n^2) running time...
    in foldl triangulateFoldStep (hedsMonotone,[]) monotoneFaces

intellij-haskell correctly deduced that edgesAndHelpers ! (incomingEdge vertex) is duplicated, but proposes to replace it with Combine with /home/werner/workspace/HaskyMcDrawface/src/MonotoneTriangulate.hs:84:9, which is the location of the second occurrence of the duplicated code.

[rikvdkleij]

Thanks for reporting!

Can you create minimal example of your issue? Your code does not compile because it's depending on HalfEdgeDS.

[ice1000]

@rikvdkleij This is very very easy to reproduce, just copy&paste two big functions and give them different name, hlint will give warning about duplication. Apply the suggestion, you'll reproduce.

The fix to this also looks simple, I guess.

[rikvdkleij]

The complexity is applying this kind of hllint suggestions in general. For other kinds of hlint suggestions applying works great.

[rikvdkleij]

But yes, would be nice if this issue could be properly solved. Need some time..