Empty stacks are vacuously sorted
In the X.509 policy rewrite, I'll be using sorted stacks to keep the
overall algorithm subquadratic. Fix up sk_FOO_is_sorted in these edge
cases so the asserts work more smoothly.
Change-Id: I369f53543f0c2219df6f62a81aead630a9dbcd8d
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/56031
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Bob Beck <bbe@google.com>
diff --git a/crypto/stack/stack.c b/crypto/stack/stack.c
index 2dbb842..7f60b2e 100644
--- a/crypto/stack/stack.c
+++ b/crypto/stack/stack.c
@@ -415,7 +415,8 @@
if (!sk) {
return 1;
}
- return sk->sorted;
+ // Zero- and one-element lists are always sorted.
+ return sk->sorted || (sk->comp != NULL && sk->num < 2);
}
OPENSSL_sk_cmp_func sk_set_cmp_func(_STACK *sk, OPENSSL_sk_cmp_func comp) {
diff --git a/crypto/stack/stack_test.cc b/crypto/stack/stack_test.cc
index 9a7832c..f96b942 100644
--- a/crypto/stack/stack_test.cc
+++ b/crypto/stack/stack_test.cc
@@ -434,3 +434,47 @@
ExpectStackEquals(sk.get(), {});
EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
}
+
+TEST(StackTest, IsSorted) {
+ bssl::UniquePtr<STACK_OF(TEST_INT)> sk(sk_TEST_INT_new_null());
+ ASSERT_TRUE(sk);
+ EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
+
+ // Empty lists are always known to be sorted.
+ sk_TEST_INT_set_cmp_func(sk.get(), compare);
+ EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
+
+ // As are one-element lists.
+ auto value = TEST_INT_new(2);
+ ASSERT_TRUE(value);
+ ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
+ EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
+
+ // Two-element lists require an explicit sort.
+ value = TEST_INT_new(1);
+ ASSERT_TRUE(value);
+ ASSERT_TRUE(bssl::PushToStack(sk.get(), std::move(value)));
+ EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
+
+ // The list is now sorted.
+ sk_TEST_INT_sort(sk.get());
+ EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
+
+ // After changing the comparison function, it no longer is sorted.
+ sk_TEST_INT_set_cmp_func(sk.get(), compare_reverse);
+ EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
+
+ sk_TEST_INT_sort(sk.get());
+ EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
+
+ // But, starting from one element, switching the comparison function preserves
+ // the sorted bit.
+ TEST_INT_free(sk_TEST_INT_pop(sk.get()));
+ EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
+ sk_TEST_INT_set_cmp_func(sk.get(), compare);
+ EXPECT_TRUE(sk_TEST_INT_is_sorted(sk.get()));
+
+ // Without a comparison function, the list cannot be sorted.
+ sk_TEST_INT_set_cmp_func(sk.get(), nullptr);
+ EXPECT_FALSE(sk_TEST_INT_is_sorted(sk.get()));
+}
diff --git a/include/openssl/stack.h b/include/openssl/stack.h
index cf03002..f667f63 100644
--- a/include/openssl/stack.h
+++ b/include/openssl/stack.h
@@ -267,8 +267,9 @@
// Note its actual type is |int (*)(const T **a, const T **b)|. Low-level |sk_*|
// functions will be passed a type-specific wrapper to call it correctly.
//
-// TODO(davidben): This type should be |const T *const *|. It is already fixed
-// in OpenSSL 1.1.1, so hopefully we can fix this compatibly.
+// TODO(https://crbug.com/boringssl/498): This type should be
+// |const T *const *|. It is already fixed in OpenSSL 1.1.1, so hopefully we can
+// fix this compatibly.
typedef int (*OPENSSL_sk_cmp_func)(const void **a, const void **b);
// OPENSSL_sk_delete_if_func is the generic version of