Attachment 200895 Details for Bug 353605 – Patch to add proper merging support, tests on this, use it and bug fixes

Some Eclipse Foundation services are deprecated, or will be soon. Please ensure you've read this important communication.

[patch] Patch to add proper merging support, tests on this, use it and bug fixes

353605-rangelist.patch (text/plain), 14.81 KB, created by Daniel Thomas

on 2011-08-04 05:46:46 EDT

(hide)

Description:

Filename:

MIME Type:

Creator: Daniel Thomas

Created: 2011-08-04 05:46:46 EDT

Size: 14.81 KB

patch

obsolete

>From 9b6b6c994e48e5fba99aba0c22f9b2d342aa6d84 Mon Sep 17 00:00:00 2001
>From: thomasd <thomasd@broadcom.com>
>Date: Mon, 25 Jul 2011 10:51:15 +0100
>Subject: [PATCH 1/4] Do proper merging of rangelists
>
>Signed-off-by: Daniel Thomas <thomasd@broadcom.com>
>---
> .../cdt/debug/edc/internal/symbols/Scope.java      |   17 ++++--
> .../edc/internal/symbols/dwarf/RangeList.java      |   53 ++++++++++++++++++++
> 2 files changed, 64 insertions(+), 6 deletions(-)
>
>diff --git a/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/Scope.java b/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/Scope.java
>index d404c3d..af4cace 100644
>--- a/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/Scope.java
>+++ b/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/Scope.java
>@@ -69,7 +69,7 @@ public abstract class Scope implements IScope {
> 		return (lowAddress == null || highAddress == null)
> 		|| (lowAddress.isZero() && highAddress.isZero())
> 		|| (lowAddress.getValue().longValue() == -1 && highAddress.isZero()); // TODO: remove this case
>-	}
>+	}//FIXME: looks like a bug: no test that lowAddress.equals(highAddress)
> 
> 	/**
> 	 * Return the list of non-contiguous ranges for this scope.
>@@ -244,6 +244,13 @@ public abstract class Scope implements IScope {
> 			}
> 			
> 			if (kid.getLowAddress().compareTo(baseAddress) > 0) {
>+				IRangeList kidRanges = kid.getRangeList();
>+				if (kidRanges == null){// If it didn't have ranges it still has one range
>+					kidRanges = new RangeList();
>+					((RangeList)kidRanges).addRange(kid.getLowAddress().getValue().longValue(),kid.getHighAddress().getValue().longValue());
>+				}
>+				newRangeList = RangeList.mergeRangeLists(newRangeList,kidRanges);
>+
> 				if (kid.getLowAddress().compareTo(newLowAddress) < 0) {
> 					newLowAddress = kid.getLowAddress();
> 					any = true;
>@@ -287,8 +294,7 @@ public abstract class Scope implements IScope {
> 			{
> 				if (rangeList != null) {
> 					if (scope.getRangeList() != null) {
>-						// TODO: merge properly
>-						rangeList = null;
>+						rangeList = RangeList.mergeRangeLists(rangeList,scope.getRangeList());
> 					} else {
> 						((RangeList)rangeList).addLowRange(scope.getLowAddress().getValue().longValue());
> 					}
>@@ -298,8 +304,7 @@ public abstract class Scope implements IScope {
> 			if (scope.getHighAddress() != null && scope.getHighAddress().compareTo(highAddress) > 0) {
> 				if (rangeList != null) {
> 					if (scope.getRangeList() != null) {
>-						// TODO: merge properly
>-						rangeList = null;
>+						rangeList = RangeList.mergeRangeLists(rangeList,scope.getRangeList());
> 					} else {
> 						((RangeList)rangeList).addHighRange(scope.getHighAddress().getValue().longValue());
> 					}
>@@ -308,7 +313,7 @@ public abstract class Scope implements IScope {
> 			}	
> 		}
> 	}
>-	
>+
> 	protected void addLineInfoToParent(IScope scope) {
> 		IScope cu = parent;
> 		while (cu != null) {
>diff --git a/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/dwarf/RangeList.java b/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/dwarf/RangeList.java
>index 51f77c4..bee4875 100644
>--- a/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/dwarf/RangeList.java
>+++ b/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/dwarf/RangeList.java
>@@ -129,4 +129,57 @@ public class RangeList implements IRangeList {
> 		}
> 		return false;
> 	}
>+
>+	public static RangeList mergeRangeLists(IRangeList first, IRangeList second){
>+		Iterator<IRangeList.Entry> firstIterator = first.iterator();
>+		Iterator<IRangeList.Entry> secondIterator = second.iterator();
>+		RangeList answer = new RangeList();
>+		IRangeList.Entry firstHead = null;
>+		IRangeList.Entry secondHead = null;
>+		while (firstIterator.hasNext() || secondIterator.hasNext()
>+				|| firstHead != null || secondHead != null){
>+			if (firstHead == null && firstIterator.hasNext()){
>+				firstHead = firstIterator.next();
>+			}
>+			if (secondHead == null && secondIterator.hasNext()){
>+				secondHead = secondIterator.next();
>+			}
>+			if (firstHead == null){
>+				if (secondHead != null){
>+					answer.addRange(secondHead.low, secondHead.high);
>+					secondHead = null;
>+				}// else we have no more work to do and will exit at the end of the loop
>+			} else {
>+				if (secondHead == null){
>+					answer.addRange(firstHead.low,firstHead.high);
>+					firstHead = null;
>+				} else {// both not null so work to do
>+					long low,high;
>+					if (firstHead.low <= secondHead.low){
>+						low = firstHead.low;
>+						if (firstHead.high < secondHead.low){// we are just using firstHead
>+							high = firstHead.high;
>+							firstHead = null;
>+						} else {// overlap so use both
>+							high = Math.max(firstHead.high, secondHead.high);
>+							firstHead = null;
>+							secondHead = null;
>+						}
>+					} else {
>+						low = secondHead.low;
>+						if (secondHead.high < firstHead.low){// just using secondHead
>+							high = secondHead.high;
>+							secondHead = null;
>+						} else { // overlap so use both
>+							high = Math.max(firstHead.high, secondHead.high);
>+							firstHead = null;
>+							secondHead = null;
>+						}
>+					}
>+					answer.addRange(low,high);
>+				}
>+			}
>+		}
>+		return answer;
>+	}
> }
>\ No newline at end of file
>-- 
>1.7.0.2
>
>From 714b1123c0b5b45c92484f92ddf3c9386b0b5c54 Mon Sep 17 00:00:00 2001
>From: Daniel Thomas <thomasd@broadcom.com>
>Date: Wed, 3 Aug 2011 17:20:58 +0100
>Subject: [PATCH 2/4] Add tests on RangeList and fix bug in isInRange
>
>>= being used where <= was meant
>
>Signed-off-by: Daniel Thomas <thomasd@broadcom.com>
>---
> .../cdt/debug/edc/symbols/tests/TestRangeList.java |   92 ++++++++++++++++++++
> .../eclipse/cdt/debug/edc/tests/AllEDCTests.java   |    2 +
> .../edc/internal/symbols/dwarf/RangeList.java      |    2 +-
> 3 files changed, 95 insertions(+), 1 deletions(-)
> create mode 100644 org.eclipse.cdt.debug.edc.tests/src/org/eclipse/cdt/debug/edc/symbols/tests/TestRangeList.java
>
>diff --git a/org.eclipse.cdt.debug.edc.tests/src/org/eclipse/cdt/debug/edc/symbols/tests/TestRangeList.java b/org.eclipse.cdt.debug.edc.tests/src/org/eclipse/cdt/debug/edc/symbols/tests/TestRangeList.java
>new file mode 100644
>index 0000000..fb2ad6c
>--- /dev/null
>+++ b/org.eclipse.cdt.debug.edc.tests/src/org/eclipse/cdt/debug/edc/symbols/tests/TestRangeList.java
>@@ -0,0 +1,92 @@
>+/*******************************************************************************
>+ * Copyright (c) 2011 Broadcom and others.
>+ * All rights reserved. This program and the accompanying materials
>+ * are made available under the terms of the Eclipse Public License v1.0
>+ * which accompanies this distribution, and is available at
>+ * http://www.eclipse.org/legal/epl-v10.html
>+ *
>+ * Contributors:
>+ * Broadcom - Initial API and implementation
>+ *******************************************************************************/
>+package org.eclipse.cdt.debug.edc.symbols.tests;
>+
>+import static org.junit.Assert.assertEquals;
>+import static org.junit.Assert.assertFalse;
>+
>+import java.util.Iterator;
>+
>+import org.eclipse.cdt.debug.edc.internal.symbols.dwarf.RangeList;
>+import org.eclipse.cdt.debug.edc.symbols.IRangeList;
>+import org.eclipse.cdt.debug.edc.symbols.IRangeList.Entry;
>+import org.junit.BeforeClass;
>+import org.junit.Test;
>+
>+public class TestRangeList {
>+
>+	private static RangeList first;
>+	private static int low;
>+	private static int high;
>+	private static RangeList second;
>+	private static RangeList expectedMerged;
>+
>+	@BeforeClass
>+	public static void init(){
>+		low = 0;
>+		high = 120;
>+		first = new RangeList();
>+		first.addRange(low,10);
>+		first.addRange(25,32);
>+		first.addRange(60,68);
>+		first.addRange(107,high);
>+
>+		second = new RangeList();
>+		second.addRange(7,18);
>+		second.addRange(32,35);
>+		second.addRange(52,60);
>+		second.addRange(75,80);
>+		second.addRange(93,high);
>+
>+		expectedMerged = new RangeList();
>+		expectedMerged.addRange(low,18);
>+		expectedMerged.addRange(25,35);
>+		expectedMerged.addRange(52,68);
>+		expectedMerged.addRange(75,80);
>+		expectedMerged.addRange(93,high);
>+	}
>+
>+	@Test
>+	public void lowHigh(){
>+		assertEquals(low,first.getLowAddress());
>+		assertEquals(high,first.getHighAddress());
>+
>+		assertEquals(low,expectedMerged.getLowAddress());
>+		assertEquals(high,expectedMerged.getHighAddress());
>+	}
>+
>+	@Test
>+	public void merge(){
>+		IRangeList merged = RangeList.mergeRangeLists(first, second);
>+		Iterator<Entry> mergedIter = merged.iterator();
>+		Iterator<Entry> expectedIter = expectedMerged.iterator();
>+		while (mergedIter.hasNext() && expectedIter.hasNext()){
>+			assertEquals("Entries should be equal",expectedIter.next(),mergedIter.next());
>+		}
>+		assertFalse("Should be finished",mergedIter.hasNext());
>+		assertFalse("Should be finished",expectedIter.hasNext());
>+	}
>+
>+	@Test
>+	public void isInRange(){
>+		checkInRange(7,true,true,true);
>+		checkInRange(8,true,true,true);
>+		checkInRange(10,false,true,true);
>+		checkInRange(20,false,false,false);
>+		checkInRange(60,true,false,true);
>+	}
>+
>+	private void checkInRange(int point, boolean inFirst, boolean inSecond, boolean inExpectedMerged) {
>+		assertEquals(inFirst,first.isInRange(point));
>+		assertEquals(inSecond,second.isInRange(point));
>+		assertEquals(inExpectedMerged,expectedMerged.isInRange(point));
>+	}
>+}
>diff --git a/org.eclipse.cdt.debug.edc.tests/src/org/eclipse/cdt/debug/edc/tests/AllEDCTests.java b/org.eclipse.cdt.debug.edc.tests/src/org/eclipse/cdt/debug/edc/tests/AllEDCTests.java
>index be525db..42c4da7 100644
>--- a/org.eclipse.cdt.debug.edc.tests/src/org/eclipse/cdt/debug/edc/tests/AllEDCTests.java
>+++ b/org.eclipse.cdt.debug.edc.tests/src/org/eclipse/cdt/debug/edc/tests/AllEDCTests.java
>@@ -24,6 +24,7 @@ import org.eclipse.cdt.debug.edc.debugger.tests.RegisterFrameTestsBlackFlagRVCT;
> import org.eclipse.cdt.debug.edc.debugger.tests.RegisterFrameTestsLinux;
> import org.eclipse.cdt.debug.edc.debugger.tests.RegisterView;
> import org.eclipse.cdt.debug.edc.debugger.tests.SnapshotTests;
>+import org.eclipse.cdt.debug.edc.symbols.tests.TestRangeList;
> import org.eclipse.cdt.debug.edc.system.tests.K9SystemViewTest;
> import org.junit.runner.RunWith;
> import org.junit.runners.Suite;
>@@ -59,6 +60,7 @@ import org.junit.runners.Suite;
> 	TestFindCodeLine.class,
> 	TestMemoryStreamBuffer.class,
> 	TestOpcodeARM.class,
>+	TestRangeList.class,
> 	TestSourceToAddressMapping.class,
> 	TestUnmanglerEABI.class,
> })
>diff --git a/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/dwarf/RangeList.java b/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/dwarf/RangeList.java
>index bee4875..78374c1 100644
>--- a/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/dwarf/RangeList.java
>+++ b/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/dwarf/RangeList.java
>@@ -124,7 +124,7 @@ public class RangeList implements IRangeList {
> 	 */
> 	public boolean isInRange(long addr) {
> 		for (Entry entry : this) {
>-			if (entry.low >= addr && addr < entry.high)
>+			if (entry.low <= addr && addr < entry.high)
> 				return true;
> 		}
> 		return false;
>-- 
>1.7.0.2
>
>From f90761c5ffa3f38be1a7431af50d8580d58d146c Mon Sep 17 00:00:00 2001
>From: thomasd <thomasd@broadcom.com>
>Date: Tue, 26 Jul 2011 09:17:41 +0100
>Subject: [PATCH 3/4] Fixup rangelist information when fixing up low an high addresses
>
>So that the rangelist is not erroneously null when the low and high addresses
>have been fixed so that they are no longer both 0.
>
>Signed-off-by: Daniel Thomas <thomasd@broadcom.com>
>---
> .../cdt/debug/edc/internal/symbols/Scope.java      |    9 +++++++--
> 1 files changed, 7 insertions(+), 2 deletions(-)
>
>diff --git a/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/Scope.java b/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/Scope.java
>index af4cace..0b5a7ce 100644
>--- a/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/Scope.java
>+++ b/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/Scope.java
>@@ -232,6 +232,7 @@ public abstract class Scope implements IScope {
> 		// figure it out from the functions
> 		IAddress newLowAddress = Addr64.MAX;
> 		IAddress newHighAddress = Addr64.ZERO;
>+		IRangeList newRangeList = new RangeList();
> 		boolean any = false;
> 		
> 		for (IScope kid : getChildren()) {
>@@ -242,7 +243,7 @@ public abstract class Scope implements IScope {
> 			if (kid.hasEmptyRange()) {
> 				continue;
> 			}
>-			
>+
> 			if (kid.getLowAddress().compareTo(baseAddress) > 0) {
> 				IRangeList kidRanges = kid.getRangeList();
> 				if (kidRanges == null){// If it didn't have ranges it still has one range
>@@ -267,7 +268,11 @@ public abstract class Scope implements IScope {
> 			//System.out.println("Needed to fix up ranges for " + getName());
> 			lowAddress = newLowAddress; 
> 			highAddress = newHighAddress;
>-			rangeList = null;
>+			int entryCount = 0;
>+			for (@SuppressWarnings("unused") IRangeList.Entry entry : newRangeList){
>+				++entryCount;
>+			}
>+			rangeList = (entryCount > 1) ? newRangeList : null;
> 		} else {
> 			if (lowAddress == null) {
> 				lowAddress = highAddress = Addr32.ZERO;
>-- 
>1.7.0.2
>
>From 96dd2c3435eaf725e6403c25cdf2694154bb73fd Mon Sep 17 00:00:00 2001
>From: thomasd <thomasd@broadcom.com>
>Date: Tue, 26 Jul 2011 09:20:12 +0100
>Subject: [PATCH 4/4] Only return a non-null IRangeList in readRangeList if it is non-empty
>
>As null is used to represent a null IRangeList and returning a non-null empty
>one results in a zero length entry at 0x0.
>
>Signed-off-by: Daniel Thomas <thomasd@broadcom.com>
>---
> .../internal/symbols/dwarf/DwarfInfoReader.java    |    5 ++++-
> 1 files changed, 4 insertions(+), 1 deletions(-)
>
>diff --git a/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/dwarf/DwarfInfoReader.java b/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/dwarf/DwarfInfoReader.java
>index 087a197..dfb8b40 100644
>--- a/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/dwarf/DwarfInfoReader.java
>+++ b/org.eclipse.cdt.debug.edc/src/org/eclipse/cdt/debug/edc/internal/symbols/dwarf/DwarfInfoReader.java
>@@ -1915,6 +1915,8 @@ public class DwarfInfoReader {
> 				 */
> 	
> 				RangeList list = new RangeList();
>+				//Whether the list actually got anything added - otherwise we should return null
>+				boolean listAddedTo = false;
> 	
> 				long base = 0;
> 				long start = data.getInt();
>@@ -1937,6 +1939,7 @@ public class DwarfInfoReader {
> 						// ignore bogus entries: GCC-E sometimes generates these buggily (for artifical non-inlined functions)
> 						if (base + start >= codeRanges.getLowAddress()) {
> 							list.addRange(base + start, base + end);
>+							listAddedTo = true;
> 						}
> 					}
> 					start = data.getInt();
>@@ -1944,7 +1947,7 @@ public class DwarfInfoReader {
> 					
> 				} while (true);
> 				
>-				return list;
>+				return (listAddedTo) ? list : null;
> 				
> 			} catch (Throwable t) {
> 				EDCDebugger.getMessageLogger().logError(DwarfMessages.DwarfInfoReader_RangeReadFailed, t);
>-- 
>1.7.0.2
>

Actions: View | Diff

Attachments on bug 353605: 200731 | 200733 | 200895