[CORD-2631] Handling dual links in T3

Change-Id: I1c1875902c3cc8744ecb9deb63a806d2c64c29ff
(cherry picked from commit e0686e729fbaf4ce236fbd409f323428a513c5b3)
diff --git a/src/main/java/org/onosproject/t3/impl/TroubleshootManager.java b/src/main/java/org/onosproject/t3/impl/TroubleshootManager.java
index c206176..21f56e8 100644
--- a/src/main/java/org/onosproject/t3/impl/TroubleshootManager.java
+++ b/src/main/java/org/onosproject/t3/impl/TroubleshootManager.java
@@ -131,6 +131,8 @@
      */
     private StaticPacketTrace getTrace(List<ConnectPoint> completePath, ConnectPoint in, StaticPacketTrace trace) {
 
+        log.debug("------------------------------------------------------------");
+
         //if the trace already contains the input connect point there is a loop
         if (pathContainsDevice(completePath, in.deviceId())) {
             trace.addResultMessage("Loop encountered in device " + in.deviceId());
@@ -151,6 +153,7 @@
         for (GroupsInDevice outputPath : trace.getGroupOuputs(in.deviceId())) {
 
             ConnectPoint cp = outputPath.getOutput();
+            log.debug("Connect point in {}", in);
             log.debug("Output path {}", cp);
 
             //Hosts for the the given output
@@ -160,7 +163,7 @@
 
             //If the two host collections contain the same item it means we reached the proper output
             if (!Collections.disjoint(hostsList, hosts)) {
-                log.debug("Stopping here because host is expected destination");
+                log.debug("Stopping here because host is expected destination {}, reached through", completePath);
                 trace.addResultMessage("Reached required destination Host " + cp);
                 computePath(completePath, trace, outputPath.getOutput());
                 break;
@@ -182,10 +185,32 @@
                 computePath(completePath, trace, outputPath.getOutput());
 
             } else {
+
+                //TODO this can be optimized if we use a Tree structure for paths.
+                //if we already have outputs let's check if the one we are considering starts from one of the devices
+                // in any of the ones we have.
+                if (trace.getCompletePaths().size() > 0) {
+                    ConnectPoint inputForOutput = null;
+                    List<ConnectPoint> previousPath = new ArrayList<>();
+                    for (List<ConnectPoint> path : trace.getCompletePaths()) {
+                        for (ConnectPoint connect : path) {
+                            //if the path already contains the input for the output we've found we use it
+                            if (connect.equals(in)) {
+                                inputForOutput = connect;
+                                previousPath = path;
+                                break;
+                            }
+                        }
+                    }
+                    //we use the pre-existing path up to the point we fork to a new output
+                    if (inputForOutput != null && completePath.contains(inputForOutput)) {
+                        List<ConnectPoint> temp = new ArrayList<>(previousPath);
+                        completePath = temp.subList(0, previousPath.indexOf(inputForOutput) + 1);
+                    }
+                }
+
                 //let's add the ouput for the input
                 completePath.add(cp);
-                log.debug("------------------------------------------------------------");
-                log.debug("Connect Point out {}", cp);
                 //let's compute the links for the given output
                 Set<Link> links = linkService.getEgressLinks(cp);
                 log.debug("Egress Links {}", links);
@@ -274,7 +299,6 @@
             traverseList.add(output);
         }
         trace.addCompletePath(traverseList);
-        completePath.clear();
     }
 
     /**
@@ -286,6 +310,12 @@
      * @return updated trace
      */
     private StaticPacketTrace traceInDevice(StaticPacketTrace trace, TrafficSelector packet, ConnectPoint in) {
+
+        //we already traversed this device.
+        if (trace.getGroupOuputs(in.deviceId()) != null) {
+            log.debug("Trace already contains device and given outputs");
+            return trace;
+        }
         log.debug("Packet {} coming in from {}", packet, in);
 
         //if device is not available exit here.
diff --git a/src/test/java/org/onosproject/t3/impl/T3TestObjects.java b/src/test/java/org/onosproject/t3/impl/T3TestObjects.java
index 744b19b..5f6a7d9 100644
--- a/src/test/java/org/onosproject/t3/impl/T3TestObjects.java
+++ b/src/test/java/org/onosproject/t3/impl/T3TestObjects.java
@@ -344,6 +344,101 @@
 
     static final FlowEntry HARDWARE_ETH_FLOW_ENTRY = new DefaultFlowEntry(HARDWARE_ETH_FLOW);
 
+    //Dual Links
+    // - (1) Device 1 (2-3) - (1-4) Device 2 (2-3) - (1-2) Device 3 (3) -
+    static final DeviceId DUAL_LINK_1 = DeviceId.deviceId("DualLink1");
+    static final DeviceId DUAL_LINK_2 = DeviceId.deviceId("DualLink2");
+    static final DeviceId DUAL_LINK_3 = DeviceId.deviceId("DualLink3");
+
+    static final ConnectPoint DUAL_LINK_1_CP_1_IN = ConnectPoint.deviceConnectPoint(DUAL_LINK_1 + "/" + 1);
+    static final ConnectPoint DUAL_LINK_1_CP_2_OUT = ConnectPoint.deviceConnectPoint(DUAL_LINK_1 + "/" + 2);
+    static final ConnectPoint DUAL_LINK_1_CP_3_OUT = ConnectPoint.deviceConnectPoint(DUAL_LINK_1 + "/" + 3);
+    static final ConnectPoint DUAL_LINK_2_CP_1_IN = ConnectPoint.deviceConnectPoint(DUAL_LINK_2 + "/" + 1);
+    static final ConnectPoint DUAL_LINK_2_CP_4_IN = ConnectPoint.deviceConnectPoint(DUAL_LINK_2 + "/" + 4);
+    static final ConnectPoint DUAL_LINK_2_CP_2_OUT = ConnectPoint.deviceConnectPoint(DUAL_LINK_2 + "/" + 2);
+    static final ConnectPoint DUAL_LINK_2_CP_3_OUT = ConnectPoint.deviceConnectPoint(DUAL_LINK_2 + "/" + 3);
+    static final ConnectPoint DUAL_LINK_3_CP_1_IN = ConnectPoint.deviceConnectPoint(DUAL_LINK_3 + "/" + 1);
+    static final ConnectPoint DUAL_LINK_3_CP_2_IN = ConnectPoint.deviceConnectPoint(DUAL_LINK_3 + "/" + 2);
+    static final ConnectPoint DUAL_LINK_3_CP_3_OUT = ConnectPoint.deviceConnectPoint(DUAL_LINK_3 + "/" + 3);
+
+    //match on port 1 and point to group for device 1 and 2
+    private static final TrafficTreatment DUAL_LINK_1_GROUP_FLOW_TREATMENT = DefaultTrafficTreatment.builder()
+            .pushMpls()
+            .setMpls(MplsLabel.mplsLabel(100))
+            .group(GROUP_ID)
+            .build();
+    private static final FlowRule DUAL_LINK_1_GROUP_FLOW = DefaultFlowEntry.builder().forDevice(DUAL_LINK_1)
+            .forTable(0)
+            .withPriority(100)
+            .withSelector(SINGLE_FLOW_SELECTOR)
+            .withTreatment(DUAL_LINK_1_GROUP_FLOW_TREATMENT)
+            .fromApp(new DefaultApplicationId(0, "TestApp"))
+            .makePermanent()
+            .build();
+    static final FlowEntry DUAL_LINK_1_GROUP_FLOW_ENTRY = new DefaultFlowEntry(DUAL_LINK_1_GROUP_FLOW);
+
+    //Match on port 4 and point to group for device 2
+    private static final TrafficSelector DUAL_LINK_2_FLOW_SELECTOR = DefaultTrafficSelector.builder()
+            .matchInPort(PortNumber.portNumber(4))
+            .matchIPSrc(IpPrefix.valueOf("127.0.0.1/32"))
+            .matchIPDst(IpPrefix.valueOf("127.0.0.2/32"))
+            .build();
+
+    private static final FlowRule DUAL_LINK_2_GROUP_FLOW = DefaultFlowEntry.builder().forDevice(DUAL_LINK_2)
+            .forTable(0)
+            .withPriority(100)
+            .withSelector(DUAL_LINK_2_FLOW_SELECTOR)
+            .withTreatment(DUAL_LINK_1_GROUP_FLOW_TREATMENT)
+            .fromApp(new DefaultApplicationId(0, "TestApp"))
+            .makePermanent()
+            .build();
+    static final FlowEntry DUAL_LINK_2_GROUP_FLOW_ENTRY = new DefaultFlowEntry(DUAL_LINK_2_GROUP_FLOW);
+
+    //Flows for device 3 to ouput on port 3
+    private static final TrafficTreatment DUAL_LINK_1_OUTPUT_TREATMENT = DefaultTrafficTreatment.builder()
+            .popMpls(EthType.EtherType.IPV4.ethType())
+            .setOutput(PortNumber.portNumber(3)).build();
+
+    private static final TrafficSelector DUAL_LINK_3_FLOW_SELECTOR_1 = DefaultTrafficSelector.builder()
+            .matchInPort(PortNumber.portNumber(1))
+            .matchIPSrc(IpPrefix.valueOf("127.0.0.1/32"))
+            .matchIPDst(IpPrefix.valueOf("127.0.0.2/32"))
+            .build();
+    private static final FlowRule DUAL_LINK_3_FLOW_1 = DefaultFlowEntry.builder().forDevice(DUAL_LINK_3)
+            .forTable(0)
+            .withPriority(100)
+            .withSelector(DUAL_LINK_3_FLOW_SELECTOR_1)
+            .withTreatment(DUAL_LINK_1_OUTPUT_TREATMENT)
+            .fromApp(new DefaultApplicationId(0, "TestApp"))
+            .makePermanent()
+            .build();
+
+    static final FlowEntry DUAL_LINK_3_FLOW_ENTRY = new DefaultFlowEntry(DUAL_LINK_3_FLOW_1);
+
+    private static final TrafficSelector DUAL_LINK_3_FLOW_SELECTOR_2 = DefaultTrafficSelector.builder()
+            .matchInPort(PortNumber.portNumber(2))
+            .matchIPSrc(IpPrefix.valueOf("127.0.0.1/32"))
+            .matchIPDst(IpPrefix.valueOf("127.0.0.2/32"))
+            .build();
+    private static final FlowRule DUAL_LINK_3_FLOW_2 = DefaultFlowEntry.builder().forDevice(DUAL_LINK_3)
+            .forTable(0)
+            .withPriority(100)
+            .withSelector(DUAL_LINK_3_FLOW_SELECTOR_2)
+            .withTreatment(DUAL_LINK_1_OUTPUT_TREATMENT)
+            .fromApp(new DefaultApplicationId(0, "TestApp"))
+            .makePermanent()
+            .build();
+
+    static final FlowEntry DUAL_LINK_3_FLOW_ENTRY_2 = new DefaultFlowEntry(DUAL_LINK_3_FLOW_2);
+
+    //Group with two buckets to output on port 2 and 3 of device 1 and 2
+
+    private static final GroupBucket BUCKET_2_DUAL =
+            DefaultGroupBucket.createSelectGroupBucket(DUAL_LINK_1_OUTPUT_TREATMENT);
+
+    private static final GroupBuckets BUCKETS_DUAL = new GroupBuckets(ImmutableList.of(BUCKET, BUCKET_2_DUAL));
+
+    static final Group DUAL_LINK_GROUP = new DefaultGroup(GROUP_ID, DUAL_LINK_1, Group.Type.SELECT, BUCKETS_DUAL);
 
     //helper elements
 
diff --git a/src/test/java/org/onosproject/t3/impl/TroubleshootManagerTest.java b/src/test/java/org/onosproject/t3/impl/TroubleshootManagerTest.java
index 7ca5136..d7d3f33 100644
--- a/src/test/java/org/onosproject/t3/impl/TroubleshootManagerTest.java
+++ b/src/test/java/org/onosproject/t3/impl/TroubleshootManagerTest.java
@@ -158,9 +158,9 @@
     @Test
     public void testSingleFlowRule() {
 
-        testSuccess(PACKET_OK, SINGLE_FLOW_IN_CP, SINGLE_FLOW_DEVICE, SINGLE_FLOW_OUT_CP, 1);
+        testSuccess(PACKET_OK, SINGLE_FLOW_IN_CP, SINGLE_FLOW_DEVICE, SINGLE_FLOW_OUT_CP, 1, 1);
 
-        testFaliure(PACKET_FAIL, SINGLE_FLOW_IN_CP, SINGLE_FLOW_DEVICE);
+        testFailure(PACKET_FAIL, SINGLE_FLOW_IN_CP, SINGLE_FLOW_DEVICE);
     }
 
     /**
@@ -172,7 +172,7 @@
         //Test Success
 
         StaticPacketTrace traceSuccess = testSuccess(PACKET_OK, DUAL_FLOW_IN_CP, DUAL_FLOW_DEVICE,
-                DUAL_FLOW_OUT_CP, 1);
+                DUAL_FLOW_OUT_CP, 1, 1);
 
         //Testing Vlan
         Criterion criterion = traceSuccess.getGroupOuputs(DUAL_FLOW_DEVICE).get(0).
@@ -184,7 +184,7 @@
         assertEquals("Vlan should be 100", VlanId.vlanId((short) 100), vlanIdCriterion.vlanId());
 
         //Test Faliure
-        testFaliure(PACKET_FAIL, DUAL_FLOW_IN_CP, DUAL_FLOW_DEVICE);
+        testFailure(PACKET_FAIL, DUAL_FLOW_IN_CP, DUAL_FLOW_DEVICE);
 
     }
 
@@ -195,7 +195,7 @@
     public void flowAndGroup() throws Exception {
 
         StaticPacketTrace traceSuccess = testSuccess(PACKET_OK, GROUP_FLOW_IN_CP, GROUP_FLOW_DEVICE,
-                GROUP_FLOW_OUT_CP, 1);
+                GROUP_FLOW_OUT_CP, 1, 1);
 
         assertTrue("Wrong Output Group", traceSuccess.getGroupOuputs(GROUP_FLOW_DEVICE)
                 .get(0).getGroups().contains(GROUP));
@@ -216,7 +216,7 @@
     public void singlePathTopology() throws Exception {
 
         StaticPacketTrace traceSuccess = testSuccess(PACKET_OK_TOPO, TOPO_FLOW_1_IN_CP,
-                TOPO_FLOW_3_DEVICE, TOPO_FLOW_3_OUT_CP, 1);
+                TOPO_FLOW_3_DEVICE, TOPO_FLOW_3_OUT_CP, 1, 1);
 
         assertTrue("Incorrect path",
                 traceSuccess.getCompletePaths().get(0).contains(TOPO_FLOW_2_IN_CP));
@@ -234,7 +234,9 @@
     public void testGroupTopo() throws Exception {
 
         StaticPacketTrace traceSuccess = testSuccess(PACKET_OK_TOPO, TOPO_FLOW_IN_CP,
-                TOPO_FLOW_3_DEVICE, TOPO_FLOW_3_OUT_CP, 2);
+                TOPO_FLOW_3_DEVICE, TOPO_FLOW_3_OUT_CP, 2, 1);
+
+        log.info("{}", traceSuccess);
 
         assertTrue("Incorrect groups",
                 traceSuccess.getGroupOuputs(TOPO_GROUP_FLOW_DEVICE).get(0).getGroups().contains(TOPO_GROUP));
@@ -249,7 +251,7 @@
     public void hardwareTest() throws Exception {
 
         StaticPacketTrace traceSuccess = testSuccess(PACKET_OK, HARDWARE_DEVICE_IN_CP,
-                HARDWARE_DEVICE, HARDWARE_DEVICE_OUT_CP, 1);
+                HARDWARE_DEVICE, HARDWARE_DEVICE_OUT_CP, 1, 1);
 
         assertEquals("wrong ETH type", EthType.EtherType.IPV4.ethType(),
                 ((EthTypeCriterion) traceSuccess.getGroupOuputs(HARDWARE_DEVICE).get(0).getFinalPacket()
@@ -257,8 +259,21 @@
 
     }
 
+    /**
+     * Test dual links between 3 topology elements.
+     */
+    @Test
+    public void dualLinks() throws Exception {
+
+        StaticPacketTrace traceSuccess = testSuccess(PACKET_OK, DUAL_LINK_1_CP_1_IN,
+                DUAL_LINK_3, DUAL_LINK_3_CP_3_OUT, 4, 1);
+
+        //TODO tests
+
+    }
+
     private StaticPacketTrace testSuccess(TrafficSelector packet, ConnectPoint in, DeviceId deviceId, ConnectPoint out,
-                                          int paths) {
+                                          int paths, int outputs) {
         StaticPacketTrace traceSuccess = mngr.trace(packet, in);
 
         log.info("trace {}", traceSuccess);
@@ -266,7 +281,8 @@
         log.info("trace {}", traceSuccess.resultMessage());
 
         assertNotNull("trace should not be null", traceSuccess);
-        assertEquals("Trace should have " + paths + " output", paths, traceSuccess.getGroupOuputs(deviceId).size());
+        assertEquals("Trace should have " + outputs + " output", outputs,
+                traceSuccess.getGroupOuputs(deviceId).size());
         assertEquals("Trace should only have " + paths + "output", paths, traceSuccess.getCompletePaths().size());
         assertTrue("Trace should be successful",
                 traceSuccess.resultMessage().contains("Reached required destination Host"));
@@ -276,7 +292,7 @@
         return traceSuccess;
     }
 
-    private void testFaliure(TrafficSelector packet, ConnectPoint in, DeviceId deviceId) {
+    private void testFailure(TrafficSelector packet, ConnectPoint in, DeviceId deviceId) {
         StaticPacketTrace traceFail = mngr.trace(packet, in);
 
         log.info("trace {}", traceFail.resultMessage());
@@ -307,6 +323,12 @@
                 return ImmutableList.of(SAME_OUTPUT_FLOW_ENTRY);
             } else if (deviceId.equals(ARP_FLOW_DEVICE)) {
                 return ImmutableList.of(ARP_FLOW_ENTRY);
+            } else if (deviceId.equals(DUAL_LINK_1)) {
+                return ImmutableList.of(DUAL_LINK_1_GROUP_FLOW_ENTRY);
+            } else if (deviceId.equals(DUAL_LINK_2)) {
+                return ImmutableList.of(DUAL_LINK_1_GROUP_FLOW_ENTRY, DUAL_LINK_2_GROUP_FLOW_ENTRY);
+            } else if (deviceId.equals(DUAL_LINK_3)) {
+                return ImmutableList.of(DUAL_LINK_3_FLOW_ENTRY, DUAL_LINK_3_FLOW_ENTRY_2);
             }
             return ImmutableList.of();
         }
@@ -331,6 +353,8 @@
                 return ImmutableList.of(GROUP);
             } else if (deviceId.equals(TOPO_GROUP_FLOW_DEVICE)) {
                 return ImmutableList.of(TOPO_GROUP);
+            } else if (deviceId.equals(DUAL_LINK_1) || deviceId.equals(DUAL_LINK_2)) {
+                return ImmutableList.of(DUAL_LINK_GROUP);
             }
             return ImmutableList.of();
         }
@@ -341,6 +365,9 @@
         public Set<Host> getConnectedHosts(ConnectPoint connectPoint) {
             if (connectPoint.equals(TOPO_FLOW_3_OUT_CP)) {
                 return ImmutableSet.of(H2);
+            } else if (connectPoint.equals(DUAL_LINK_1_CP_2_OUT) || connectPoint.equals(DUAL_LINK_1_CP_3_OUT) ||
+                    connectPoint.equals(DUAL_LINK_2_CP_2_OUT) || connectPoint.equals(DUAL_LINK_2_CP_3_OUT)) {
+                return ImmutableSet.of();
             }
             return ImmutableSet.of(H1);
         }
@@ -398,6 +425,34 @@
                         .src(TOPO_FLOW_4_OUT_CP)
                         .dst(TOPO_FLOW_3_IN_2_CP)
                         .build());
+            } else if (connectPoint.equals(DUAL_LINK_1_CP_2_OUT)) {
+                return ImmutableSet.of(DefaultLink.builder()
+                        .providerId(ProviderId.NONE)
+                        .type(Link.Type.DIRECT)
+                        .src(DUAL_LINK_1_CP_2_OUT)
+                        .dst(DUAL_LINK_2_CP_1_IN)
+                        .build());
+            } else if (connectPoint.equals(DUAL_LINK_1_CP_3_OUT)) {
+                return ImmutableSet.of(DefaultLink.builder()
+                        .providerId(ProviderId.NONE)
+                        .type(Link.Type.DIRECT)
+                        .src(DUAL_LINK_1_CP_3_OUT)
+                        .dst(DUAL_LINK_2_CP_4_IN)
+                        .build());
+            } else if (connectPoint.equals(DUAL_LINK_2_CP_2_OUT)) {
+                return ImmutableSet.of(DefaultLink.builder()
+                        .providerId(ProviderId.NONE)
+                        .type(Link.Type.DIRECT)
+                        .src(DUAL_LINK_2_CP_2_OUT)
+                        .dst(DUAL_LINK_3_CP_1_IN)
+                        .build());
+            } else if (connectPoint.equals(DUAL_LINK_2_CP_3_OUT)) {
+                return ImmutableSet.of(DefaultLink.builder()
+                        .providerId(ProviderId.NONE)
+                        .type(Link.Type.DIRECT)
+                        .src(DUAL_LINK_2_CP_3_OUT)
+                        .dst(DUAL_LINK_3_CP_2_IN)
+                        .build());
             }
             return ImmutableSet.of();
         }