[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnunet-scheme] 02/03: utils/bv-slice: Define ‘slice-independent’ proced
|
From: |
gnunet |
|
Subject: |
[gnunet-scheme] 02/03: utils/bv-slice: Define ‘slice-independent’ procedure. |
|
Date: |
Tue, 22 Feb 2022 20:36:45 +0100 |
This is an automated email from the git hooks/post-receive script.
maxime-devos pushed a commit to branch master
in repository gnunet-scheme.
commit d12032fee579669d4071795c2bf668c555461f20
Author: Maxime Devos <maximedevos@telenet.be>
AuthorDate: Tue Feb 22 10:42:40 2022 +0000
utils/bv-slice: Define ‘slice-independent’ procedure.
* gnu/gnunet/utils/bv-slice.scm (slice-independent?): New procedure.
* tests/bv-slice.scm (slice-independent?): Remove.
("empty slices are independent")
("empty slices are independent, even if using the same bytevector")
("empty slices are independent, even when using offsets (1)")
("empty slices are independent, even when using offsets (2)")
("empty slices are independent, even if eq?")
("slice-independent? is irreflexive (assuming non-empty) and ignores
capabilities (1)")
("slice-independent? is irreflexive (assuming non-empty) and ignores
capabilities (2)")
("empty slice is independent, even if inside the other slice")
("non-overlapping ranges are independent")
("overlapping ranges are dependent"): New tests.
---
gnu/gnunet/utils/bv-slice.scm | 21 ++++++++-
tests/bv-slice.scm | 93 ++++++++++++++++++++++++++++++++++++++--
tests/distributed-hash-table.scm | 3 --
3 files changed, 109 insertions(+), 8 deletions(-)
diff --git a/gnu/gnunet/utils/bv-slice.scm b/gnu/gnunet/utils/bv-slice.scm
index c8206a7..c171039 100644
--- a/gnu/gnunet/utils/bv-slice.scm
+++ b/gnu/gnunet/utils/bv-slice.scm
@@ -69,7 +69,9 @@
missing-capabilities-what
missing-capabilities-permitted
missing-capabilities-required
- CAP_READ CAP_WRITE)
+ CAP_READ CAP_WRITE
+
+ slice-independent?)
(import (rnrs arithmetic bitwise)
(rnrs base)
(rnrs bytevectors)
@@ -348,4 +350,19 @@ The slice @var{original} must be readable."
"Return a fresh read-only slice with the same contents as @var{original}.
Future modifications to @var{original} will not impact the returned slice.
THe slice @var{originall} must be readable."
- (slice/read-only (slice-copy/read-write original))))
+ (slice/read-only (slice-copy/read-write original)))
+
+ (define (slice-independent? x y)
+ "Return @code{#true} if all changes to the bytes in @var{x} do not
+impact @var{y}, @code{#false} otherwise. This is a symmetric relation.
+If @var{x} or @var{y} is empty, the slices @var{x} and @var{y} are independent.
+The capabilities of @var{x} and @var{y} are irrelevant."
+ ;; Except for utils/bv-slice.scm, the tests actually only require
+ ;; @code{(not (eq? (slice-bv x) (slice-bv y)))}.
+ ;;
+ ;; TODO: should write access to 'x' or 'y' be required?
+ (or (not (eq? (slice-bv x) (slice-bv y)))
+ (= 0 (slice-length x))
+ (= 0 (slice-length y))
+ (<= (+ (slice-offset x) (slice-length x)) (slice-offset y))
+ (<= (+ (slice-offset y) (slice-length y)) (slice-offset x)))))
diff --git a/tests/bv-slice.scm b/tests/bv-slice.scm
index 620373b..edaefbf 100644
--- a/tests/bv-slice.scm
+++ b/tests/bv-slice.scm
@@ -19,7 +19,9 @@
(import (gnu gnunet utils bv-slice)
(srfi srfi-26)
(ice-9 match)
+ (only (rnrs base) assert)
(rnrs conditions)
+ (rnrs control)
(rnrs exceptions)
(rnrs bytevectors))
@@ -176,9 +178,6 @@
(object->string
(slice/write-only (bv-slice/read-write #vu8(1 2 3)))))
-(define (slice-independent? x y)
- (not (eq? (slice-bv x) (slice-bv y))))
-
(test-missing-caps
"source of slice-copy/read-write must be readable"
'original
@@ -272,6 +271,94 @@
(slice-copy! copy (bv-slice/read-write bv))
bv))
+(test-assert "empty slices are independent"
+ (slice-independent? (make-slice/read-write 0) (make-slice/read-write 0)))
+
+(test-assert "empty slices are independent, even if using the same bytevector"
+ (let ((bv #vu8()))
+ (slice-independent? (bv-slice/read-write bv) (bv-slice/read-write bv))))
+
+(test-assert "empty slices are independent, even when using offsets (1)"
+ (let ((bv #vu8(0 1 2 3)))
+ (slice-independent? (bv-slice/read-write bv 1 0)
+ (bv-slice/read-write bv 2 0))))
+
+(test-assert "empty slices are independent, even when using offsets (2)"
+ (let ((bv #vu8(0 1 2 3)))
+ (slice-independent? (bv-slice/read-write bv 2 0)
+ (bv-slice/read-write bv 1 0))))
+
+(test-assert "empty slices are independent, even if eq?"
+ (let ((s (bv-slice/read-write #vu8())))
+ (slice-independent? s s)))
+
+(test-assert "slice-independent? is irreflexive (assuming non-empty) and
ignores capabilities (1)"
+ (let ((s (make-slice/read-write 99)))
+ (not (slice-independent? (slice/write-only s) (slice/read-only s)))))
+
+(test-assert "slice-independent? is irreflexive (assuming non-empty) and
ignores capabilities (2)"
+ (let ((s (make-slice/read-write 1)))
+ (not (slice-independent? (slice/write-only s) (slice/read-only s)))))
+
+(test-assert "empty slice is independent, even if inside the other slice"
+ (let ((bv #vu8(0 1 2 3 4 5 6 7 8 9)))
+ (do ((offset-x 0 (+ 1 offset-x)))
+ ((> offset-x (bytevector-length bv)) #true)
+ (do ((length-x 0 (+ 1 length-x)))
+ ((>= length-x (- (bytevector-length bv) offset-x)))
+ (let ((x (bv-slice/read-write bv offset-x length-x)))
+ (do ((offset 0 (+ 1 offset)))
+ ((>= offset (bytevector-length bv)) (values))
+ (let ((y (bv-slice/read-write bv offset 0)))
+ (assert (slice-independent? x y))
+ (assert (slice-independent? y x)))))))))
+
+(test-assert "non-overlapping ranges are independent"
+ (let ((bv #vu8(0 1 2 3 4 5 6 7 8 9)))
+ (do ((offset-x 0 (+ 1 offset-x)))
+ ((> offset-x (bytevector-length bv)) #true)
+ (do ((length-x 0 (+ 1 length-x)))
+ ((>= length-x (- (bytevector-length bv) offset-x)))
+ (let ((x (bv-slice/read-write bv offset-x length-x)))
+ ;; Make a slice on the left
+ (do ((offset-y 0 (+ 1 offset-y)))
+ ((> offset-y offset-x))
+ (do ((length-y 0 (+ 1 length-y)))
+ ((>= (+ length-y offset-y) offset-x))
+ (let ((y (bv-slice/read-write bv offset-y length-y)))
+ (assert (slice-independent? x y))
+ (assert (slice-independent? y x)))))
+ ;; And a slice on the right
+ (do ((offset-y (+ offset-x length-x) (+ 1 offset-y)))
+ ((> offset-y (bytevector-length bv)))
+ (do ((length-y 0 (+ 1 length-y)))
+ ((>= (+ length-y offset-y) (bytevector-length bv)))
+ (let ((y (bv-slice/read-write bv offset-y length-y)))
+ (assert (slice-independent? x y))
+ (assert (slice-independent? y x))))))))))
+
+(test-assert "overlapping ranges are dependent"
+ (let ((bv #vu8(0 1 2 3 4 5 6 7 8 9)))
+ (do ((offset-x 0 (+ 1 offset-x)))
+ ;; - 1 to make sure 'x' is non-empty
+ ((> offset-x (- (bytevector-length bv) 1)) #true)
+ (do ((length-x 1 (+ 1 length-x)))
+ ((>= length-x (- (bytevector-length bv) offset-x)))
+ (let ((x (bv-slice/read-write bv offset-x length-x)))
+ ;; Choose a start coordinate inside x or left of x
+ (do ((offset-y 0 (+ 1 offset-y)))
+ ((>= offset-y (+ offset-x length-x) -1))
+ ;; Choose a (non-empty) length
+ (do ((length-y (if (< offset-y offset-x)
+ (- offset-x offset-y -1)
+ 1)
+ (+ 1 length-y)))
+ ((>= (+ offset-y length-y) (bytevector-length bv)))
+ (let ((y (bv-slice/read-write bv offset-y length-y)))
+ (assert (not (slice-independent? x y)))
+ (assert (not (slice-independent? y x)))))))))
+ #true))
+
(test-end "bv-slice")
;; ^ TODO: test other procedures
diff --git a/tests/distributed-hash-table.scm b/tests/distributed-hash-table.scm
index 0d752b6..a961e43 100644
--- a/tests/distributed-hash-table.scm
+++ b/tests/distributed-hash-table.scm
@@ -268,9 +268,6 @@
(define (insertion=? x y)
(equal? (insertion->sexp x) (insertion->sexp y)))
-(define (slice-independent? x y)
- (not (eq? (slice-bv x) (slice-bv y))))
-
(define (query-independent? x y)
(slice-independent? (query-key x) (query-key y)))
--
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.