More fuzzing interfaces

llvm-svn: 316394

3 files changed, 145 insertions, 20 deletions

diff --git a/libcxx/fuzzing/RoutineNames.txt b/libcxx/fuzzing/RoutineNames.txt
new file mode 100644
index 00000000000..cbfe4155ae4
--- /dev/null
+++ b/libcxx/fuzzing/RoutineNames.txt
@@ -0,0 +1,16 @@
+sort
+stable_sort
+partition
+stable_partition
+nth_element
+partial_sort
+make_heap
+push_heap
+pop_heap
+regex_ECMAScript
+regex_POSIX
+regex_extended
+regex_awk
+regex_grep
+regex_egrep
+search
diff --git a/libcxx/fuzzing/fuzzing.cpp b/libcxx/fuzzing/fuzzing.cpp
index c4410199d65..66a9d6af2e4 100644
--- a/libcxx/fuzzing/fuzzing.cpp
+++ b/libcxx/fuzzing/fuzzing.cpp
@@ -26,9 +26,12 @@
 #include "fuzzing.h"
 #include <vector>
 #include <algorithm>
+#include <functional>
 #include <regex>
 
-//	If we had C++14, we could use the four iterator version of is_permutation
+#include <iostream>
+
+//	If we had C++14, we could use the four iterator version of is_permutation and equal
 
 namespace fuzzing {
 
@@ -273,4 +276,101 @@ int regex_egrep (const uint8_t *data, size_t size)
 	return 0;
 }
 
+// --	heap fuzzers
+int make_heap (const uint8_t *data, size_t size)
+{
+	std::vector<uint8_t> working(data, data + size);
+	std::make_heap(working.begin(), working.end());
+
+	if (!std::is_heap(working.begin(), working.end())) return 1;
+	if (!std::is_permutation(data, data + size, working.begin())) return 99;
+	return 0;
+}
+
+int push_heap (const uint8_t *data, size_t size)
+{
+	if (size < 2) return 0;
+
+//	Make a heap from the first half of the data
+	std::vector<uint8_t> working(data, data + size);
+	auto iter = working.begin() + (size / 2);
+	std::make_heap(working.begin(), iter);
+	if (!std::is_heap(working.begin(), iter)) return 1;
+
+//	Now push the rest onto the heap, one at a time
+	++iter;
+	for (; iter != working.end(); ++iter) {
+		std::push_heap(working.begin(), iter);
+		if (!std::is_heap(working.begin(), iter)) return 2;	
+		}
+
+	if (!std::is_permutation(data, data + size, working.begin())) return 99;
+	return 0;
+}
+
+int pop_heap (const uint8_t *data, size_t size)
+{
+	if (size < 2) return 0;
+	std::vector<uint8_t> working(data, data + size);
+	std::make_heap(working.begin(), working.end());
+
+//	Pop things off, one at a time
+	auto iter = --working.end();
+	while (iter != working.begin()) {
+		std::pop_heap(working.begin(), iter);
+		if (!std::is_heap(working.begin(), --iter)) return 2;	
+		}
+
+	return 0;
+}
+
+
+// --	search fuzzers
+int search (const uint8_t *data, size_t size)
+{
+	if (size < 2) return 0;
+	
+	const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max();
+	assert(pat_size <= size - 1);
+	const uint8_t *pat_begin = data + 1;
+	const uint8_t *pat_end   = pat_begin + pat_size;
+	const uint8_t *data_end  = data + size;
+	assert(pat_end <= data_end);
+// 	std::cerr << "data[0] = " << size_t(data[0]) << " ";
+// 	std::cerr << "Pattern size = " << pat_size << "; corpus is " << size - 1 << std::endl;
+	auto it = std::search(pat_end, data_end, pat_begin, pat_end);
+	if (it != data_end) // not found
+		if (!std::equal(pat_begin, pat_end, it))
+			return 1;
+	return 0;
+}
+
+template <typename S>
+static int search_helper (const uint8_t *data, size_t size)
+{
+	if (size < 2) return 0;
+	
+	const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max();
+	const uint8_t *pat_begin = data + 1;
+	const uint8_t *pat_end   = pat_begin + pat_size;
+	const uint8_t *data_end  = data + size;
+
+	auto it = std::search(pat_end, data_end, S(pat_begin, pat_end));
+	if (it != data_end) // not found
+		if (!std::equal(pat_begin, pat_end, it))
+			return 1;
+	return 0;
+}
+
+//	These are still in std::experimental
+// int search_boyer_moore (const uint8_t *data, size_t size)
+// {
+// 	return search_helper<std::boyer_moore_searcher<const uint8_t *>>(data, size);
+// }
+// 
+// int search_boyer_moore_horspool (const uint8_t *data, size_t size)
+// {
+// 	return search_helper<std::boyer_moore_horspool_searcher<const uint8_t *>>(data, size);
+// }
+
 } // namespace fuzzing
diff --git a/libcxx/fuzzing/fuzzing.h b/libcxx/fuzzing/fuzzing.h
index 6624955f8ed..6093c32c226 100644
--- a/libcxx/fuzzing/fuzzing.h
+++ b/libcxx/fuzzing/fuzzing.h
@@ -16,25 +16,34 @@
 
 namespace fuzzing {
 
-//	These all return 0 on success; != 0 on failure
-	int sort             (const uint8_t *data, size_t size);
-	int stable_sort      (const uint8_t *data, size_t size);
-	int partition        (const uint8_t *data, size_t size);
-	int stable_partition (const uint8_t *data, size_t size);
-
-//	partition and stable_partition take Bi-Di iterators.
-//	Should test those, too
-
-	int nth_element      (const uint8_t *data, size_t size);
-	int partial_sort     (const uint8_t *data, size_t size);
-
-//	Various flavors of regex
-	int regex_ECMAScript (const uint8_t *data, size_t size);
-	int regex_POSIX      (const uint8_t *data, size_t size);
-	int regex_extended   (const uint8_t *data, size_t size);
-	int regex_awk        (const uint8_t *data, size_t size);
-	int regex_grep       (const uint8_t *data, size_t size);
-	int regex_egrep      (const uint8_t *data, size_t size);
+//  These all return 0 on success; != 0 on failure
+    int sort             (const uint8_t *data, size_t size);
+    int stable_sort      (const uint8_t *data, size_t size);
+    int partition        (const uint8_t *data, size_t size);
+    int stable_partition (const uint8_t *data, size_t size);
+
+//  partition and stable_partition take Bi-Di iterators.
+//  Should test those, too
+    int nth_element      (const uint8_t *data, size_t size);
+    int partial_sort     (const uint8_t *data, size_t size);
+
+//  Heap operations
+    int make_heap        (const uint8_t *data, size_t size);
+    int push_heap        (const uint8_t *data, size_t size);
+    int pop_heap         (const uint8_t *data, size_t size);
+
+//  Various flavors of regex
+    int regex_ECMAScript (const uint8_t *data, size_t size);
+    int regex_POSIX      (const uint8_t *data, size_t size);
+    int regex_extended   (const uint8_t *data, size_t size);
+    int regex_awk        (const uint8_t *data, size_t size);
+    int regex_grep       (const uint8_t *data, size_t size);
+    int regex_egrep      (const uint8_t *data, size_t size);
+
+//	Searching
+	int search                      (const uint8_t *data, size_t size);
+// 	int search_boyer_moore          (const uint8_t *data, size_t size);
+// 	int search_boyer_moore_horspool (const uint8_t *data, size_t size);
 
 } // namespace fuzzing