diff options
Diffstat (limited to 'docs/analyzer')
| -rw-r--r-- | docs/analyzer/DebugChecks.rst | 134 | ||||
| -rw-r--r-- | docs/analyzer/IPA.txt | 105 | ||||
| -rw-r--r-- | docs/analyzer/Makefile | 155 | ||||
| -rw-r--r-- | docs/analyzer/RegionStore.txt | 171 | ||||
| -rw-r--r-- | docs/analyzer/conf.py | 246 | ||||
| -rw-r--r-- | docs/analyzer/debug-checks.txt | 89 | ||||
| -rw-r--r-- | docs/analyzer/index.rst | 23 | ||||
| -rw-r--r-- | docs/analyzer/make.bat | 190 |
8 files changed, 987 insertions, 126 deletions
diff --git a/docs/analyzer/DebugChecks.rst b/docs/analyzer/DebugChecks.rst new file mode 100644 index 0000000..f8e6f82 --- /dev/null +++ b/docs/analyzer/DebugChecks.rst @@ -0,0 +1,134 @@ +============ +Debug Checks +============ + +.. contents:: + :local: + +The analyzer contains a number of checkers which can aid in debugging. Enable +them by using the "-analyzer-checker=" flag, followed by the name of the +checker. + + +General Analysis Dumpers +======================== + +These checkers are used to dump the results of various infrastructural analyses +to stderr. Some checkers also have "view" variants, which will display a graph +using a 'dot' format viewer (such as Graphviz on OS X) instead. + +- debug.DumpCallGraph, debug.ViewCallGraph: Show the call graph generated for + the current translation unit. This is used to determine the order in which to + analyze functions when inlining is enabled. + +- debug.DumpCFG, debug.ViewCFG: Show the CFG generated for each top-level + function being analyzed. + +- debug.DumpDominators: Shows the dominance tree for the CFG of each top-level + function. + +- debug.DumpLiveVars: Show the results of live variable analysis for each + top-level function being analyzed. + + +Path Tracking +============= + +These checkers print information about the path taken by the analyzer engine. + +- debug.DumpCalls: Prints out every function or method call encountered during a + path traversal. This is indented to show the call stack, but does NOT do any + special handling of branches, meaning different paths could end up + interleaved. + +- debug.DumpTraversal: Prints the name of each branch statement encountered + during a path traversal ("IfStmt", "WhileStmt", etc). Currently used to check + whether the analysis engine is doing BFS or DFS. + + +State Checking +============== + +These checkers will print out information about the analyzer state in the form +of analysis warnings. They are intended for use with the -verify functionality +in regression tests. + +- debug.TaintTest: Prints out the word "tainted" for every expression that + carries taint. At the time of this writing, taint was only introduced by the + checks under experimental.security.taint.TaintPropagation; this checker may + eventually move to the security.taint package. + +- debug.ExprInspection: Responds to certain function calls, which are modeled + after builtins. These function calls should affect the program state other + than the evaluation of their arguments; to use them, you will need to declare + them within your test file. The available functions are described below. + +(FIXME: debug.ExprInspection should probably be renamed, since it no longer only +inspects expressions.) + + +ExprInspection checks +--------------------- + +- void clang_analyzer_eval(bool); + + Prints TRUE if the argument is known to have a non-zero value, FALSE if the + argument is known to have a zero or null value, and UNKNOWN if the argument + isn't sufficiently constrained on this path. You can use this to test other + values by using expressions like "x == 5". Note that this functionality is + currently DISABLED in inlined functions, since different calls to the same + inlined function could provide different information, making it difficult to + write proper -verify directives. + + In C, the argument can be typed as 'int' or as '_Bool'. + + Example usage:: + + clang_analyzer_eval(x); // expected-warning{{UNKNOWN}} + if (!x) return; + clang_analyzer_eval(x); // expected-warning{{TRUE}} + + +- void clang_analyzer_checkInlined(bool); + + If a call occurs within an inlined function, prints TRUE or FALSE according to + the value of its argument. If a call occurs outside an inlined function, + nothing is printed. + + The intended use of this checker is to assert that a function is inlined at + least once (by passing 'true' and expecting a warning), or to assert that a + function is never inlined (by passing 'false' and expecting no warning). The + argument is technically unnecessary but is intended to clarify intent. + + You might wonder why we can't print TRUE if a function is ever inlined and + FALSE if it is not. The problem is that any inlined function could conceivably + also be analyzed as a top-level function (in which case both TRUE and FALSE + would be printed), depending on the value of the -analyzer-inlining option. + + In C, the argument can be typed as 'int' or as '_Bool'. + + Example usage:: + + int inlined() { + clang_analyzer_checkInlined(true); // expected-warning{{TRUE}} + return 42; + } + + void topLevel() { + clang_analyzer_checkInlined(false); // no-warning (not inlined) + int value = inlined(); + // This assertion will not be valid if the previous call was not inlined. + clang_analyzer_eval(value == 42); // expected-warning{{TRUE}} + } + + +Statistics +========== + +The debug.Stats checker collects various information about the analysis of each +function, such as how many blocks were reached and if the analyzer timed out. + +There is also an additional -analyzer-stats flag, which enables various +statistics within the analyzer engine. Note the Stats checker (which produces at +least one bug report per function) may actually change the values reported by +-analyzer-stats. diff --git a/docs/analyzer/IPA.txt b/docs/analyzer/IPA.txt index 016cea9..01e73ce 100644 --- a/docs/analyzer/IPA.txt +++ b/docs/analyzer/IPA.txt @@ -2,36 +2,37 @@ Inlining ======== There are several options that control which calls the analyzer will consider for -inlining. The major one is -analyzer-ipa: +inlining. The major one is -analyzer-config ipa: - -analyzer-ipa=none - All inlining is disabled. This is the only mode available - in LLVM 3.1 and earlier and in Xcode 4.3 and earlier. + -analyzer-config ipa=none - All inlining is disabled. This is the only mode + available in LLVM 3.1 and earlier and in Xcode 4.3 and earlier. - -analyzer-ipa=basic-inlining - Turns on inlining for C functions, C++ static - member functions, and blocks -- essentially, the calls that behave like - simple C function calls. This is essentially the mode used in Xcode 4.4. + -analyzer-config ipa=basic-inlining - Turns on inlining for C functions, C++ + static member functions, and blocks -- essentially, the calls that behave + like simple C function calls. This is essentially the mode used in + Xcode 4.4. - -analyzer-ipa=inlining - Turns on inlining when we can confidently find the - function/method body corresponding to the call. (C functions, static + -analyzer-config ipa=inlining - Turns on inlining when we can confidently find + the function/method body corresponding to the call. (C functions, static functions, devirtualized C++ methods, Objective-C class methods, Objective-C instance methods when ExprEngine is confident about the dynamic type of the instance). - -analyzer-ipa=dynamic - Inline instance methods for which the type is + -analyzer-config ipa=dynamic - Inline instance methods for which the type is determined at runtime and we are not 100% sure that our type info is correct. For virtual calls, inline the most plausible definition. - -analyzer-ipa=dynamic-bifurcate - Same as -analyzer-ipa=dynamic, but the path - is split. We inline on one branch and do not inline on the other. This mode - does not drop the coverage in cases when the parent class has code that is - only exercised when some of its methods are overridden. + -analyzer-config ipa=dynamic-bifurcate - Same as -analyzer-config ipa=dynamic, + but the path is split. We inline on one branch and do not inline on the + other. This mode does not drop the coverage in cases when the parent class + has code that is only exercised when some of its methods are overridden. -Currently, -analyzer-ipa=dynamic-bifurcate is the default mode. +Currently, -analyzer-config ipa=dynamic-bifurcate is the default mode. -While -analyzer-ipa determines in general how aggressively the analyzer will try to -inline functions, several additional options control which types of functions can -inlined, in an all-or-nothing way. These options use the analyzer's configuration -table, so they are all specified as follows: +While -analyzer-config ipa determines in general how aggressively the analyzer +will try to inline functions, several additional options control which types of +functions can inlined, in an all-or-nothing way. These options use the +analyzer's configuration table, so they are all specified as follows: -analyzer-config OPTION=VALUE @@ -45,10 +46,14 @@ Each of these modes implies that all the previous member function kinds will be inlined as well; it doesn't make sense to inline destructors without inlining constructors, for example. -The default c++-inlining mode is 'methods', meaning only regular member -functions and overloaded operators will be inlined. Note that no C++ member -functions will be inlined under -analyzer-ipa=none or --analyzer-ipa=basic-inlining. +The default c++-inlining mode is 'destructors', meaning that all member +functions with visible definitions will be considered for inlining. In some +cases the analyzer may still choose not to inline the function. + +Note that under 'constructors', constructors for types with non-trivial +destructors will not be inlined. Additionally, no C++ member functions will be +inlined under -analyzer-config ipa=none or -analyzer-config ipa=basic-inlining, +regardless of the setting of the c++-inlining mode. ### c++-template-inlining ### @@ -71,7 +76,8 @@ considered for inlining. -analyzer-config c++-template-inlining=[true | false] -Currently, C++ standard library functions are NOT considered for inlining by default. +Currently, C++ standard library functions are considered for inlining by +default. The standard library functions and the STL in particular are used ubiquitously enough that our tolerance for false positives is even lower here. A false @@ -79,6 +85,31 @@ positive due to poor modeling of the STL leads to a poor user experience, since most users would not be comfortable adding assertions to system headers in order to silence analyzer warnings. +### c++-container-inlining ### + +This option controls whether constructors and destructors of "container" types +should be considered for inlining. + + -analyzer-config c++-container-inlining=[true | false] + +Currently, these constructors and destructors are NOT considered for inlining +by default. + +The current implementation of this setting checks whether a type has a member +named 'iterator' or a member named 'begin'; these names are idiomatic in C++, +with the latter specified in the C++11 standard. The analyzer currently does a +fairly poor job of modeling certain data structure invariants of container-like +objects. For example, these three expressions should be equivalent: + + std::distance(c.begin(), c.end()) == 0 + c.begin() == c.end() + c.empty()) + +Many of these issues are avoided if containers always have unknown, symbolic +state, which is what happens when their constructors are treated as opaque. +In the future, we may decide specific containers are "safe" to model through +inlining, or choose to model them directly using checkers instead. + Basics of Implementation ----------------------- @@ -229,31 +260,31 @@ inlined. == Inlining Dynamic Calls == -The -analyzer-ipa option has five different modes: none, basic-inlining, -inlining, dynamic, and dynamic-bifurcate. Under -analyzer-ipa=dynamic, all -dynamic calls are inlined, whether we are certain or not that this will actually -be the definition used at runtime. Under -analyzer-ipa=inlining, only -"near-perfect" devirtualized calls are inlined*, and other dynamic calls are -evaluated conservatively (as if no definition were available). +The -analyzer-config ipa option has five different modes: none, basic-inlining, +inlining, dynamic, and dynamic-bifurcate. Under -analyzer-config ipa=dynamic, +all dynamic calls are inlined, whether we are certain or not that this will +actually be the definition used at runtime. Under -analyzer-config ipa=inlining, +only "near-perfect" devirtualized calls are inlined*, and other dynamic calls +are evaluated conservatively (as if no definition were available). * Currently, no Objective-C messages are not inlined under - -analyzer-ipa=inlining, even if we are reasonably confident of the type of the - receiver. We plan to enable this once we have tested our heuristics more - thoroughly. + -analyzer-config ipa=inlining, even if we are reasonably confident of the type + of the receiver. We plan to enable this once we have tested our heuristics + more thoroughly. -The last option, -analyzer-ipa=dynamic-bifurcate, behaves similarly to +The last option, -analyzer-config ipa=dynamic-bifurcate, behaves similarly to "dynamic", but performs a conservative invalidation in the general virtual case in *addition* to inlining. The details of this are discussed below. -As stated above, -analyzer-ipa=basic-inlining does not inline any C++ member -functions or Objective-C method calls, even if they are non-virtual or can be -safely devirtualized. +As stated above, -analyzer-config ipa=basic-inlining does not inline any C++ +member functions or Objective-C method calls, even if they are non-virtual or +can be safely devirtualized. Bifurcation ----------- -ExprEngine::BifurcateCall implements the -analyzer-ipa=dynamic-bifurcate +ExprEngine::BifurcateCall implements the -analyzer-config ipa=dynamic-bifurcate mode. When a call is made on an object with imprecise dynamic type information diff --git a/docs/analyzer/Makefile b/docs/analyzer/Makefile new file mode 100644 index 0000000..14f5e60 --- /dev/null +++ b/docs/analyzer/Makefile @@ -0,0 +1,155 @@ +# Makefile for Sphinx documentation +# + +# You can set these variables from the command line. +SPHINXOPTS = +SPHINXBUILD = sphinx-build +PAPER = +BUILDDIR = _build + +# Internal variables. +PAPEROPT_a4 = -D latex_paper_size=a4 +PAPEROPT_letter = -D latex_paper_size=letter +ALLSPHINXOPTS = -d $(BUILDDIR)/doctrees $(PAPEROPT_$(PAPER)) $(SPHINXOPTS) . +# the i18n builder cannot share the environment and doctrees with the others +I18NSPHINXOPTS = $(PAPEROPT_$(PAPER)) $(SPHINXOPTS) . + +.PHONY: help clean html dirhtml singlehtml pickle json htmlhelp qthelp devhelp epub latex latexpdf text man changes linkcheck doctest gettext + +default: html + +help: + @echo "Please use \`make <target>' where <target> is one of" + @echo " html to make standalone HTML files" + @echo " dirhtml to make HTML files named index.html in directories" + @echo " singlehtml to make a single large HTML file" + @echo " pickle to make pickle files" + @echo " json to make JSON files" + @echo " htmlhelp to make HTML files and a HTML help project" + @echo " qthelp to make HTML files and a qthelp project" + @echo " devhelp to make HTML files and a Devhelp project" + @echo " epub to make an epub" + @echo " latex to make LaTeX files, you can set PAPER=a4 or PAPER=letter" + @echo " latexpdf to make LaTeX files and run them through pdflatex" + @echo " text to make text files" + @echo " man to make manual pages" + @echo " texinfo to make Texinfo files" + @echo " info to make Texinfo files and run them through makeinfo" + @echo " gettext to make PO message catalogs" + @echo " changes to make an overview of all changed/added/deprecated items" + @echo " linkcheck to check all external links for integrity" + @echo " doctest to run all doctests embedded in the documentation (if enabled)" + +clean: + -rm -rf $(BUILDDIR)/* + +html: + $(SPHINXBUILD) -b html $(ALLSPHINXOPTS) $(BUILDDIR)/html + @echo + @echo "Build finished. The HTML pages are in $(BUILDDIR)/html." + +dirhtml: + $(SPHINXBUILD) -b dirhtml $(ALLSPHINXOPTS) $(BUILDDIR)/dirhtml + @echo + @echo "Build finished. The HTML pages are in $(BUILDDIR)/dirhtml." + +singlehtml: + $(SPHINXBUILD) -b singlehtml $(ALLSPHINXOPTS) $(BUILDDIR)/singlehtml + @echo + @echo "Build finished. The HTML page is in $(BUILDDIR)/singlehtml." + +pickle: + $(SPHINXBUILD) -b pickle $(ALLSPHINXOPTS) $(BUILDDIR)/pickle + @echo + @echo "Build finished; now you can process the pickle files." + +json: + $(SPHINXBUILD) -b json $(ALLSPHINXOPTS) $(BUILDDIR)/json + @echo + @echo "Build finished; now you can process the JSON files." + +htmlhelp: + $(SPHINXBUILD) -b htmlhelp $(ALLSPHINXOPTS) $(BUILDDIR)/htmlhelp + @echo + @echo "Build finished; now you can run HTML Help Workshop with the" \ + ".hhp project file in $(BUILDDIR)/htmlhelp." + +qthelp: + $(SPHINXBUILD) -b qthelp $(ALLSPHINXOPTS) $(BUILDDIR)/qthelp + @echo + @echo "Build finished; now you can run "qcollectiongenerator" with the" \ + ".qhcp project file in $(BUILDDIR)/qthelp, like this:" + @echo "# qcollectiongenerator $(BUILDDIR)/qthelp/ClangStaticAnalyzer.qhcp" + @echo "To view the help file:" + @echo "# assistant -collectionFile $(BUILDDIR)/qthelp/ClangStaticAnalyzer.qhc" + +devhelp: + $(SPHINXBUILD) -b devhelp $(ALLSPHINXOPTS) $(BUILDDIR)/devhelp + @echo + @echo "Build finished." + @echo "To view the help file:" + @echo "# mkdir -p $$HOME/.local/share/devhelp/ClangStaticAnalyzer" + @echo "# ln -s $(BUILDDIR)/devhelp $$HOME/.local/share/devhelp/ClangStaticAnalyzer" + @echo "# devhelp" + +epub: + $(SPHINXBUILD) -b epub $(ALLSPHINXOPTS) $(BUILDDIR)/epub + @echo + @echo "Build finished. The epub file is in $(BUILDDIR)/epub." + +latex: + $(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex + @echo + @echo "Build finished; the LaTeX files are in $(BUILDDIR)/latex." + @echo "Run \`make' in that directory to run these through (pdf)latex" \ + "(use \`make latexpdf' here to do that automatically)." + +latexpdf: + $(SPHINXBUILD) -b latex $(ALLSPHINXOPTS) $(BUILDDIR)/latex + @echo "Running LaTeX files through pdflatex..." + $(MAKE) -C $(BUILDDIR)/latex all-pdf + @echo "pdflatex finished; the PDF files are in $(BUILDDIR)/latex." + +text: + $(SPHINXBUILD) -b text $(ALLSPHINXOPTS) $(BUILDDIR)/text + @echo + @echo "Build finished. The text files are in $(BUILDDIR)/text." + +man: + $(SPHINXBUILD) -b man $(ALLSPHINXOPTS) $(BUILDDIR)/man + @echo + @echo "Build finished. The manual pages are in $(BUILDDIR)/man." + +texinfo: + $(SPHINXBUILD) -b texinfo $(ALLSPHINXOPTS) $(BUILDDIR)/texinfo + @echo + @echo "Build finished. The Texinfo files are in $(BUILDDIR)/texinfo." + @echo "Run \`make' in that directory to run these through makeinfo" \ + "(use \`make info' here to do that automatically)." + +info: + $(SPHINXBUILD) -b texinfo $(ALLSPHINXOPTS) $(BUILDDIR)/texinfo + @echo "Running Texinfo files through makeinfo..." + make -C $(BUILDDIR)/texinfo info + @echo "makeinfo finished; the Info files are in $(BUILDDIR)/texinfo." + +gettext: + $(SPHINXBUILD) -b gettext $(I18NSPHINXOPTS) $(BUILDDIR)/locale + @echo + @echo "Build finished. The message catalogs are in $(BUILDDIR)/locale." + +changes: + $(SPHINXBUILD) -b changes $(ALLSPHINXOPTS) $(BUILDDIR)/changes + @echo + @echo "The overview file is in $(BUILDDIR)/changes." + +linkcheck: + $(SPHINXBUILD) -b linkcheck $(ALLSPHINXOPTS) $(BUILDDIR)/linkcheck + @echo + @echo "Link check complete; look for any errors in the above output " \ + "or in $(BUILDDIR)/linkcheck/output.txt." + +doctest: + $(SPHINXBUILD) -b doctest $(ALLSPHINXOPTS) $(BUILDDIR)/doctest + @echo "Testing of doctests in the sources finished, look at the " \ + "results in $(BUILDDIR)/doctest/output.txt." diff --git a/docs/analyzer/RegionStore.txt b/docs/analyzer/RegionStore.txt new file mode 100644 index 0000000..5d37cf7 --- /dev/null +++ b/docs/analyzer/RegionStore.txt @@ -0,0 +1,171 @@ +The analyzer "Store" represents the contents of memory regions. It is an opaque +functional data structure stored in each ProgramState; the only class that can +modify the store is its associated StoreManager. + +Currently (Feb. 2013), the only StoreManager implementation being used is +RegionStoreManager. This store records bindings to memory regions using a "base +region + offset" key. (This allows `*p` and `p[0]` to map to the same location, +among other benefits.) + +Regions are grouped into "clusters", which roughly correspond to "regions with +the same base region". This allows certain operations to be more efficient, +such as invalidation. + +Regions that do not have a known offset use a special "symbolic" offset. These +keys store both the original region, and the "concrete offset region" -- the +last region whose offset is entirely concrete. (For example, in the expression +`foo.bar[1][i].baz`, the concrete offset region is the array `foo.bar[1]`, +since that has a known offset from the start of the top-level `foo` struct.) + + +Binding Invalidation +==================== + +Supporting both concrete and symbolic offsets makes things a bit tricky. Here's +an example: + + foo[0] = 0; + foo[1] = 1; + foo[i] = i; + +After the third assignment, nothing can be said about the value of `foo[0]`, +because `foo[i]` may have overwritten it! Thus, *binding to a region with a +symbolic offset invalidates the entire concrete offset region.* We know +`foo[i]` is somewhere within `foo`, so we don't have to invalidate anything +else, but we do have to be conservative about all other bindings within `foo`. + +Continuing the example: + + foo[i] = i; + foo[0] = 0; + +After this latest assignment, nothing can be said about the value of `foo[i]`, +because `foo[0]` may have overwritten it! *Binding to a region R with a +concrete offset invalidates any symbolic offset bindings whose concrete offset +region is a super-region **or** sub-region of R.* All we know about `foo[i]` is +that it is somewhere within `foo`, so changing *anything* within `foo` might +change `foo[i]`, and changing *all* of `foo` (or its base region) will +*definitely* change `foo[i]`. + +This logic could be improved by using the current constraints on `i`, at the +cost of speed. The latter case could also be improved by matching region kinds, +i.e. changing `foo[0].a` is unlikely to affect `foo[i].b`, no matter what `i` +is. + +For more detail, read through RegionStoreManager::removeSubRegionBindings in +RegionStore.cpp. + + +ObjCIvarRegions +=============== + +Objective-C instance variables require a bit of special handling. Like struct +fields, they are not base regions, and when their parent object region is +invalidated, all the instance variables must be invalidated as well. However, +they have no concrete compile-time offsets (in the modern, "non-fragile" +runtime), and so cannot easily be represented as an offset from the start of +the object in the analyzer. Moreover, this means that invalidating a single +instance variable should *not* invalidate the rest of the object, since unlike +struct fields or array elements there is no way to perform pointer arithmetic +to access another instance variable. + +Consequently, although the base region of an ObjCIvarRegion is the entire +object, RegionStore offsets are computed from the start of the instance +variable. Thus it is not valid to assume that all bindings with non-symbolic +offsets start from the base region! + + +Region Invalidation +=================== + +Unlike binding invalidation, region invalidation occurs when the entire +contents of a region may have changed---say, because it has been passed to a +function the analyzer can model, like memcpy, or because its address has +escaped, usually as an argument to an opaque function call. In these cases we +need to throw away not just all bindings within the region itself, but within +its entire cluster, since neighboring regions may be accessed via pointer +arithmetic. + +Region invalidation typically does even more than this, however. Because it +usually represents the complete escape of a region from the analyzer's model, +its *contents* must also be transitively invalidated. (For example, if a region +'p' of type 'int **' is invalidated, the contents of '*p' and '**p' may have +changed as well.) The algorithm that traverses this transitive closure of +accessible regions is known as ClusterAnalysis, and is also used for finding +all live bindings in the store (in order to throw away the dead ones). The name +"ClusterAnalysis" predates the cluster-based organization of bindings, but +refers to the same concept: during invalidation and liveness analysis, all +bindings within a cluster must be treated in the same way for a conservative +model of program behavior. + + +Default Bindings +================ + +Most bindings in RegionStore are simple scalar values -- integers and pointers. +These are known as "Direct" bindings. However, RegionStore supports a second +type of binding called a "Default" binding. These are used to provide values to +all the elements of an aggregate type (struct or array) without having to +explicitly specify a binding for each individual element. + +When there is no Direct binding for a particular region, the store manager +looks at each super-region in turn to see if there is a Default binding. If so, +this value is used as the value of the original region. The search ends when +the base region is reached, at which point the RegionStore will pick an +appropriate default value for the region (usually a symbolic value, but +sometimes zero, for static data, or "uninitialized", for stack variables). + + int manyInts[10]; + manyInts[1] = 42; // Creates a Direct binding for manyInts[1]. + print(manyInts[1]); // Retrieves the Direct binding for manyInts[1]; + print(manyInts[0]); // There is no Direct binding for manyInts[1]. + // Is there a Default binding for the entire array? + // There is not, but it is a stack variable, so we use + // "uninitialized" as the default value (and emit a + // diagnostic!). + +NOTE: The fact that bindings are stored as a base region plus an offset limits +the Default Binding strategy, because in C aggregates can contain other +aggregates. In the current implementation of RegionStore, there is no way to +distinguish a Default binding for an entire aggregate from a Default binding +for the sub-aggregate at offset 0. + + +Lazy Bindings (LazyCompoundVal) +=============================== + +RegionStore implements an optimization for copying aggregates (structs and +arrays) called "lazy bindings", implemented using a special SVal called +LazyCompoundVal. When the store is asked for the "binding" for an entire +aggregate (i.e. for an lvalue-to-rvalue conversion), it returns a +LazyCompoundVal instead. When this value is then stored into a variable, it is +bound as a Default value. This makes copying arrays and structs much cheaper +than if they had required memberwise access. + +Under the hood, a LazyCompoundVal is implemented as a uniqued pair of (region, +store), representing "the value of the region during this 'snapshot' of the +store". This has important implications for any sort of liveness or +reachability analysis, which must take the bindings in the old store into +account. + +Retrieving a value from a lazy binding happens in the same way as any other +Default binding: since there is no direct binding, the store manager falls back +to super-regions to look for an appropriate default binding. LazyCompoundVal +differs from a normal default binding, however, in that it contains several +different values, instead of one value that will appear several times. Because +of this, the store manager has to reconstruct the subregion chain on top of the +LazyCompoundVal region, and look up *that* region in the previous store. + +Here's a concrete example: + + CGPoint p; + p.x = 42; // A Direct binding is made to the FieldRegion 'p.x'. + CGPoint p2 = p; // A LazyCompoundVal is created for 'p', along with a + // snapshot of the current store state. This value is then + // used as a Default binding for the VarRegion 'p2'. + return p2.x; // The binding for FieldRegion 'p2.x' is requested. + // There is no Direct binding, so we look for a Default + // binding to 'p2' and find the LCV. + // Because it's an LCV, we look at our requested region + // and see that it's the '.x' field. We ask for the value + // of 'p.x' within the snapshot, and get back 42. diff --git a/docs/analyzer/conf.py b/docs/analyzer/conf.py new file mode 100644 index 0000000..dff9610 --- /dev/null +++ b/docs/analyzer/conf.py @@ -0,0 +1,246 @@ +# -*- coding: utf-8 -*- +# +# Clang Static Analyzer documentation build configuration file, created by +# sphinx-quickstart on Wed Jan 2 15:54:28 2013. +# +# This file is execfile()d with the current directory set to its containing dir. +# +# Note that not all possible configuration values are present in this +# autogenerated file. +# +# All configuration values have a default; values that are commented out +# serve to show the default. + +import sys, os + +# If extensions (or modules to document with autodoc) are in another directory, +# add these directories to sys.path here. If the directory is relative to the +# documentation root, use os.path.abspath to make it absolute, like shown here. +#sys.path.insert(0, os.path.abspath('.')) + +# -- General configuration ----------------------------------------------------- + +# If your documentation needs a minimal Sphinx version, state it here. +#needs_sphinx = '1.0' + +# Add any Sphinx extension module names here, as strings. They can be extensions +# coming with Sphinx (named 'sphinx.ext.*') or your custom ones. +extensions = ['sphinx.ext.todo', 'sphinx.ext.mathjax'] + +# Add any paths that contain templates here, relative to this directory. +templates_path = ['_templates'] + +# The suffix of source filenames. +source_suffix = '.rst' + +# The encoding of source files. +#source_encoding = 'utf-8-sig' + +# The master toctree document. +master_doc = 'index' + +# General information about the project. +project = u'Clang Static Analyzer' +copyright = u'2013, Analyzer Team' + +# The version info for the project you're documenting, acts as replacement for +# |version| and |release|, also used in various other places throughout the +# built documents. +# +# The short X.Y version. +version = '3.3' +# The full version, including alpha/beta/rc tags. +release = '3.3' + +# The language for content autogenerated by Sphinx. Refer to documentation +# for a list of supported languages. +#language = None + +# There are two options for replacing |today|: either, you set today to some +# non-false value, then it is used: +#today = '' +# Else, today_fmt is used as the format for a strftime call. +#today_fmt = '%B %d, %Y' + +# List of patterns, relative to source directory, that match files and +# directories to ignore when looking for source files. +exclude_patterns = ['_build'] + +# The reST default role (used for this markup: `text`) to use for all documents. +#default_role = None + +# If true, '()' will be appended to :func: etc. cross-reference text. +#add_function_parentheses = True + +# If true, the current module name will be prepended to all description +# unit titles (such as .. function::). +#add_module_names = True + +# If true, sectionauthor and moduleauthor directives will be shown in the +# output. They are ignored by default. +#show_authors = False + +# The name of the Pygments (syntax highlighting) style to use. +pygments_style = 'sphinx' + +# A list of ignored prefixes for module index sorting. +#modindex_common_prefix = [] + + +# -- Options for HTML output --------------------------------------------------- + +# The theme to use for HTML and HTML Help pages. See the documentation for +# a list of builtin themes. +html_theme = 'haiku' + +# Theme options are theme-specific and customize the look and feel of a theme +# further. For a list of options available for each theme, see the +# documentation. +#html_theme_options = {} + +# Add any paths that contain custom themes here, relative to this directory. +#html_theme_path = [] + +# The name for this set of Sphinx documents. If None, it defaults to +# "<project> v<release> documentation". +#html_title = None + +# A shorter title for the navigation bar. Default is the same as html_title. +#html_short_title = None + +# The name of an image file (relative to this directory) to place at the top +# of the sidebar. +#html_logo = None + +# The name of an image file (within the static path) to use as favicon of the +# docs. This file should be a Windows icon file (.ico) being 16x16 or 32x32 +# pixels large. +#html_favicon = None + +# Add any paths that contain custom static files (such as style sheets) here, +# relative to this directory. They are copied after the builtin static files, +# so a file named "default.css" will overwrite the builtin "default.css". +html_static_path = [] + +# If not '', a 'Last updated on:' timestamp is inserted at every page bottom, +# using the given strftime format. +#html_last_updated_fmt = '%b %d, %Y' + +# If true, SmartyPants will be used to convert quotes and dashes to +# typographically correct entities. +#html_use_smartypants = True + +# Custom sidebar templates, maps document names to template names. +#html_sidebars = {} + +# Additional templates that should be rendered to pages, maps page names to +# template names. +#html_additional_pages = {} + +# If false, no module index is generated. +#html_domain_indices = True + +# If false, no index is generated. +#html_use_index = True + +# If true, the index is split into individual pages for each letter. +#html_split_index = False + +# If true, links to the reST sources are added to the pages. +#html_show_sourcelink = True + +# If true, "Created using Sphinx" is shown in the HTML footer. Default is True. +#html_show_sphinx = True + +# If true, "(C) Copyright ..." is shown in the HTML footer. Default is True. +#html_show_copyright = True + +# If true, an OpenSearch description file will be output, and all pages will +# contain a <link> tag referring to it. The value of this option must be the +# base URL from which the finished HTML is served. +#html_use_opensearch = '' + +# This is the file name suffix for HTML files (e.g. ".xhtml"). +#html_file_suffix = None + +# Output file base name for HTML help builder. +htmlhelp_basename = 'ClangStaticAnalyzerdoc' + + +# -- Options for LaTeX output -------------------------------------------------- + +latex_elements = { +# The paper size ('letterpaper' or 'a4paper'). +#'papersize': 'letterpaper', + +# The font size ('10pt', '11pt' or '12pt'). +#'pointsize': '10pt', + +# Additional stuff for the LaTeX preamble. +#'preamble': '', +} + +# Grouping the document tree into LaTeX files. List of tuples +# (source start file, target name, title, author, documentclass [howto/manual]). +latex_documents = [ + ('index', 'ClangStaticAnalyzer.tex', u'Clang Static Analyzer Documentation', + u'Analyzer Team', 'manual'), +] + +# The name of an image file (relative to this directory) to place at the top of +# the title page. +#latex_logo = None + +# For "manual" documents, if this is true, then toplevel headings are parts, +# not chapters. +#latex_use_parts = False + +# If true, show page references after internal links. +#latex_show_pagerefs = False + +# If true, show URL addresses after external links. +#latex_show_urls = False + +# Documents to append as an appendix to all manuals. +#latex_appendices = [] + +# If false, no module index is generated. +#latex_domain_indices = True + + +# -- Options for manual page output -------------------------------------------- + +# One entry per manual page. List of tuples +# (source start file, name, description, authors, manual section). +man_pages = [ + ('index', 'clangstaticanalyzer', u'Clang Static Analyzer Documentation', + [u'Analyzer Team'], 1) +] + +# If true, show URL addresses after external links. +#man_show_urls = False + + +# -- Options for Texinfo output ------------------------------------------------ + +# Grouping the document tree into Texinfo files. List of tuples +# (source start file, target name, title, author, +# dir menu entry, description, category) +texinfo_documents = [ + ('index', 'ClangStaticAnalyzer', u'Clang Static Analyzer Documentation', + u'Analyzer Team', 'ClangStaticAnalyzer', 'One line description of project.', + 'Miscellaneous'), +] + +# Documents to append as an appendix to all manuals. +#texinfo_appendices = [] + +# If false, no module index is generated. +#texinfo_domain_indices = True + +# How to display URL addresses: 'footnote', 'no', or 'inline'. +#texinfo_show_urls = 'footnote' + + +# Example configuration for intersphinx: refer to the Python standard library. +intersphinx_mapping = {'http://docs.python.org/': None} diff --git a/docs/analyzer/debug-checks.txt b/docs/analyzer/debug-checks.txt deleted file mode 100644 index 6ac451f..0000000 --- a/docs/analyzer/debug-checks.txt +++ /dev/null @@ -1,89 +0,0 @@ -The analyzer contains a number of checkers which can aid in debugging. Enable them by using the "-analyzer-checker=" flag, followed by the name of the checker. - -General Analysis Dumpers -======================== -These checkers are used to dump the results of various infrastructural analyses to stderr. Some checkers also have "view" variants, which will display a graph using a 'dot' format viewer (such as Graphviz on OS X) instead. - -- debug.DumpCallGraph, debug.ViewCallGraph: Show the call graph generated for the current translation unit. This is used to determine the order in which to analyze functions when inlining is enabled. -- debug.DumpCFG, debug.ViewCFG: Show the CFG generated for each top-level function being analyzed. -- debug.DumpDominators: Shows the dominance tree for the CFG of each top-level function. -- debug.DumpLiveVars: Show the results of live variable analysis for each top-level function being analyzed. - - -Path Tracking -============= -These checkers print information about the path taken by the analyzer engine. - -- debug.DumpCalls: Prints out every function or method call encountered during a path traversal. This is indented to show the call stack, but does NOT do any special handling of branches, meaning different paths could end up interleaved. -- debug.DumpTraversal: Prints the name of each branch statement encountered during a path traversal ("IfStmt", "WhileStmt", etc). Currently used to check whether the analysis engine is doing BFS or DFS. - - -State Checking -============== -These checkers will print out information about the analyzer state in the form of analysis warnings. They are intended for use with the -verify functionality in regression tests. - -- debug.TaintTest: Prints out the word "tainted" for every expression that carries taint. At the time of this writing, taint was only introduced by the checks under experimental.security.taint.TaintPropagation; this checker may eventually move to the security.taint package. -- debug.ExprInspection: Responds to certain function calls, which are modeled after builtins. These function calls should affect the program state other than the evaluation of their arguments; to use them, you will need to declare them within your test file. The available functions are described below. - -(FIXME: debug.ExprInspection should probably be renamed, since it no longer only inspects expressions.) - - -ExprInspection checks ---------------------- - -- void clang_analyzer_eval(bool); - -Prints TRUE if the argument is known to have a non-zero value, - FALSE if the argument is known to have a zero or null value, and - UNKNOWN if the argument isn't sufficiently constrained on this path. -You can use this to test other values by using expressions like "x == 5". -Note that this functionality is currently DISABLED in inlined functions, -since different calls to the same inlined function could provide different -information, making it difficult to write proper -verify directives. - -In C, the argument can be typed as 'int' or as '_Bool'. - -Example usage: - clang_analyzer_eval(x); // expected-warning{{UNKNOWN}} - if (!x) return; - clang_analyzer_eval(x); // expected-warning{{TRUE}} - - -- void clang_analyzer_checkInlined(bool); - -If a call occurs within an inlined function, prints TRUE or FALSE according to -the value of its argument. If a call occurs outside an inlined function, -nothing is printed. - -The intended use of this checker is to assert that a function is inlined at -least once (by passing 'true' and expecting a warning), or to assert that a -function is never inlined (by passing 'false' and expecting no warning). The -argument is technically unnecessary but is intended to clarify intent. - -You might wonder why we can't print TRUE if a function is ever inlined and -FALSE if it is not. The problem is that any inlined function could conceivably -also be analyzed as a top-level function (in which case both TRUE and FALSE -would be printed), depending on the value of the -analyzer-inlining option. - -In C, the argument can be typed as 'int' or as '_Bool'. - -Example usage: - int inlined() { - clang_analyzer_checkInlined(true); // expected-warning{{TRUE}} - return 42; - } - - void topLevel() { - clang_analyzer_checkInlined(false); // no-warning (not inlined) - int value = inlined(); - // This assertion will not be valid if the previous call was not inlined. - clang_analyzer_eval(value == 42); // expected-warning{{TRUE}} - } - - - -Statistics -========== -The debug.Stats checker collects various information about the analysis of each function, such as how many blocks were reached and if the analyzer timed out. - -There is also an additional -analyzer-stats flag, which enables various statistics within the analyzer engine. Note the Stats checker (which produces at least one bug report per function) may actually change the values reported by -analyzer-stats. diff --git a/docs/analyzer/index.rst b/docs/analyzer/index.rst new file mode 100644 index 0000000..767567f --- /dev/null +++ b/docs/analyzer/index.rst @@ -0,0 +1,23 @@ +.. Clang Static Analyzer documentation master file, created by + sphinx-quickstart on Wed Jan 2 15:54:28 2013. + You can adapt this file completely to your liking, but it should at least + contain the root `toctree` directive. + +Welcome to Clang Static Analyzer's documentation! +================================================= + +Contents: + +.. toctree:: + :maxdepth: 2 + + DebugChecks + + +Indices and tables +================== + +* :ref:`genindex` +* :ref:`modindex` +* :ref:`search` + diff --git a/docs/analyzer/make.bat b/docs/analyzer/make.bat new file mode 100644 index 0000000..6c2c63d --- /dev/null +++ b/docs/analyzer/make.bat @@ -0,0 +1,190 @@ +@ECHO OFF + +REM Command file for Sphinx documentation + +if "%SPHINXBUILD%" == "" ( + set SPHINXBUILD=sphinx-build +) +set BUILDDIR=_build +set ALLSPHINXOPTS=-d %BUILDDIR%/doctrees %SPHINXOPTS% . +set I18NSPHINXOPTS=%SPHINXOPTS% . +if NOT "%PAPER%" == "" ( + set ALLSPHINXOPTS=-D latex_paper_size=%PAPER% %ALLSPHINXOPTS% + set I18NSPHINXOPTS=-D latex_paper_size=%PAPER% %I18NSPHINXOPTS% +) + +if "%1" == "" goto help + +if "%1" == "help" ( + :help + echo.Please use `make ^<target^>` where ^<target^> is one of + echo. html to make standalone HTML files + echo. dirhtml to make HTML files named index.html in directories + echo. singlehtml to make a single large HTML file + echo. pickle to make pickle files + echo. json to make JSON files + echo. htmlhelp to make HTML files and a HTML help project + echo. qthelp to make HTML files and a qthelp project + echo. devhelp to make HTML files and a Devhelp project + echo. epub to make an epub + echo. latex to make LaTeX files, you can set PAPER=a4 or PAPER=letter + echo. text to make text files + echo. man to make manual pages + echo. texinfo to make Texinfo files + echo. gettext to make PO message catalogs + echo. changes to make an overview over all changed/added/deprecated items + echo. linkcheck to check all external links for integrity + echo. doctest to run all doctests embedded in the documentation if enabled + goto end +) + +if "%1" == "clean" ( + for /d %%i in (%BUILDDIR%\*) do rmdir /q /s %%i + del /q /s %BUILDDIR%\* + goto end +) + +if "%1" == "html" ( + %SPHINXBUILD% -b html %ALLSPHINXOPTS% %BUILDDIR%/html + if errorlevel 1 exit /b 1 + echo. + echo.Build finished. The HTML pages are in %BUILDDIR%/html. + goto end +) + +if "%1" == "dirhtml" ( + %SPHINXBUILD% -b dirhtml %ALLSPHINXOPTS% %BUILDDIR%/dirhtml + if errorlevel 1 exit /b 1 + echo. + echo.Build finished. The HTML pages are in %BUILDDIR%/dirhtml. + goto end +) + +if "%1" == "singlehtml" ( + %SPHINXBUILD% -b singlehtml %ALLSPHINXOPTS% %BUILDDIR%/singlehtml + if errorlevel 1 exit /b 1 + echo. + echo.Build finished. The HTML pages are in %BUILDDIR%/singlehtml. + goto end +) + +if "%1" == "pickle" ( + %SPHINXBUILD% -b pickle %ALLSPHINXOPTS% %BUILDDIR%/pickle + if errorlevel 1 exit /b 1 + echo. + echo.Build finished; now you can process the pickle files. + goto end +) + +if "%1" == "json" ( + %SPHINXBUILD% -b json %ALLSPHINXOPTS% %BUILDDIR%/json + if errorlevel 1 exit /b 1 + echo. + echo.Build finished; now you can process the JSON files. + goto end +) + +if "%1" == "htmlhelp" ( + %SPHINXBUILD% -b htmlhelp %ALLSPHINXOPTS% %BUILDDIR%/htmlhelp + if errorlevel 1 exit /b 1 + echo. + echo.Build finished; now you can run HTML Help Workshop with the ^ +.hhp project file in %BUILDDIR%/htmlhelp. + goto end +) + +if "%1" == "qthelp" ( + %SPHINXBUILD% -b qthelp %ALLSPHINXOPTS% %BUILDDIR%/qthelp + if errorlevel 1 exit /b 1 + echo. + echo.Build finished; now you can run "qcollectiongenerator" with the ^ +.qhcp project file in %BUILDDIR%/qthelp, like this: + echo.^> qcollectiongenerator %BUILDDIR%\qthelp\ClangStaticAnalyzer.qhcp + echo.To view the help file: + echo.^> assistant -collectionFile %BUILDDIR%\qthelp\ClangStaticAnalyzer.ghc + goto end +) + +if "%1" == "devhelp" ( + %SPHINXBUILD% -b devhelp %ALLSPHINXOPTS% %BUILDDIR%/devhelp + if errorlevel 1 exit /b 1 + echo. + echo.Build finished. + goto end +) + +if "%1" == "epub" ( + %SPHINXBUILD% -b epub %ALLSPHINXOPTS% %BUILDDIR%/epub + if errorlevel 1 exit /b 1 + echo. + echo.Build finished. The epub file is in %BUILDDIR%/epub. + goto end +) + +if "%1" == "latex" ( + %SPHINXBUILD% -b latex %ALLSPHINXOPTS% %BUILDDIR%/latex + if errorlevel 1 exit /b 1 + echo. + echo.Build finished; the LaTeX files are in %BUILDDIR%/latex. + goto end +) + +if "%1" == "text" ( + %SPHINXBUILD% -b text %ALLSPHINXOPTS% %BUILDDIR%/text + if errorlevel 1 exit /b 1 + echo. + echo.Build finished. The text files are in %BUILDDIR%/text. + goto end +) + +if "%1" == "man" ( + %SPHINXBUILD% -b man %ALLSPHINXOPTS% %BUILDDIR%/man + if errorlevel 1 exit /b 1 + echo. + echo.Build finished. The manual pages are in %BUILDDIR%/man. + goto end +) + +if "%1" == "texinfo" ( + %SPHINXBUILD% -b texinfo %ALLSPHINXOPTS% %BUILDDIR%/texinfo + if errorlevel 1 exit /b 1 + echo. + echo.Build finished. The Texinfo files are in %BUILDDIR%/texinfo. + goto end +) + +if "%1" == "gettext" ( + %SPHINXBUILD% -b gettext %I18NSPHINXOPTS% %BUILDDIR%/locale + if errorlevel 1 exit /b 1 + echo. + echo.Build finished. The message catalogs are in %BUILDDIR%/locale. + goto end +) + +if "%1" == "changes" ( + %SPHINXBUILD% -b changes %ALLSPHINXOPTS% %BUILDDIR%/changes + if errorlevel 1 exit /b 1 + echo. + echo.The overview file is in %BUILDDIR%/changes. + goto end +) + +if "%1" == "linkcheck" ( + %SPHINXBUILD% -b linkcheck %ALLSPHINXOPTS% %BUILDDIR%/linkcheck + if errorlevel 1 exit /b 1 + echo. + echo.Link check complete; look for any errors in the above output ^ +or in %BUILDDIR%/linkcheck/output.txt. + goto end +) + +if "%1" == "doctest" ( + %SPHINXBUILD% -b doctest %ALLSPHINXOPTS% %BUILDDIR%/doctest + if errorlevel 1 exit /b 1 + echo. + echo.Testing of doctests in the sources finished, look at the ^ +results in %BUILDDIR%/doctest/output.txt. + goto end +) + +:end |
