tmf.ui: fix line thickness bug on arrows.

Use the Cohen Sutherland algorithm to clip lines properly. Adds a log(n) compute time,
but fixes the bug in Linux's LibCairo gtk library.

Bug 470115

Change-Id: Ic4ce13398b25c2c2628283a0017419fe5bdbbb02
Signed-off-by: Matthew Khouzam <matthew.khouzam@ericsson.com>
Reviewed-on: https://git.eclipse.org/r/111937
Tested-by: Hudson CI
Reviewed-by: Loic Prieur-Drevon <loic.prieurdrevon@gmail.com>

1 files changed, 128 insertions, 2 deletions

diff --git a/tmf/org.eclipse.tracecompass.tmf.ui/src/org/eclipse/tracecompass/tmf/ui/widgets/timegraph/widgets/TimeGraphControl.java b/tmf/org.eclipse.tracecompass.tmf.ui/src/org/eclipse/tracecompass/tmf/ui/widgets/timegraph/widgets/TimeGraphControl.java
index d7da4ee7ed..8ceb64c811 100644
--- a/tmf/org.eclipse.tracecompass.tmf.ui/src/org/eclipse/tracecompass/tmf/ui/widgets/timegraph/widgets/TimeGraphControl.java
+++ b/tmf/org.eclipse.tracecompass.tmf.ui/src/org/eclipse/tracecompass/tmf/ui/widgets/timegraph/widgets/TimeGraphControl.java
@@ -36,6 +36,7 @@ import java.util.Queue;
 import java.util.Set;
 
 import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
 import org.eclipse.jface.action.IStatusLineManager;
 import org.eclipse.jface.resource.JFaceResources;
 import org.eclipse.jface.resource.LocalResourceManager;
@@ -121,6 +122,15 @@ public class TimeGraphControl extends TimeGraphBaseControl
         MenuDetectListener, ITmfTimeGraphDrawingHelper, ITimeGraphColorListener, Listener {
 
     /**
+     * Quadrant bitmaks for Cohen Sutherland
+     */
+    private static final int DOWN = 1 << 4;
+    private static final int UP = 1 << 3;
+    private static final int RIGHT = 1 << 2;
+    private static final int LEFT = 1 << 1;
+    private static final int INSIDE = 0;
+
+    /**
      * Constant indicating that all levels of the time graph should be expanded
      */
     public static final int ALL_LEVELS = AbstractTreeViewer.ALL_LEVELS;
@@ -2264,7 +2274,7 @@ public class TimeGraphControl extends TimeGraphBaseControl
         drawArrow(getColorScheme(), event, getArrowRectangle(bounds, event), gc);
     }
 
-    private Rectangle getArrowRectangle(Rectangle bounds, ILinkEvent event) {
+    private @Nullable Rectangle getArrowRectangle(Rectangle bounds, ILinkEvent event) {
         int srcIndex = fItemData.findItemIndex(event.getEntry());
         int destIndex = fItemData.findItemIndex(event.getDestinationEntry());
 
@@ -2286,7 +2296,123 @@ public class TimeGraphControl extends TimeGraphBaseControl
 
         int y0 = src.y + src.height / 2;
         int y1 = dst.y + dst.height / 2;
-        return new Rectangle(x0, y0, x1 - x0, y1 - y0);
+        return cohenSutherlandClipped(bounds, x0, y0, x1, y1);
+    }
+
+    /**
+     * Computer graphics algorithm used for line clipping, workaround for Cairo bug
+     *
+     * https://bugs.eclipse.org/bugs/show_bug.cgi?id=470115
+     *
+     * https://bugs.freedesktop.org/show_bug.cgi?id=103840
+     *
+     * @param bounds
+     *            the clipping rectangle
+     * @param x0
+     *            point 0 x
+     * @param y0
+     *            point 0 y
+     * @param x1
+     *            point 1 x
+     * @param y1
+     *            point 1 y
+     * @return
+     */
+    private static Rectangle cohenSutherlandClipped(Rectangle bounds, int x0, int y0, int x1, int y1) {
+        int quadrant0 = computeQuadrant(x0, y0, bounds);
+        int quadrant1 = computeQuadrant(x1, y1, bounds);
+        if (quadrant0 == 0 && quadrant1 == 0) {
+            return new Rectangle(x0, y0, x1 - x0, y1 - y0);
+        }
+        if ((quadrant0 & quadrant1) != 0 || bounds.width == 0 || bounds.height == 0) {
+            return null;
+        }
+        long deltaY = (long) y1 - (long) y0;
+        long deltaX = (long) x1 - (long) x0;
+        double slope = deltaY / (double) deltaX;
+        double antiSlope = deltaX / (double) deltaY;
+        int newX0 = x0;
+        int newY0 = y0;
+        int newX1 = x1;
+        int newY1 = y1;
+        // log n iterations
+        while (quadrant0 != 0) {
+            if ((quadrant0 & UP) != 0) {
+                newX0 = (int) (newX0 + antiSlope * (bounds.y - newY0));
+                newY0 = bounds.height + bounds.y;
+            } else if ((quadrant0 & DOWN) != 0) {
+                newX0 = (int) (newX0 + antiSlope * (bounds.y + bounds.height - newY0));
+                newY0 = bounds.y;
+            } else if ((quadrant0 & RIGHT) != 0) {
+                newY0 = (int) (newY0 + slope * (bounds.x + bounds.width - newX0));
+                newX0 = bounds.x + bounds.width;
+            } else {
+                newY0 = (int) (newY0 + slope * (bounds.x - newX0));
+                newX0 = bounds.x;
+            }
+            quadrant0 = computeQuadrant(newX0, newY0, bounds);
+        }
+        // ditto
+        while (quadrant1 != 0) {
+            if ((quadrant1 & UP) != 0) {
+                newX1 = (int) (newX0 + antiSlope * (bounds.y - newY0));
+                newY1 = bounds.height + bounds.y;
+            } else if ((quadrant1 & DOWN) != 0) {
+                newX1 = (int) (newX0 + antiSlope * (bounds.y + bounds.height - newY0));
+                newY1 = bounds.y;
+            } else if ((quadrant1 & RIGHT) != 0) {
+                newY1 = (int) (newY0 + slope * (bounds.x + bounds.width - newX0));
+                newX1 = bounds.x + bounds.width;
+            } else {
+                newY1 = (int) (newY0 + slope * (bounds.x - newX0));
+                newX1 = bounds.x;
+            }
+            quadrant1 = computeQuadrant(newX1, newY1, bounds);
+        }
+        return new Rectangle(newX0, newY0, newX1 - newX0, newY1 - newY0);
+    }
+
+    /**
+     * Cohen Sutherland compute algorithm
+     * <table>
+     * <tr>
+     * <th>0101</th>
+     * <th>0100</th>
+     * <th>0110</th>
+     * </tr>
+     * <tr>
+     * <th>0001</th>
+     * <th>0000</th>
+     * <th>0010</th>
+     * </tr>
+     * <tr>
+     * <th>1001</th>
+     * <th>1000</th>
+     * <th>1010</th>
+     * </tr>
+     * </table>
+     *
+     * @param x
+     *            point x
+     * @param y
+     *            point y
+     * @param bounds
+     *            bounds rectangle
+     * @return a quadrant
+     */
+    private static int computeQuadrant(int x, int y, Rectangle bounds) {
+        int retCode = INSIDE;
+        if (x < bounds.x) {
+            retCode |= LEFT;
+        } else if (x > (bounds.x + bounds.width)) {
+            retCode |= RIGHT;
+        }
+        if (y < bounds.y) {
+            retCode |= UP;
+        } else if (y > (bounds.y + bounds.height)) {
+            retCode |= DOWN;
+        }
+        return retCode;
     }
 
     /**