[analyzer] Provide Contains() on ImmutableMap program state partial trait.

[dcoughlin]

This seems reasonable and it looks good to me (as long as there is a later patch coming that calls the new method).

However: is there a situation where Contains() is preferable to Lookup()? It seems to me that in some cases you would want the looked-up value -- and in those where you don't there is no cost to return a pointer to it. As far as I can tell both ultimately end up as a call to find() on the AVL tree.

[ddcc]

Even though there isn't a performance difference, I think it is semantically clearer since it is explicit that the value is unneeded.

The interface of ProgramState provides a contains() function that calls into Contains() of the underlying partial traits as part of its implementation. That function is present for ImmutableSet and ImmutableList, so it is inconsistent that ImmutableMap doesn't have it. I've been working on a Z3 constraint backend that uses this, though the implementation has been trickier than I expected.

[dcoughlin]

In D26373#589614, @ddcc wrote:

Even though there isn't a performance difference, I think it is semantically clearer since it is explicit that the value is unneeded.

Makes sense to me!

include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h

 //ProgramStateTrait.h - Partial implementations of ProgramStateTrait -*- C++ -*-
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines partial implementations of template specializations of
-//  the class ProgramStateTrait<>.  ProgramStateTrait<> is used by ProgramState 
+//  the class ProgramStateTrait<>.  ProgramStateTrait<> is used by ProgramState
 //  to implement set/get methods for manipulating a ProgramState's
 //  generic data map.
 //
 //===----------------------------------------------------------------------===//
 
 
 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATETRAIT_H
 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_PROGRAMSTATETRAIT_H
struct ProgramStatePartialTrait< llvm::ImmutableMap<Key,Data,Info> > {
     static data_type Set(data_type B, key_type K, value_type E,context_type F){
       return F.add(B, K, E);
     }
 
     static data_type Remove(data_type B, key_type K, context_type F) {
       return F.remove(B, K);
     }
 
+    static bool Contains(data_type B, key_type K) {
+      return B.contains(K);
+    }
+
     static inline context_type MakeContext(void *p) {
       return *((typename data_type::Factory*) p);
     }
 
     static void *CreateContext(llvm::BumpPtrAllocator& Alloc) {
       return new typename data_type::Factory(Alloc);
     }
 
static void *CreateContext(llvm::BumpPtrAllocator& Alloc) {
       return new typename data_type::Factory(Alloc);
     }
 
     static void DeleteContext(void *Ctx) {
       delete (typename data_type::Factory*) Ctx;
     }
   };
 
-  
   // Partial specialization for bool.
   template <> struct ProgramStatePartialTrait<bool> {
     typedef bool data_type;
 
     static inline data_type MakeData(void *const* p) {
       return p ? (data_type) (uintptr_t) *p
                : data_type();
     }
     static inline void *MakeVoidPtr(data_type d) {
       return (void*) (uintptr_t) d;
     }
   };
-  
   // Partial specialization for unsigned.
   template <> struct ProgramStatePartialTrait<unsigned> {
     typedef unsigned data_type;
 
     static inline data_type MakeData(void *const* p) {
       return p ? (data_type) (uintptr_t) *p
                : data_type();
     }