4 files changed, 189 insertions, 3 deletions
diff --git a/test/example/space.cpp b/test/example/space.cpp
new file mode 100644
index 000000000..33256eedf
--- /dev/null
+++ b/test/example/space.cpp
@@ -0,0 +1,115 @@
+#include <cassert>
+#include <iostream>
+
+#include <support/space.h>
+
+using namespace wasm;
+
+using Span = DisjointSpans::Span;
+
+int main() {
+  // No spans
+  {
+    DisjointSpans root;
+    // Nothing in root
+    assert(!root.checkOverlap(Span{0, 100}));
+  }
+  // One span
+  {
+    DisjointSpans root;
+    root.add(Span{0, 100});
+    // It is there
+    assert(root.checkOverlap(Span{0, 100}));
+  }
+  {
+    DisjointSpans root;
+    root.add(Span{40, 60});
+    // Exact match
+    assert(root.checkOverlap(Span{40, 60}));
+    // No overlap
+    assert(!root.checkOverlap(Span{20, 30}));
+    // Touching, but no overlap
+    assert(!root.checkOverlap(Span{20, 40}));
+    // Overlap
+    assert(root.checkOverlap(Span{20, 41}));
+    assert(root.checkOverlap(Span{40, 41}));
+    // Internal
+    assert(root.checkOverlap(Span{45, 50}));
+    // Touches other side
+    assert(root.checkOverlap(Span{45, 60}));
+    // Overlaps on other side
+    assert(root.checkOverlap(Span{45, 70}));
+    // Just inside.
+    assert(root.checkOverlap(Span{59, 60}));
+    // Just outside
+    assert(!root.checkOverlap(Span{60, 61}));
+    // Totally outside
+    assert(!root.checkOverlap(Span{70, 80}));
+  }
+  // Two spans, different subtrees
+  {
+    DisjointSpans root;
+    root.add(Span{30, 40});
+    root.add(Span{60, 70});
+    assert(!root.checkOverlap(Span{10, 20}));
+    assert(!root.checkOverlap(Span{10, 30}));
+    assert(root.checkOverlap(Span{10, 40}));
+    assert(root.checkOverlap(Span{35, 40}));
+    assert(!root.checkOverlap(Span{40, 60}));
+    assert(!root.checkOverlap(Span{45, 55}));
+    assert(root.checkOverlap(Span{50, 61}));
+    assert(root.checkOverlap(Span{50, 100}));
+    assert(root.checkOverlap(Span{60, 70}));
+    assert(root.checkOverlap(Span{60, 61}));
+    assert(!root.checkOverlap(Span{70, 80}));
+    assert(!root.checkOverlap(Span{70, 100}));
+  }
+  // Two spans, same subtree
+  {
+    DisjointSpans root;
+    root.add(Span{30, 40});
+    root.add(Span{40, 45});
+    assert(!root.checkOverlap(Span{10, 20}));
+    assert(!root.checkOverlap(Span{10, 30}));
+    assert(root.checkOverlap(Span{10, 40}));
+    assert(root.checkOverlap(Span{35, 40}));
+    assert(root.checkOverlap(Span{40, 41}));
+    assert(root.checkOverlap(Span{35, 45}));
+    assert(!root.checkOverlap(Span{45, 100}));
+  }
+  // "Pixels"
+  {
+    const int N = 40;
+    for (int i = 0; i < N; i++) {
+      DisjointSpans root;
+      for (int j = 0; j < N; j++) {
+        // add all pixels but the i-th
+        if (j != i) {
+          root.add(Span{j, j + 1});
+        }
+      }
+      for (int j = 0; j < N; j++) {
+        if (j != i) {
+          assert(root.checkOverlap(Span{j, j + 1}));
+        } else {
+          assert(!root.checkOverlap(Span{j, j + 1}));
+        }
+      }
+      assert(root.checkOverlap(Span{10, N + 10}));
+      assert(!root.checkOverlap(Span{N + 10, N + 20}));
+    }
+  }
+  // Large numbers.
+  {
+    DisjointSpans root;
+    assert(!root.checkOverlap(Span{2948, 2949}));
+    root.add(Span{2948, 2949});
+    assert(root.checkOverlap(Span{2948, 2949}));
+    assert(root.checkOverlap(Span{2940, 2949}));
+    assert(root.checkOverlap(Span{2948, 2959}));
+    assert(root.checkOverlap(Span{0, 18766}));
+    assert(!root.checkOverlap(Span{2000, 2001}));
+    assert(!root.checkOverlap(Span{3000, 3001}));
+  }
+  std::cout << "success.\n";
+}
diff --git a/test/example/space.txt b/test/example/space.txt
new file mode 100644
index 000000000..b32bb74d2
--- /dev/null
+++ b/test/example/space.txt
@@ -0,0 +1 @@
+success.
diff --git a/test/passes/memory-packing_all-features.txt b/test/passes/memory-packing_all-features.txt
index bc9139f74..2d183860c 100644
--- a/test/passes/memory-packing_all-features.txt
+++ b/test/passes/memory-packing_all-features.txt
@@ -7,9 +7,13 @@
  (import "env" "memoryBase" (global $memoryBase i32))
 )
 (module
- (type $none_=>_none (func))
  (import "env" "memory" (memory $0 2048 2048))
  (data (global.get $memoryBase) "waka this cannot be optimized\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00we don\'t know where it will go")
+ (import "env" "memoryBase" (global $memoryBase i32))
+)
+(module
+ (type $none_=>_none (func))
+ (memory $0 1 1)
  (data (i32.const 1024) "waka this CAN be optimized")
  (data (i32.const 1107) "we DO know where it will go")
  (data (i32.const 2057) "zeros before")
@@ -17,7 +21,6 @@
  (data (i32.const 4000) "zeros\00in\00the\00middle")
  (data (i32.const 4035) "nice skip here")
  (data (i32.const 4066) "another\00but no")
- (import "env" "memoryBase" (global $memoryBase i32))
  (func $nonzero-size-init-of-active-will-trap
   (block
    (drop
@@ -1506,6 +1509,37 @@
  )
 )
 (module
+ (memory $0 1 1)
+ (data (i32.const 1024) "x")
+ (data (i32.const 1024) "\00")
+)
+(module
+ (memory $0 1 1)
+ (data (i32.const 1024) "x")
+)
+(module
+ (memory $0 1 1)
+ (data (i32.const 1024) "x")
+)
+(module
+ (memory $0 1 1)
+ (data (i32.const 1024) "x")
+ (data (i32.const 1024) "\00")
+ (data (i32.const 4096) "\00")
+)
+(module
+ (import "env" "memory" (memory $0 1 1))
+ (data (i32.const 1024) "x")
+ (data (global.get $memoryBase) "\00")
+ (import "env" "memoryBase" (global $memoryBase i32))
+)
+(module
+ (import "env" "memory" (memory $0 1 1))
+ (data (i32.const 1024) "\00")
+ (data (global.get $memoryBase) "x")
+ (import "env" "memoryBase" (global $memoryBase i32))
+)
+(module
  (type $none_=>_none (func))
  (import "env" "memory" (memory $mimport$0 1 1))
  (data passive "skipped")
diff --git a/test/passes/memory-packing_all-features.wast b/test/passes/memory-packing_all-features.wast
index 3ee0bd5e7..9355c6dfa 100644
--- a/test/passes/memory-packing_all-features.wast
+++ b/test/passes/memory-packing_all-features.wast
@@ -15,6 +15,10 @@
   (import "env" "memoryBase" (global $memoryBase i32))
 
   (data (global.get $memoryBase) "waka this cannot be optimized\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00we don't know where it will go")
+)
+
+(module
+  (memory 1 1)
 
   (data (i32.const 1024) "waka this CAN be optimized\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00we DO know where it will go")
 
@@ -495,7 +499,39 @@
     (data.drop 0)
   )
 )
-
+(module
+ (memory $0 1 1)
+ (data (i32.const 1024) "x")
+ (data (i32.const 1024) "\00") ;; this tramples the "x", and so must be kept.
+)
+(module
+ (memory $0 1 1)
+ (data (i32.const 1024) "x")
+ (data (i32.const 1025) "\00")
+)
+(module
+ (memory $0 1 1)
+ (data (i32.const 1024) "x")
+ (data (i32.const 1023) "\00")
+)
+(module
+ (memory $0 1 1)
+ (data (i32.const 1024) "x")
+ (data (i32.const 1024) "\00") ;; when we see one bad thing, we give up
+ (data (i32.const 4096) "\00")
+)
+(module
+ (import "env" "memory" (memory $0 1 1))
+ (import "env" "memoryBase" (global $memoryBase i32))
+ (data (i32.const 1024) "x")
+ (data (global.get $memoryBase) "\00") ;; this could trample, or not
+)
+(module
+ (import "env" "memory" (memory $0 1 1))
+ (import "env" "memoryBase" (global $memoryBase i32))
+ (data (i32.const 1024) "\00") ;; this could trample, or not
+ (data (global.get $memoryBase) "x")
+)
 (module
  (import "env" "memory" (memory 1 1))
  (data passive "skipped\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00included")