From a6b5f19c37001d7c9974248ffcb65aadba33283c Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Thu, 19 Dec 2019 15:43:04 -0500 Subject: [PATCH] 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. --- gcc/ChangeLog | 4 + gcc/Makefile.in | 1 + gcc/analyzer/ChangeLog | 9 ++ gcc/analyzer/analyzer-selftests.cc | 1 + gcc/analyzer/analyzer-selftests.h | 1 + gcc/analyzer/function-set.cc | 191 +++++++++++++++++++++++++++++ gcc/analyzer/function-set.h | 46 +++++++ 7 files changed, 253 insertions(+) create mode 100644 gcc/analyzer/function-set.cc create mode 100644 gcc/analyzer/function-set.h diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 356bc63c6d0..73170037f0d 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,7 @@ +2020-01-14 David Malcolm + + * Makefile.in (ANALYZER_OBJS): Add analyzer/function-set.o. + 2020-01-15 Jakub Jelinek PR target/93009 diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 5c6d0a737e6..c86fc7f41dc 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 96d5ce99538..93efb47bb7c 100644 --- a/gcc/analyzer/ChangeLog +++ b/gcc/analyzer/ChangeLog @@ -1,3 +1,12 @@ +2020-01-14 David Malcolm + + * 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 * analyzer.h (fndecl_has_gimple_body_p): New decl. diff --git a/gcc/analyzer/analyzer-selftests.cc b/gcc/analyzer/analyzer-selftests.cc index 8f52ce2e45c..99b730a6be5 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 6f08aa2b1bc..61e3a024dff 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 00000000000..93ce473405f --- /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 . + +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 +. */ + +#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 00000000000..9c73bf57ade --- /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 . + +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 +. */ + +#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 */ -- 2.30.2