analyzer: add heuristics for switch on enum type [PR105273]

Assume that switch on an enum doesn't follow an implicit default
skipping all cases when all enum values are covered by cases.

Fixes various false positives from -Wanalyzer-use-of-uninitialized-value
such as this one seen in Doom:

p_maputl.c: In function 'P_BoxOnLineSide':
p_maputl.c:151:8: warning: use of uninitialized value 'p1' [CWE-457] [-Wanalyzer-use-of-uninitialized-value]
  151 |     if (p1 == p2)
      |        ^
  'P_BoxOnLineSide': events 1-5
    |
    |  115 |     int         p1;
    |      |                 ^~
    |      |                 |
    |      |                 (1) region created on stack here
    |      |                 (2) capacity: 4 bytes
    |......
    |  118 |     switch (ld->slopetype)
    |      |     ~~~~~~
    |      |     |
    |      |     (3) following 'default:' branch...
    |......
    |  151 |     if (p1 == p2)
    |      |        ~
    |      |        |
    |      |        (4) ...to here
    |      |        (5) use of uninitialized value 'p1' here
    |

where "ld->slopetype" is a "slopetype_t" enum, and for every value of
that enum the switch has a case that initializes "p1".

gcc/analyzer/ChangeLog:
	PR analyzer/105273
	* region-model.cc (has_nondefault_case_for_value_p): New.
	(has_nondefault_cases_for_all_enum_values_p): New.
	(region_model::apply_constraints_for_gswitch): Skip
	implicitly-created "default" when switching on an enum
	and all enum values have non-default cases.
	(rejected_default_case::dump_to_pp): New.
	* region-model.h (region_model_context::possibly_tainted_p): New
	decl.
	(class rejected_default_case): New.
	* sm-taint.cc (region_model_context::possibly_tainted_p): New.
	* supergraph.cc (switch_cfg_superedge::dump_label_to_pp): Dump
	when implicitly_created_default_p.
	(switch_cfg_superedge::implicitly_created_default_p): New.
	* supergraph.h
	(switch_cfg_superedge::implicitly_created_default_p): New decl.

gcc/testsuite/ChangeLog:
	PR analyzer/105273
	* gcc.dg/analyzer/switch-enum-1.c: New test.
	* gcc.dg/analyzer/switch-enum-2.c: New test.
	* gcc.dg/analyzer/switch-enum-pr105273-git-vreportf-2.c: New test.
	* gcc.dg/analyzer/switch-enum-taint-1.c: New test.
	* gcc.dg/analyzer/switch-wrong-enum.c: New test.
	* gcc.dg/analyzer/torture/switch-enum-pr105273-doom-p_floor.c: New
	test.
	* gcc.dg/analyzer/torture/switch-enum-pr105273-doom-p_maputl.c:
	New test.
	* gcc.dg/analyzer/torture/switch-enum-pr105273-git-vreportf-1.c:
	New test.

Signed-off-by: David Malcolm <dmalcolm@redhat.com>

5 files changed, 163 insertions, 2 deletions

diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 2e59fba..6a3a1b4 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -4341,6 +4341,72 @@ region_model::apply_constraints_for_gcond (const cfg_superedge &sedge,
   return add_constraint (lhs, op, rhs, ctxt, out);
 }
 
+/* Return true iff SWITCH_STMT has a non-default label that contains
+   INT_CST.  */
+
+static bool
+has_nondefault_case_for_value_p (const gswitch *switch_stmt, tree int_cst)
+{
+  /* We expect the initial label to be the default; skip it.  */
+  gcc_assert (CASE_LOW (gimple_switch_label (switch_stmt, 0)) == NULL);
+  unsigned min_idx = 1;
+  unsigned max_idx = gimple_switch_num_labels (switch_stmt) - 1;
+
+  /* Binary search: try to find the label containing INT_CST.
+     This requires the cases to be sorted by CASE_LOW (done by the
+     gimplifier).  */
+  while (max_idx >= min_idx)
+    {
+      unsigned case_idx = (min_idx + max_idx) / 2;
+      tree label =  gimple_switch_label (switch_stmt, case_idx);
+      tree low = CASE_LOW (label);
+      gcc_assert (low);
+      tree high = CASE_HIGH (label);
+      if (!high)
+	high = low;
+      if (tree_int_cst_compare (int_cst, low) < 0)
+	{
+	  /* INT_CST is below the range of this label.  */
+	  gcc_assert (case_idx > 0);
+	  max_idx = case_idx - 1;
+	}
+      else if (tree_int_cst_compare (int_cst, high) > 0)
+	{
+	  /* INT_CST is above the range of this case.  */
+	  min_idx = case_idx + 1;
+	}
+      else
+	/* This case contains INT_CST.  */
+	return true;
+    }
+  /* Not found.  */
+  return false;
+}
+
+/* Return true iff SWITCH_STMT (which must be on an enum value)
+   has nondefault cases handling all values in the enum.  */
+
+static bool
+has_nondefault_cases_for_all_enum_values_p (const gswitch *switch_stmt)
+{
+  gcc_assert (switch_stmt);
+  tree type = TREE_TYPE (gimple_switch_index (switch_stmt));
+  gcc_assert (TREE_CODE (type) == ENUMERAL_TYPE);
+
+  for (tree enum_val_iter = TYPE_VALUES (type);
+       enum_val_iter;
+       enum_val_iter = TREE_CHAIN (enum_val_iter))
+    {
+      tree enum_val = TREE_VALUE (enum_val_iter);
+      gcc_assert (TREE_CODE (enum_val) == CONST_DECL);
+      gcc_assert (TREE_CODE (DECL_INITIAL (enum_val)) == INTEGER_CST);
+      if (!has_nondefault_case_for_value_p (switch_stmt,
+					    DECL_INITIAL (enum_val)))
+	return false;
+    }
+  return true;
+}
+
 /* Given an EDGE guarded by SWITCH_STMT, determine appropriate constraints
    for the edge to be taken.
 
@@ -4357,11 +4423,37 @@ region_model::apply_constraints_for_gswitch (const switch_cfg_superedge &edge,
 					     region_model_context *ctxt,
 					     rejected_constraint **out)
 {
+  tree index  = gimple_switch_index (switch_stmt);
+  const svalue *index_sval = get_rvalue (index, ctxt);
+
+  /* If we're switching based on an enum type, assume that the user is only
+     working with values from the enum.  Hence if this is an
+     implicitly-created "default", assume it doesn't get followed.
+     This fixes numerous "uninitialized" false positives where we otherwise
+     consider jumping past the initialization cases.  */
+
+  if (/* Don't check during feasibility-checking (when ctxt is NULL).  */
+      ctxt
+      /* Must be an enum value.  */
+      && index_sval->get_type ()
+      && TREE_CODE (TREE_TYPE (index)) == ENUMERAL_TYPE
+      && TREE_CODE (index_sval->get_type ()) == ENUMERAL_TYPE
+      /* If we have a constant, then we can check it directly.  */
+      && index_sval->get_kind () != SK_CONSTANT
+      && edge.implicitly_created_default_p ()
+      && has_nondefault_cases_for_all_enum_values_p (switch_stmt)
+      /* Don't do this if there's a chance that the index is
+	 attacker-controlled.  */
+      && !ctxt->possibly_tainted_p (index_sval))
+    {
+      if (out)
+	*out = new rejected_default_case (*this);
+      return false;
+    }
+
   bounded_ranges_manager *ranges_mgr = get_range_manager ();
   const bounded_ranges *all_cases_ranges
     = ranges_mgr->get_or_create_ranges_for_switch (&edge, switch_stmt);
-  tree index  = gimple_switch_index (switch_stmt);
-  const svalue *index_sval = get_rvalue (index, ctxt);
   bool sat = m_constraints->add_bounded_ranges (index_sval, all_cases_ranges);
   if (!sat && out)
     *out = new rejected_ranges_constraint (*this, index, all_cases_ranges);
@@ -5686,6 +5778,14 @@ rejected_op_constraint::dump_to_pp (pretty_printer *pp) const
   rhs_sval->dump_to_pp (pp, true);
 }
 
+/* class rejected_default_case : public rejected_constraint.  */
+
+void
+rejected_default_case::dump_to_pp (pretty_printer *pp) const
+{
+  pp_string (pp, "implicit default for enum");
+}
+
 /* class rejected_ranges_constraint : public rejected_constraint.  */
 
 void
diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h
index e8767e5..4e1a5c6 100644
--- a/gcc/analyzer/region-model.h
+++ b/gcc/analyzer/region-model.h
@@ -703,6 +703,8 @@ class region_model_context
     return get_state_map_by_name ("taint", out_smap, out_sm, out_sm_idx, NULL);
   }
 
+  bool possibly_tainted_p (const svalue *sval);
+
   /* Get the current statement, if any.  */
   virtual const gimple *get_stmt () const = 0;
 };
@@ -1010,6 +1012,16 @@ public:
   tree m_rhs;
 };
 
+class rejected_default_case : public rejected_constraint
+{
+public:
+  rejected_default_case (const region_model &model)
+  : rejected_constraint (model)
+  {}
+
+  void dump_to_pp (pretty_printer *pp) const final override;
+};
+
 class rejected_ranges_constraint : public rejected_constraint
 {
 public:
diff --git a/gcc/analyzer/sm-taint.cc b/gcc/analyzer/sm-taint.cc
index a2b442a..3a619b1 100644
--- a/gcc/analyzer/sm-taint.cc
+++ b/gcc/analyzer/sm-taint.cc
@@ -1549,6 +1549,31 @@ region_model::mark_as_tainted (const svalue *sval,
   smap->set_state (this, sval, taint_sm.m_tainted, NULL, *ext_state);
 }
 
+/* Return true if SVAL could possibly be attacker-controlled.  */
+
+bool
+region_model_context::possibly_tainted_p (const svalue *sval)
+{
+  sm_state_map *smap;
+  const state_machine *sm;
+  unsigned sm_idx;
+  if (!get_taint_map (&smap, &sm, &sm_idx))
+      return false;
+
+  const taint_state_machine &taint_sm = (const taint_state_machine &)*sm;
+
+  const extrinsic_state *ext_state = get_ext_state ();
+  if (!ext_state)
+    return false;
+
+  const state_machine::state_t state = smap->get_state (sval, *ext_state);
+  gcc_assert (state);
+
+  return (state == taint_sm.m_tainted
+	  || state == taint_sm.m_has_lb
+	  || state == taint_sm.m_has_ub);
+}
+
 } // namespace ana
 
 #endif /* #if ENABLE_ANALYZER */
diff --git a/gcc/analyzer/supergraph.cc b/gcc/analyzer/supergraph.cc
index 8195fe8..c0bb2c6 100644
--- a/gcc/analyzer/supergraph.cc
+++ b/gcc/analyzer/supergraph.cc
@@ -1153,9 +1153,31 @@ switch_cfg_superedge::dump_label_to_pp (pretty_printer *pp,
 	    pp_printf (pp, "default");
 	}
       pp_character (pp, '}');
+      if (implicitly_created_default_p ())
+	{
+	  pp_string (pp, " IMPLICITLY CREATED");
+	}
     }
 }
 
+/* Return true iff this edge is purely for an implicitly-created "default".  */
+
+bool
+switch_cfg_superedge::implicitly_created_default_p () const
+{
+  if (m_case_labels.length () != 1)
+    return false;
+
+  tree case_label = m_case_labels[0];
+  gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
+  if (CASE_LOW (case_label))
+    return false;
+
+  /* We have a single "default" case.
+     Assume that it was implicitly created if it has UNKNOWN_LOCATION.  */
+  return EXPR_LOCATION (case_label) == UNKNOWN_LOCATION;
+}
+
 /* Implementation of superedge::dump_label_to_pp for interprocedural
    superedges.  */
 
diff --git a/gcc/analyzer/supergraph.h b/gcc/analyzer/supergraph.h
index f66058c..d359e95 100644
--- a/gcc/analyzer/supergraph.h
+++ b/gcc/analyzer/supergraph.h
@@ -570,6 +570,8 @@ class switch_cfg_superedge : public cfg_superedge {
 
   const vec<tree> &get_case_labels () const { return m_case_labels; }
 
+  bool implicitly_created_default_p () const;
+
 private:
   auto_vec<tree> m_case_labels;
 };