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>

crypto/stack/stack.c

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) {

crypto/stack/stack_test.cc

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()));
+}

include/openssl/stack.h

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