analyzer: add function-set.cc/h

This patch adds a simple mechanism for tracking sets of functions
for which a particular property holds, as a pragmatic way to build
knowledge about important APIs into the analyzer without requiring
markup of the user's libc.

gcc/ChangeLog:
	* Makefile.in (ANALYZER_OBJS): Add analyzer/function-set.o.

gcc/analyzer/ChangeLog:
	* analyzer-selftests.cc (selftest::run_analyzer_selftests): Call
	selftest::analyzer_function_set_cc_tests.
	* analyzer-selftests.h (selftest::analyzer_function_set_cc_tests):
	New decl.
	* function-set.cc: New file.
	* function-set.h: New file.

7 files changed, 253 insertions, 0 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 356bc63..7317003 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,7 @@
+2020-01-14  David Malcolm  <dmalcolm@redhat.com>
+
+	* Makefile.in (ANALYZER_OBJS): Add analyzer/function-set.o.
+
 2020-01-15  Jakub Jelinek  <jakub@redhat.com>
 
 	PR target/93009
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 5c6d0a7..c86fc7f 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1226,6 +1226,7 @@ ANALYZER_OBJS = \
 	analyzer/constraint-manager.o \
 	analyzer/diagnostic-manager.o \
 	analyzer/engine.o \
+	analyzer/function-set.o \
 	analyzer/pending-diagnostic.o \
 	analyzer/program-point.o \
 	analyzer/program-state.o \
diff --git a/gcc/analyzer/ChangeLog b/gcc/analyzer/ChangeLog
index 96d5ce9..93efb47 100644
--- a/gcc/analyzer/ChangeLog
+++ b/gcc/analyzer/ChangeLog
@@ -1,5 +1,14 @@
 2020-01-14  David Malcolm  <dmalcolm@redhat.com>
 
+	* analyzer-selftests.cc (selftest::run_analyzer_selftests): Call
+	selftest::analyzer_function_set_cc_tests.
+	* analyzer-selftests.h (selftest::analyzer_function_set_cc_tests):
+	New decl.
+	* function-set.cc: New file.
+	* function-set.h: New file.
+
+2020-01-14  David Malcolm  <dmalcolm@redhat.com>
+
 	* analyzer.h (fndecl_has_gimple_body_p): New decl.
 	* engine.cc (impl_region_model_context::on_unknown_change): New
 	function.
diff --git a/gcc/analyzer/analyzer-selftests.cc b/gcc/analyzer/analyzer-selftests.cc
index 8f52ce2..99b730a 100644
--- a/gcc/analyzer/analyzer-selftests.cc
+++ b/gcc/analyzer/analyzer-selftests.cc
@@ -50,6 +50,7 @@ run_analyzer_selftests ()
 {
 #if ENABLE_ANALYZER
   analyzer_constraint_manager_cc_tests ();
+  analyzer_function_set_cc_tests ();
   analyzer_program_point_cc_tests ();
   analyzer_program_state_cc_tests ();
   analyzer_region_model_cc_tests ();
diff --git a/gcc/analyzer/analyzer-selftests.h b/gcc/analyzer/analyzer-selftests.h
index 6f08aa2..61e3a02 100644
--- a/gcc/analyzer/analyzer-selftests.h
+++ b/gcc/analyzer/analyzer-selftests.h
@@ -33,6 +33,7 @@ extern void run_analyzer_selftests ();
    alphabetical order.  */
 extern void analyzer_checker_script_cc_tests ();
 extern void analyzer_constraint_manager_cc_tests ();
+extern void analyzer_function_set_cc_tests ();
 extern void analyzer_program_point_cc_tests ();
 extern void analyzer_program_state_cc_tests ();
 extern void analyzer_region_model_cc_tests ();
diff --git a/gcc/analyzer/function-set.cc b/gcc/analyzer/function-set.cc
new file mode 100644
index 0000000..93ce473
--- /dev/null
+++ b/gcc/analyzer/function-set.cc
@@ -0,0 +1,191 @@
+/* Sets of function names.
+   Copyright (C) 2019-2020 Free Software Foundation, Inc.
+   Contributed by David Malcolm <dmalcolm@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tree.h"
+#include "selftest.h"
+#include "analyzer/function-set.h"
+
+#if ENABLE_ANALYZER
+
+/* Return true if NAME is within this set.  */
+
+bool
+function_set::contains_name_p (const char *name) const
+{
+  /* Binary search.  */
+  int min = 0;
+  int max = m_count - 1;
+  while (true)
+    {
+      if (min > max)
+	return false;
+      int midpoint = (min + max) / 2;
+      gcc_assert ((size_t)midpoint < m_count);
+      int cmp = strcmp (name, m_names[midpoint]);
+      if (cmp == 0)
+	return true;
+      else if (cmp < 0)
+	max = midpoint - 1;
+      else
+	min = midpoint + 1;
+    }
+}
+
+/* Return true if FNDECL is within this set.  */
+
+bool
+function_set::contains_decl_p (tree fndecl) const
+{
+  gcc_assert (fndecl && DECL_P (fndecl));
+  return contains_name_p (IDENTIFIER_POINTER (DECL_NAME (fndecl)));
+}
+
+/* Assert that the list of names is in sorted order.  */
+
+void
+function_set::assert_sorted () const
+{
+#if CHECKING_P
+  for (size_t idx = 1; idx < m_count; idx++)
+    gcc_assert (strcmp (m_names[idx - 1], m_names[idx]) < 0);
+#endif /* #if CHECKING_P  */
+}
+
+/* Assert that contains_p is true for all members of the set.  */
+
+void
+function_set::assert_sane () const
+{
+#if CHECKING_P
+  for (size_t i = 0; i < m_count; i++)
+    gcc_assert (contains_name_p (m_names[i]));
+#endif /* #if CHECKING_P  */
+}
+
+#if CHECKING_P
+
+namespace selftest {
+
+/* Verify that an empty function_set works as expected.  */
+
+static void
+test_empty ()
+{
+  function_set fs (NULL, 0);
+  fs.assert_sorted ();
+  fs.assert_sane ();
+  ASSERT_FALSE (fs.contains_name_p (""));
+  ASSERT_FALSE (fs.contains_name_p ("haystack"));
+}
+
+/* Verify that a function_set with an odd number of elements works as
+   expected.  */
+
+static void
+test_odd ()
+{
+  static const char * const names[3] = {"alpha", "beta", "gamma"};
+  function_set fs (names, 3);
+  fs.assert_sorted ();
+  fs.assert_sane ();
+  ASSERT_FALSE (fs.contains_name_p (""));
+  ASSERT_FALSE (fs.contains_name_p ("haystack"));
+}
+
+/* Verify that a function_set with an even number of elements works as
+   expected.  */
+
+static void
+test_even ()
+{
+  static const char * const names[3] = {"alpha", "beta"};
+  function_set fs (names, 2);
+  fs.assert_sorted ();
+  fs.assert_sane ();
+  ASSERT_FALSE (fs.contains_name_p (""));
+  ASSERT_FALSE (fs.contains_name_p ("haystack"));
+}
+
+/* Verify that a function_set with some nontrivial stdio.h data works as
+   expected.  */
+
+static void
+test_stdio_example ()
+{
+  static const char * const example[] = {
+    "__fbufsize",
+    "__flbf",
+    "__fpending",
+    "__fpurge",
+    "__freadable",
+    "__freading",
+    "__fsetlocking",
+    "__fwritable",
+    "__fwriting",
+    "clearerr_unlocked",
+    "feof_unlocked",
+    "ferror_unlocked",
+    "fflush_unlocked",
+    "fgetc_unlocked",
+    "fgets",
+    "fgets_unlocked",
+    "fgetwc_unlocked",
+    "fgetws_unlocked",
+    "fileno_unlocked",
+    "fputc_unlocked",
+    "fputs_unlocked",
+    "fputwc_unlocked",
+    "fputws_unlocked",
+    "fread_unlocked",
+    "fwrite_unlocked",
+    "getc_unlocked",
+    "getwc_unlocked",
+    "putc_unlocked"
+  };
+  const size_t count = sizeof(example) / sizeof (example[0]);
+  function_set fs (example, count);
+  fs.assert_sorted ();
+  fs.assert_sane ();
+  /* Examples of strings not present: before, after and alongside the
+     sorted list.  */
+  ASSERT_FALSE (fs.contains_name_p ("___"));
+  ASSERT_FALSE (fs.contains_name_p ("Z"));
+  ASSERT_FALSE (fs.contains_name_p ("fgets_WITH_A_PREFIX"));
+}
+
+/* Run all of the selftests within this file.  */
+
+void
+analyzer_function_set_cc_tests ()
+{
+  test_empty ();
+  test_odd ();
+  test_even ();
+  test_stdio_example ();
+}
+
+} // namespace selftest
+
+#endif /* CHECKING_P */
+
+#endif /* #if ENABLE_ANALYZER */
diff --git a/gcc/analyzer/function-set.h b/gcc/analyzer/function-set.h
new file mode 100644
index 0000000..9c73bf5
--- /dev/null
+++ b/gcc/analyzer/function-set.h
@@ -0,0 +1,46 @@
+/* Sets of function names.
+   Copyright (C) 2019-2020 Free Software Foundation, Inc.
+   Contributed by David Malcolm <dmalcolm@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GCC_ANALYZER_FUNCTION_SET_H
+#define GCC_ANALYZER_FUNCTION_SET_H
+
+/* A set of names.  */
+
+class function_set
+{
+public:
+  /* Construct from a sorted array NAMES of size COUNT.  */
+  function_set (const char * const *names, size_t count)
+  : m_names (names), m_count (count)
+  {
+  }
+
+  bool contains_name_p (const char *name) const;
+  bool contains_decl_p (tree fndecl) const;
+
+  void assert_sorted () const;
+  void assert_sane () const;
+
+private:
+  const char * const *m_names; // must be sorted
+  size_t m_count;
+};
+
+#endif /* GCC_ANALYZER_FUNCTION_SET_H */