20 ms·

Why Don't Software Developers Use Static Analysis Tools to Find Bugs?

107 points by cpeterso 11y ago

kwhitefoot 11y ago
For the same reason my colleagues won't use contracts: they get in the way of the job you are trying to do today. I have explained over and over again that they are an investment that pays off by helping to avoid having to fix bugs in the future but most people discount the value of a lack of future bugs so heavily that they feel that the convenience of not being nagged by the machine is worth it.
moru0011 11y ago
no button in the IDE :)
- anon1385 11y ago
  Have you used one of the popular IDEs recently (Visual Studio, Xcode etc)? It's built into most these days. Everybody I know who actually uses static analysis does so because it's built into their IDE and very easy to use.
  - kybernetyk 11y ago
    In Xcode at least there's a 'Build & Analyze" command (cmd-shift-b). What I like to do is to force a deep analyze on every build. Takes a little longer to build but at least I catch some bugs when I introduce them.
    - maccard 11y ago
      My compile is already 10 minutes, I don't want to add a static analysis pass to every build thanks.
      - kybernetyk 11y ago
        Don't do a full build every time then.
      - andymcsherry 11y ago
        I would wager 10 minutes is far from the norm for most user's builds in X-Code. That being said, analyzing every build seems a bit much.
        kybernetyk 11y ago
        Analyzing is incremental too. If you only change foo.cpp then only foo.cpp will be analyzed.
      - 72deluxe 11y ago
        Why is your compile 10 minutes? Mine is about 20 seconds for ~82000 lines of C++ (not comments), with 43000 header lines and 7669 lines of C (according to cloc), and that's on a 2008 quad-core Xeon Mac Pro. Do you not parallel build?
        Ono-Sendai 11y ago
        He probably has more source code.
        maccard 11y ago
        Parallel build with 40 cores(2x intel xeons), 32GB ram using Visual Studio. According to cloc, we have 11k C++ files. 18k C/c++ header, with 4.5M lines of C++, and 1.5M C/C++ Header, and 700K C. We use a unity build to speed it up (to 10 minutes) without it, it's roughly 40 minutes.
        72deluxe 11y ago
        Haha my project is tiny, yours is mental haha that's bonkers
        kasey_junk 11y ago
        130K LOC is an extremely small project. 10 minute compile steps are less common than they used to be, but early in my career I would have dreamed for 10 minute compile cycles.
      - AndreyKarpov 11y ago
        I would like to put my two cents. 1) PVS-Studio can instead be set to run in background immediately after the edited code has been successfully compiled. 2) PVS-Studio integrates with IncrediBuild. And soon we will publish an article about it. A little spoiler. :)
      - verinus 11y ago
        well then run it on CI/daily builds.
        maccard 11y ago
        That's fine, but making it a default option for all developers on every build wouldn't be suitable for us is what I was saying. I'm fine if it's run on the CI servers, or even if it's a requirement that I submit a "clean" static analysis report with my changes, which can be done by giving me the option (like XCode/Visual studio already do).
  - AndreyKarpov 11y ago
    Also, I recommend you to try Incremental analysis mode in PVS-Studio. It corrects on its own and doesn't distract programmer. http://www.viva64.com/en/b/0305/#ID0ECLDK http://www.viva64.com/en/b/0305/#ID0ECLDK
nkurz 11y ago
Nice paper from 2013, but I was confused at first how it related to the blog. This paragraph just after the abstract explained, but I missed it the first time through: The original article in PDF[1] was published at the NCSU COE People site. It was translated and published at our blog by the authors' permission. At the end of the article[2], we added a short section about the PVS-Studio analyzer, where we describe which of the recommendations suggested in the article are or aren't implemented in our tool and why. [1] http://people.engr.ncsu.edu/ermurph3/papers/icse13b.pdf http://people.engr.ncsu.edu/ermurph3/papers/icse13b.pdf [2] http://www.viva64.com/en/b/0335/#ID0EU4CK http://www.viva64.com/en/b/0335/#ID0EU4CK
- smarks 11y ago
  Yes, I also found this quite confusing. The way this paper was attributed seems quite sloppy. It mentions previous publication at the "NCSU COE People site" and gives a link, but omits mention that this paper was originally presented at the International Conference on Software Engineering (ICSE 2013): http://2013.icse-conferences.org/index.html http://2013.icse-conferences.org/index.html These notes shouldn't have been tacked onto the abstract. Instead they should have been clearly separated from the paper itself. In addition, the PVS Studio team "added a short section" which appears as if it were a modification to the paper, and and it also appears in the augmented table of contents. If one is not reading carefully, or if the section heading has scrolled of the top of the screen, one might be misled into thinking the "added section" was also authored by Johnson et. al. instead of by the PVS Studio team. The "added short section" should also have been published entirely separately.
inglor 11y ago
ReSharper (on C# in Visual Studio) and Visual Studio itself do perform static analysis and find out bugs like "possible multiple enumerations of IEnumerable" for you pretty readily, developers also use code coverage tools. Still, good article.
- zamalek 11y ago
  ReSharper does lightweight static analysis - I would venture to go as far as to place it into the "code smell analysis" category. Using something like Code Contracts, properly, drastically changes your outlook on static analysis. ReSharper: you've enumerated this enumerable multiple times. This if statement is redundant. Basically stuff within the scope of a single method. Code Contracts: you've passed an integer to this function. The function asks that you check that the integer falls into the length of the array that you are also passing in and that it's a multiple of two. Also, the function doesn't promise that it won't return a null value and you are using the result without checking it first. Basically looks at your entire project and can work out code paths across methods. There's worlds of a difference. ReSharper is definitely useful, but doesn't come close to what proper static analysis can do. If you like what ReSharper is doing for your codebase I thoroughly recommend having a look at Code Contracts (it's a free Microsoft Research project).
  - kwhitefoot 11y ago
    The problem with contracts and static analysis is that large projects are often so tangled up by the time that someone (me) applies contracts to them that the static analysis takes days or weeks of execution time. I add the contracts anyway because they really do help find bugs at run time too and also act as executable comments.
  - Alphasite_ 11y ago
    I don't know about code contracts, but IntelliJ does have an equivilent, if less advanced version of these as well, using Java annotations. Although it's mostly used for nullability/taint detection ATM.
deleted 11y ago
[deleted]
derefr 11y ago
I don't know how is why! (And if I learned, then my coworkers wouldn't know how, so until I got everyone else on board, I would be making the bed only to have them jump all over it again.) Don't tell me to hunt down random third-party tools that none of my coworkers has heard of, that I have to convince them to adopt, and which each solve a little (usually overlapping) bit of the problem so I have to run all of them in series. That way leads to madness, and horrible one-off UIs developed by people more concerned with their tool's special-snowflake analysis algorithm than its output. Instead, ship an extensible, plugin-based linter with your language's toolchain (e.g. mix for Elixir, lein for Clojure, etc.) Make its output beautiful. Write one or two simple plugins, and make installing lint-plugins as simple as adding something to the project's dependency file. Then I (and everyone else) will use this stuff.
- maccard 11y ago
  Given that this article is written by/for pvs studio, which works mostly inside visual studio (you can get it to work outside but it seems to require some amount of setup), anyone using visual studio's too chain has a static analysis tool at their disposal. Also, clang has built in static analysis, and I can't speak for gcc.
  - AndreyKarpov 11y ago
    It is simply a conspiracy theory :-) PVS-Studio team doesn't belong to the article somehow. However, we knew about it and took into account.
  - deleted 11y ago
    [deleted]
j_jochem 11y ago
In one of my recent projects, we used SonarQube. I had actually never worked with that tool before. What bothered me most was how it marked things as errors but did not explain _why_ they were wrong. When it comes to code style, there's a lot of room for personal opinion, and this just led to me arguing with the architect about whether something is a false positive or not. That time could have been spent writing actual, working code or more unit tests.
- karlmdavis 11y ago
  I use SonarQube myself and have generally found its rules to make sense after a quick Google, at most. Aside from its code formatting rules, which are just silly. They're easy enough to modify or turn off, though, so there's that.
tunesmith 11y ago
It's possible to ship working dynamically-typed code that is just absolutely littered with problems that static-analysis tools complain about (even to the point of being "accidentally correct"). So then you can spend a bunch of hours making it compliant, and it's a big refactor that takes a while for other people to review/qa/approve, meanwhile the product folks are grousing about the time it's taking away from the sprint when it's not a roadmap feature, and as a programmer you might completely believe it's worth the effort to clean up the code, but you're still having to deal with a lot of friction.
- frobozz 11y ago
  If you had static analysis in from the start, that wouldn't be a problem. If you add static analysis to a messy project, define success thresholds based on the current violation count, and/or disable violation categories that you can live with. The rule then should be "don't make it worse, try to make it a bit better when you can", rather than "don't commit anything to main until the checker says it's perfect".
  - AnimalMuppet 11y ago
    Our approach was, fix the really horrible ones now, and don't add new ones that we care about. Then, as we have time, fix the next-most-horrible ones.
ThePhysicist 11y ago
Very interesting article! I am developing static code analysis tools for Python myself (https://www.quantifiedcode.com https://www.quantifiedcode.com) and have thought a lot about this problem as well. Since we offer a SaaS solution instead of an IDE plugin the boundary conditions are a bit different for us (e.g. we have less strict "realtime" requirements but the feedback time is also longer), but the basic question is the same: Why doesn't everyone use static analysis to improve their code? After having surveyed most of the available static analysis tools I think that part of the answer is that often the tools simply do not provide enough value for developers, especially those analyzing dynamic languages like Python / Ruby / Javascript (for C++/Java the tooling is much better). We are currently trying to change that by developing a new, data-driven approach to code analysis, which (we hope) should improve the quality of the analyses quite a bit and provide better and more actionable feedback. Part of the problem is also cultural of course: People have different ideas about what "good code" is and they usually do not like having their code critiqued. Using an automated tool rather than manual code review to check some aspects of code quality can be beneficial though, since it is normally easier to accept harsh feedback from a machine than a human.
- oellegaard 11y ago
  It looks like it takes quite a while to analyze :-( It just says Waiting for analysis to start (queue position: 46)
geromek 11y ago
I think the reason is fairly simple: even the most evident-no-doubt clear SQL Injection vulnerability found by a SCA tool may never be exploited at all under production (for instance because of a WAF). Then the obvious benefits of static analysis are not that obvious for your employer. Sometimes we forget companies do not want a perfect code or the best possible well designed software but a product that make them earn money. My experience is that developers only use those kind of tools if they are forced to by their QA managers of bounded by contract. Programmers usually don't want to fix or track bugs.
- PinguTS 11y ago
  So, you are saying "Developers don't want to deliver quality."? If that it true, than I don't want to work with them.
  - geromek 11y ago
    I am saying "Developers do not want : 1 - Pay A LOT of money for advanced solutions that are more than AST checkers (hello SonarQube) or big piles of false positives. 2 - Add overhead to their workflows (more than an IDE plugin is harmful, and what happens with those devs not using an IDE?). 3 - Spend time on figuring out if the static analysis results make sense or not, one by one. A typical SCA tool can report hundreds or thousands of occurrences for a certain code base. How are developers going to deal with them?
    - PinguTS 11y ago
      I am from engineering background and not soley a software guy, so forgive me my different view on this topic. I learned, that every error you can fix early on will cost you about 10x to fix in the next stage. All the new principles like Agile have not changed that.
      - glogla 11y ago
        I think the idea is not that it's not worth to fix errors as soon as possible (which it is), but that static analysis tools provide too many false positives and too many non-errors to be useful.
dschiptsov 11y ago
Because neither an advanced type system nor static analysis could catch bugs in program logic?) The benefits of static typing (complie-time checks) are grossly exaggerated. If the claims were true, Java itself and Java projects would be much less buggy.)
- HOLYCOWBATMAN 11y ago
  >The benefits of static typing (complie-time checks) are grossly exaggerated. If the claims were true, Java itself and Java projects would be much less buggy I wouldnt call Java an "advanced type system". Take a look at Idris then try to say that with a straight face: >Because neither an advanced type system nor static analysis could catch bugs in program logic It certainly does if you indeed use an advanced type system.
- amirmc 11y ago
  This reasoning makes no sense to me. It's like: Alice: "Doing X will prevent bugs like Y!" Bob: "Oh, but it does nothing for bugs like Z. I just won't bother at all, then". Why would you not want to try and remove an entire class of bugs if it were within your power to do so? Just look at all the effort companies like Facebook have poured into exactly this kind of problem with things like Hack and Flow (which make use of OCaml).
  - glogla 11y ago
    I think you're missing each other in terms of what static typing you mean. Haskell or ML style static typing is very useful, completely changes the way you do things and gives you many guarantees. C or Java static typing is almost useless with regards to bugs (see null) and serves mostly to annoy you. It has many of extra costs of stronger static typing, but gives you very little of the benefits.
    - taeric 11y ago
      Static analysis is more than just static typing. Notably, it is possible to leverage static analysis for solid gains in reliability against code bases without having to rewrite them to take advantage of a different typing paradigm. To repeat, you can harden a code base without rewriting it by using static analysis tools. This is not as true with static typing.
irascible 11y ago
Because the good ones are too fucking expensive.
raz32dust 11y ago
The problem I have is that there are many cases where the tools are too defensive. If I want to override the tool, I'd typically have to add some annotation in the code to signal to the tool that I am ok with this warning and don't want to see it again. And I, for some reason, just hate adding style checker and static analysis annotations in my code. It just looks ugly to me.
faragon 11y ago
They should. There is no excuse: clang has it for free, Visul Studio, too (Express Editions, since 2013). Also, for Open Source projects Coverity is free.
72deluxe 11y ago
I do! For cheapness, Flawfinder, CPPCheck, and Product > Analyze in xcode (thanks clang) (the walkthroughs in xcode of how they deduced the problem are really great, blue arrows everywhere, very neat). EDIT: Additionally, given the changes in C++11 we should be able to push all the work onto the compiler for checking type problems, remove dangerous operations, dangling pointers, naked new/delete and avoid casting where possible. It would make for bug-free software. I know someone who writes their C++ like it is late 80s C and firstly, it's horrible to read. And secondly, it does really dangerous things.
- roel_v 11y ago
  I refactored some code this week that used realloc to allocate memory for a 'vector' (which was a typedef for float*), and then a loop with additional realloc's to allocate memory for each element in that vector, to end up with a matrix 8| This is code that was written in the last few years, too. Welcome to academia :(
egwor 11y ago
I use IntelliJ for my java development. It has a lot of analysis built in (whilst you're writing code). I'm not sure if there are that many static analysis checks (Findbugs etc) that are missing outside of those real time checks? I can often determine whether someone had used Eclipse or IntelliJ; there tend to be a lot fewer analysis warnings if someone has used IntelliJ (out of the box) => perhaps we need this analysis in real time?
- M4v3R 11y ago
  Don't know about IntelliJ, but XCode does real-time analysis as well, but it also has a mode for deep static analysis, which for example does code path analysis for finding dead code paths, even across methods. This kind of stuff would be hard to perform in real-time.
  - inglor 11y ago
    Why? You'd just keep the code in SSA and diff whenever the user adds code - you need to create the form _once_ but after you've created it diffing it should be reasonably fast - the creation can be done at project creation time and it can be changed on-line and incrementally. I'm not sure if tools actually do it but it definitely sounds possible.
    - danbruc 11y ago
      How would maintaining a SSA representation of the code help detecting dead code paths? Doing so requires reasoning about possible truth values of conditions and is in general equivalent to the halting problem and therefore undecidable. You could only spend the cycles available in real time and that will in a certain number of cases be enough to solve the problem but there will also be instances requiring more cycles and instances being undecidable.
      - inglor 11y ago
        > How would maintaining a SSA representation of the code help detecting dead code paths? Well, if a variable assigned but never appears in a path that might have side effects it's dead. It's only the halting problem if you pretend to catch 100% of cases under all inputs. You can find lots of dead code without it. For more information about the specific technique of DCE under SSA form see http://grothoff.org/christian/teaching/2007/3353/papers/ssa.pdf http://grothoff.org/christian/teaching/2007/3353/papers/ssa....
deleted 11y ago
[deleted]
pmontra 11y ago
I used lint for C some 20 or 25 years ago, then moved to using dynamical languages (Perl, Ruby, JS.) Not much use of static analysis tools for those languages I thought (but for example check https://www.infinum.co/the-capsized-eight/articles/top-8-tools-for-ruby-on-rails-code-optimization-and-cleanup https://www.infinum.co/the-capsized-eight/articles/top-8-too...). I used Java sometimes and took advantage of Netbeans/Eclipse's hints about Java code but I use emacs for everything else (some vim too). I used jslint on a JavaScript project a few months ago. It catched a few things I overlooked, I learned a couple of things (example: it's useless to define a var inside a loop) but it's also very opinionated and insisted that I write code in a way that pleases its author. I had to refactor working code to make most of the warnings go away. I ended up with something that worked as well as the original but was much more complicated to read (at least for me). I stopped using it and regretted making all those changes to the code. There are some configuration switches but nothing that could make it work for me. I should check jshint but unfortunately jslint primed me against that kind of tools. I prefer to catch errors with tests and test coverage tools. They must be used anyway and they bend to me, not the other way around.
- taeric 11y ago
  It is the "opinions enforced with static analysis" that ultimately annoy me with most analysis tools out there. Things that actually cause bugs, I welcome ways of finding them. Chaining all of my variable declarations together... What? The sad thing is that the powerful analysis tools are truly amazing and do find things. They just are not what the majority of people have experience with. That does seem to be changing.
- stevedonovan 11y ago
  Ditto and likewise - same applies to pylint, which must have been the most opinionated piece of software I've ever used. The trouble is that there's some very useful warnings buried in the opinion spew - warnings which would be an error in other languages.
  - falcolas 11y ago
    pylint is also trivially easy to configure to omit most of these stylistic warnings. I say this as someone who took 10 minutes to generate and configure the pylintrc for a new project. After taking this time, pylint has been quite useful.
scotty79 11y ago
Same reason people use email and code html in editors that are barely more capable then notepad. Sophisticated solutions tend to fail from time to time when applied. And when they fail they are tossed aside for simpler more resilient ones.
deleted 11y ago
[deleted]
deleted 11y ago
[deleted]
jokoon 11y ago
I once was told that any compiler warning message act as static analysis. I think static analysis is a complex subject, because it can touch some sensitive subject like programming style and other more expert subjects like compiler back end and how the language defines such and such code behavior. Static analysis should be made more mainstream, it would be such a great way to teach everybody how to write better code, including and especially students.
crdoconnor 11y ago
Mainly because most of the tool reports freely mix critical issues with stuff that is just opinionated bullshit (e.g. 80 character length lines). When the output is as long as your arm and you have pick through it with a fine toothcomb to find the things that matter (and even they aren't necessarily causes of bugs), the whole idea becomes substantially less appealing.
- yeahdude 11y ago
  grep -v
  - rjaco31 11y ago
    if you have to make a dozen of grep to exclude trivial results, it might be a hint there's something wrong with the pertinence of your output or the customizability of your tool
    - yeahdude 11y ago
      From another perspective, hacking often involves making broken things work better.
      - crdoconnor 11y ago
        From yet another perspective: don't use broken tools.
        yeahdude 11y ago
        I keep forgetting this one: don't offer help to complainers.
        crdoconnor 11y ago
        If the help constitutes telling people about this wonderful new tool you've just discovered called grep, perhaps that's for the best.
kushti 11y ago
I don't know tools for Scala/Haskell making me excited, that's why. Would be happy to see something here.
asfa124sfaf 11y ago
This is something that Checkmarx.com (checkmarx.com) does. They recently received substantial investments and seem to be popular.
franzpeterfolz 11y ago
Well, I did it the other way around. When my co-workers drove me crazy. I just launched Findbugs on their Repo/Projects and filed some bugs in the Bugtracker. That is just a matter of 5 Minutes to get them down to the ground and show that they are not that kind of Rockstar-Devs they pretend to be. But never reveal your secret tools! Well, and if they get curious about your magical Bug-Finding-Skills, they are easy to convince to use these tools. Its a kind of marketing.
- omouse 11y ago
  using clonedigger for python I found lots of copy/paste code and surprise! where did we find bugs? right in every spot clonedigger pointed out.
iolothebard 11y ago
Nice advertisement. It's Alt+F11 in Visual Studio. Between that and Resharper, life is good.
- PVS-Studio 11y ago
  Not so simple. Review John Carmack article: http://gamasutra.com/view/news/128836/InDepth_Static_Code_Analysis.php http://gamasutra.com/view/news/128836/InDepth_Static_Code_An...
watmough 11y ago
cl : Command line warning D9040: ignoring option '/analyze'; Code Analysis warnings are not available in this edition of the compiler Ooops.
tosh 11y ago
The Dart analyzer (https://pub.dartlang.org/packages/analyzer https://pub.dartlang.org/packages/analyzer) is used by various IDEs and text editors like IntelliJ, Eclipse, Sublime and Atom to provide semantic autocompletion, documentation and inline warnings/errors.
chimtim 11y ago
Static analysis tools are great for simple bugs. However, most compiler tools already fix these simple bugs. If there is a class of bugs not addressed by a compiler, most developers have a script to catch these. It may not find the harder to detect bugs (such as those arising out of nested calls), but it gets the job done. The complex tools pushed out by the static analysis guys usually has a high false positive rate that at first becomes annoying to use and later is completely ignored. As for more complex bugs, most developers are aware these bugs exist but do not want to fix them immediately. The reason is on many occasions, these bugs represent some bigger problem in the code base that requires significant re-factoring. And applying the quick fix as suggested by the code analysis tool simply buries these problems instead of fixing them the right way.
- AndreyKarpov 11y ago
  Yes, static analyzers mostly catch simple bugs. But it doesn't really matter if a bug is simple or complicated. You see, programmers believe they never make or make very few simple bugs: http://www.viva64.com/en/b/0116/ http://www.viva64.com/en/b/0116/ But they are wrong. They do make quite a lot of them. Here's, for instance, a bug database we have collected and keep updating: http://www.viva64.com/en/examples/ http://www.viva64.com/en/examples/. Moreover, some bugs can take quite a while to find, despite being simple. Here's a nice example: The conclusion is: the bug we had wasted about 50 hours to track was detected at once with the first run of the analyzer and fixed in less than an hour! Source: http://www.viva64.com/en/b/0221/ http://www.viva64.com/en/b/0221/ True, false positives aren't good, but they are not that much trouble. Static analysis tools provide numbers of means to suppress them. At least, we in PVS-Studio do have a lot of false positive suppression mechanisms. But it's a long story, so you'd better refer to the documentation.
AndreyKarpov 11y ago
Parallel Reddit discussion: https://www.reddit.com/r/programming/comments/3b67pi/why_dont_software_developers_use_static_analysis/ https://www.reddit.com/r/programming/comments/3b67pi/why_don...
skrowl 11y ago
Because we already have a better tool for finding bugs: Production users
- AndreyKarpov 11y ago
  Therac-25: https://en.wikipedia.org/wiki/Therac-25 https://en.wikipedia.org/wiki/Therac-25
shavenwarthog2 11y ago
As a Python programmer, I live and die over Pylint. Yes it's annoying to configure it, but it saves me hours every _day_. The two biggest benefits are: - syntax or undefined variables in exception handlers - showing which modules are no longer used, so we can have a clearer import block
- omouse 11y ago
  could you share your pylintrc for others to learn from?
GFK_of_xmaspast 11y ago
It's hard enough sometimes getting people to turn on compiler warnings.
wyldfire 11y ago
We do. (some of us do, anyways). > Mike: "Clang is my favorite. Its built into the compiler. You don't have to invoke anything special." I agree with Mike. I've also used Coverity Static Analysis and various other tools. Some of them are better than others. Also, "-Wall -Wextra" or "-Weverything" are fantastic for a simple first-pass static analysis.
nachiketn 11y ago
Additional work. Developers don't like to deal with false positives. If static analysis tools were like a laser. It's more like a shotgun that throws a bunch of shrapnel. Sure it hits some really difficult to find bugs. But developers don't like to have to go through a long list of warnings that aren't really guaranteed to find a valid bug, especially in the applications' context. For example null checking is good, but is it needed if I know it is never really going to be null? Isn't that arguably extra effort of typing and compiling and couple of extra lines to compute? I think we will truly move to better adoption if: 1) We had better configuration for customizing it for our application. 2) More education among developers about what is the correct way to modify the tool's behaviour to aid their work. Help the tool, help them in return. 3) More tools that do specific and general work. Example tools extremely focused on mobile development but also tools that not just help you with correcting design and coding problems but also security vulnerabilities.
NickNameNick 11y ago
I ended up writing my own for the bespoke language my company uses internally. The lack of tools like java findbugs had been annoying me. Luckily the server side 'workflow' language, and the client side templates are all written in xml, so its trivial to parse. The first version was painfully slow. The second version tracked the range of possible states as it did a depth first search of the AST, and then stored the requirements of each node of the tree before it moved on to the nodes next sibling or parent. That way if another part of the software later called into an equivalent subtree, I could compare the current range of possible states to the requirements of the first node in the subtree and record any mismatches, then move on. It went from taking over a minute to evaluate a fairly trivial app, to parsing the biggest apps my company has ever shipped in 1-2 seconds. I'm sure the technique is quite common. I wish I could remember if I read about it, or applied it from a different context. In any case the exercise was more useful for learning than as a finished product.

107 points by cpeterso 11y ago

For the same reason my colleagues won't use contracts: they get in the way of the job you are trying to do today. I have explained over and over again that they are an investment that pays off by helping to avoid having to fix bugs in the future but most people discount the value of a lack of future bugs so heavily that they feel that the convenience of not being nagged by the machine is worth it.

moru0011 11y ago

no button in the IDE :)

anon1385 11y ago
Have you used one of the popular IDEs recently (Visual Studio, Xcode etc)? It's built into most these days. Everybody I know who actually uses static analysis does so because it's built into their IDE and very easy to use.
- kybernetyk 11y ago
  In Xcode at least there's a 'Build & Analyze" command (cmd-shift-b). What I like to do is to force a deep analyze on every build. Takes a little longer to build but at least I catch some bugs when I introduce them.
  - maccard 11y ago
    My compile is already 10 minutes, I don't want to add a static analysis pass to every build thanks.
    - kybernetyk 11y ago
      Don't do a full build every time then.
    - andymcsherry 11y ago
      I would wager 10 minutes is far from the norm for most user's builds in X-Code. That being said, analyzing every build seems a bit much.
      - kybernetyk 11y ago
        Analyzing is incremental too. If you only change foo.cpp then only foo.cpp will be analyzed.
    - 72deluxe 11y ago
      Why is your compile 10 minutes? Mine is about 20 seconds for ~82000 lines of C++ (not comments), with 43000 header lines and 7669 lines of C (according to cloc), and that's on a 2008 quad-core Xeon Mac Pro. Do you not parallel build?
      - Ono-Sendai 11y ago
        He probably has more source code.
      - maccard 11y ago
        Parallel build with 40 cores(2x intel xeons), 32GB ram using Visual Studio. According to cloc, we have 11k C++ files. 18k C/c++ header, with 4.5M lines of C++, and 1.5M C/C++ Header, and 700K C. We use a unity build to speed it up (to 10 minutes) without it, it's roughly 40 minutes.
        72deluxe 11y ago
        Haha my project is tiny, yours is mental haha that's bonkers
      - kasey_junk 11y ago
        130K LOC is an extremely small project. 10 minute compile steps are less common than they used to be, but early in my career I would have dreamed for 10 minute compile cycles.
    - AndreyKarpov 11y ago
      I would like to put my two cents. 1) PVS-Studio can instead be set to run in background immediately after the edited code has been successfully compiled. 2) PVS-Studio integrates with IncrediBuild. And soon we will publish an article about it. A little spoiler. :)
    - verinus 11y ago
      well then run it on CI/daily builds.
      - maccard 11y ago
        That's fine, but making it a default option for all developers on every build wouldn't be suitable for us is what I was saying. I'm fine if it's run on the CI servers, or even if it's a requirement that I submit a "clean" static analysis report with my changes, which can be done by giving me the option (like XCode/Visual studio already do).
- AndreyKarpov 11y ago
  Also, I recommend you to try Incremental analysis mode in PVS-Studio. It corrects on its own and doesn't distract programmer. http://www.viva64.com/en/b/0305/#ID0ECLDK http://www.viva64.com/en/b/0305/#ID0ECLDK

nkurz 11y ago

Nice paper from 2013, but I was confused at first how it related to the blog. This paragraph just after the abstract explained, but I missed it the first time through: The original article in PDF[1] was published at the NCSU COE People site. It was translated and published at our blog by the authors' permission. At the end of the article[2], we added a short section about the PVS-Studio analyzer, where we describe which of the recommendations suggested in the article are or aren't implemented in our tool and why. [1] http://people.engr.ncsu.edu/ermurph3/papers/icse13b.pdf http://people.engr.ncsu.edu/ermurph3/papers/icse13b.pdf [2] http://www.viva64.com/en/b/0335/#ID0EU4CK http://www.viva64.com/en/b/0335/#ID0EU4CK

smarks 11y ago
Yes, I also found this quite confusing. The way this paper was attributed seems quite sloppy. It mentions previous publication at the "NCSU COE People site" and gives a link, but omits mention that this paper was originally presented at the International Conference on Software Engineering (ICSE 2013): http://2013.icse-conferences.org/index.html http://2013.icse-conferences.org/index.html These notes shouldn't have been tacked onto the abstract. Instead they should have been clearly separated from the paper itself. In addition, the PVS Studio team "added a short section" which appears as if it were a modification to the paper, and and it also appears in the augmented table of contents. If one is not reading carefully, or if the section heading has scrolled of the top of the screen, one might be misled into thinking the "added section" was also authored by Johnson et. al. instead of by the PVS Studio team. The "added short section" should also have been published entirely separately.

inglor 11y ago

ReSharper (on C# in Visual Studio) and Visual Studio itself do perform static analysis and find out bugs like "possible multiple enumerations of IEnumerable" for you pretty readily, developers also use code coverage tools. Still, good article.

zamalek 11y ago
ReSharper does lightweight static analysis - I would venture to go as far as to place it into the "code smell analysis" category. Using something like Code Contracts, properly, drastically changes your outlook on static analysis. ReSharper: you've enumerated this enumerable multiple times. This if statement is redundant. Basically stuff within the scope of a single method. Code Contracts: you've passed an integer to this function. The function asks that you check that the integer falls into the length of the array that you are also passing in and that it's a multiple of two. Also, the function doesn't promise that it won't return a null value and you are using the result without checking it first. Basically looks at your entire project and can work out code paths across methods. There's worlds of a difference. ReSharper is definitely useful, but doesn't come close to what proper static analysis can do. If you like what ReSharper is doing for your codebase I thoroughly recommend having a look at Code Contracts (it's a free Microsoft Research project).
- kwhitefoot 11y ago
  The problem with contracts and static analysis is that large projects are often so tangled up by the time that someone (me) applies contracts to them that the static analysis takes days or weeks of execution time. I add the contracts anyway because they really do help find bugs at run time too and also act as executable comments.
- Alphasite_ 11y ago
  I don't know about code contracts, but IntelliJ does have an equivilent, if less advanced version of these as well, using Java annotations. Although it's mostly used for nullability/taint detection ATM.

deleted 11y ago

[deleted]

derefr 11y ago

I don't know how is why! (And if I learned, then my coworkers wouldn't know how, so until I got everyone else on board, I would be making the bed only to have them jump all over it again.) Don't tell me to hunt down random third-party tools that none of my coworkers has heard of, that I have to convince them to adopt, and which each solve a little (usually overlapping) bit of the problem so I have to run all of them in series. That way leads to madness, and horrible one-off UIs developed by people more concerned with their tool's special-snowflake analysis algorithm than its output. Instead, ship an extensible, plugin-based linter with your language's toolchain (e.g. mix for Elixir, lein for Clojure, etc.) Make its output beautiful. Write one or two simple plugins, and make installing lint-plugins as simple as adding something to the project's dependency file. Then I (and everyone else) will use this stuff.

maccard 11y ago
Given that this article is written by/for pvs studio, which works mostly inside visual studio (you can get it to work outside but it seems to require some amount of setup), anyone using visual studio's too chain has a static analysis tool at their disposal. Also, clang has built in static analysis, and I can't speak for gcc.
- AndreyKarpov 11y ago
  It is simply a conspiracy theory :-) PVS-Studio team doesn't belong to the article somehow. However, we knew about it and took into account.
- deleted 11y ago
  [deleted]

j_jochem 11y ago

In one of my recent projects, we used SonarQube. I had actually never worked with that tool before. What bothered me most was how it marked things as errors but did not explain _why_ they were wrong. When it comes to code style, there's a lot of room for personal opinion, and this just led to me arguing with the architect about whether something is a false positive or not. That time could have been spent writing actual, working code or more unit tests.

karlmdavis 11y ago
I use SonarQube myself and have generally found its rules to make sense after a quick Google, at most. Aside from its code formatting rules, which are just silly. They're easy enough to modify or turn off, though, so there's that.

tunesmith 11y ago

It's possible to ship working dynamically-typed code that is just absolutely littered with problems that static-analysis tools complain about (even to the point of being "accidentally correct"). So then you can spend a bunch of hours making it compliant, and it's a big refactor that takes a while for other people to review/qa/approve, meanwhile the product folks are grousing about the time it's taking away from the sprint when it's not a roadmap feature, and as a programmer you might completely believe it's worth the effort to clean up the code, but you're still having to deal with a lot of friction.

frobozz 11y ago
If you had static analysis in from the start, that wouldn't be a problem. If you add static analysis to a messy project, define success thresholds based on the current violation count, and/or disable violation categories that you can live with. The rule then should be "don't make it worse, try to make it a bit better when you can", rather than "don't commit anything to main until the checker says it's perfect".
- AnimalMuppet 11y ago
  Our approach was, fix the really horrible ones now, and don't add new ones that we care about. Then, as we have time, fix the next-most-horrible ones.

ThePhysicist 11y ago

Very interesting article! I am developing static code analysis tools for Python myself (https://www.quantifiedcode.com https://www.quantifiedcode.com) and have thought a lot about this problem as well. Since we offer a SaaS solution instead of an IDE plugin the boundary conditions are a bit different for us (e.g. we have less strict "realtime" requirements but the feedback time is also longer), but the basic question is the same: Why doesn't everyone use static analysis to improve their code? After having surveyed most of the available static analysis tools I think that part of the answer is that often the tools simply do not provide enough value for developers, especially those analyzing dynamic languages like Python / Ruby / Javascript (for C++/Java the tooling is much better). We are currently trying to change that by developing a new, data-driven approach to code analysis, which (we hope) should improve the quality of the analyses quite a bit and provide better and more actionable feedback. Part of the problem is also cultural of course: People have different ideas about what "good code" is and they usually do not like having their code critiqued. Using an automated tool rather than manual code review to check some aspects of code quality can be beneficial though, since it is normally easier to accept harsh feedback from a machine than a human.

oellegaard 11y ago
It looks like it takes quite a while to analyze :-( It just says Waiting for analysis to start (queue position: 46)

geromek 11y ago

I think the reason is fairly simple: even the most evident-no-doubt clear SQL Injection vulnerability found by a SCA tool may never be exploited at all under production (for instance because of a WAF). Then the obvious benefits of static analysis are not that obvious for your employer. Sometimes we forget companies do not want a perfect code or the best possible well designed software but a product that make them earn money. My experience is that developers only use those kind of tools if they are forced to by their QA managers of bounded by contract. Programmers usually don't want to fix or track bugs.

PinguTS 11y ago
So, you are saying "Developers don't want to deliver quality."? If that it true, than I don't want to work with them.
- geromek 11y ago
  I am saying "Developers do not want : 1 - Pay A LOT of money for advanced solutions that are more than AST checkers (hello SonarQube) or big piles of false positives. 2 - Add overhead to their workflows (more than an IDE plugin is harmful, and what happens with those devs not using an IDE?). 3 - Spend time on figuring out if the static analysis results make sense or not, one by one. A typical SCA tool can report hundreds or thousands of occurrences for a certain code base. How are developers going to deal with them?
  - PinguTS 11y ago
    I am from engineering background and not soley a software guy, so forgive me my different view on this topic. I learned, that every error you can fix early on will cost you about 10x to fix in the next stage. All the new principles like Agile have not changed that.
    - glogla 11y ago
      I think the idea is not that it's not worth to fix errors as soon as possible (which it is), but that static analysis tools provide too many false positives and too many non-errors to be useful.

dschiptsov 11y ago

Because neither an advanced type system nor static analysis could catch bugs in program logic?) The benefits of static typing (complie-time checks) are grossly exaggerated. If the claims were true, Java itself and Java projects would be much less buggy.)

HOLYCOWBATMAN 11y ago
>The benefits of static typing (complie-time checks) are grossly exaggerated. If the claims were true, Java itself and Java projects would be much less buggy I wouldnt call Java an "advanced type system". Take a look at Idris then try to say that with a straight face: >Because neither an advanced type system nor static analysis could catch bugs in program logic It certainly does if you indeed use an advanced type system.
amirmc 11y ago
This reasoning makes no sense to me. It's like: Alice: "Doing X will prevent bugs like Y!" Bob: "Oh, but it does nothing for bugs like Z. I just won't bother at all, then". Why would you not want to try and remove an entire class of bugs if it were within your power to do so? Just look at all the effort companies like Facebook have poured into exactly this kind of problem with things like Hack and Flow (which make use of OCaml).
- glogla 11y ago
  I think you're missing each other in terms of what static typing you mean. Haskell or ML style static typing is very useful, completely changes the way you do things and gives you many guarantees. C or Java static typing is almost useless with regards to bugs (see null) and serves mostly to annoy you. It has many of extra costs of stronger static typing, but gives you very little of the benefits.
  - taeric 11y ago
    Static analysis is more than just static typing. Notably, it is possible to leverage static analysis for solid gains in reliability against code bases without having to rewrite them to take advantage of a different typing paradigm. To repeat, you can harden a code base without rewriting it by using static analysis tools. This is not as true with static typing.

irascible 11y ago

Because the good ones are too fucking expensive.

raz32dust 11y ago

The problem I have is that there are many cases where the tools are too defensive. If I want to override the tool, I'd typically have to add some annotation in the code to signal to the tool that I am ok with this warning and don't want to see it again. And I, for some reason, just hate adding style checker and static analysis annotations in my code. It just looks ugly to me.

faragon 11y ago

They should. There is no excuse: clang has it for free, Visul Studio, too (Express Editions, since 2013). Also, for Open Source projects Coverity is free.

72deluxe 11y ago

I do! For cheapness, Flawfinder, CPPCheck, and Product > Analyze in xcode (thanks clang) (the walkthroughs in xcode of how they deduced the problem are really great, blue arrows everywhere, very neat). EDIT: Additionally, given the changes in C++11 we should be able to push all the work onto the compiler for checking type problems, remove dangerous operations, dangling pointers, naked new/delete and avoid casting where possible. It would make for bug-free software. I know someone who writes their C++ like it is late 80s C and firstly, it's horrible to read. And secondly, it does really dangerous things.

roel_v 11y ago
I refactored some code this week that used realloc to allocate memory for a 'vector' (which was a typedef for float*), and then a loop with additional realloc's to allocate memory for each element in that vector, to end up with a matrix 8| This is code that was written in the last few years, too. Welcome to academia :(

egwor 11y ago

I use IntelliJ for my java development. It has a lot of analysis built in (whilst you're writing code). I'm not sure if there are that many static analysis checks (Findbugs etc) that are missing outside of those real time checks? I can often determine whether someone had used Eclipse or IntelliJ; there tend to be a lot fewer analysis warnings if someone has used IntelliJ (out of the box) => perhaps we need this analysis in real time?

M4v3R 11y ago
Don't know about IntelliJ, but XCode does real-time analysis as well, but it also has a mode for deep static analysis, which for example does code path analysis for finding dead code paths, even across methods. This kind of stuff would be hard to perform in real-time.
- inglor 11y ago
  Why? You'd just keep the code in SSA and diff whenever the user adds code - you need to create the form _once_ but after you've created it diffing it should be reasonably fast - the creation can be done at project creation time and it can be changed on-line and incrementally. I'm not sure if tools actually do it but it definitely sounds possible.
  - danbruc 11y ago
    How would maintaining a SSA representation of the code help detecting dead code paths? Doing so requires reasoning about possible truth values of conditions and is in general equivalent to the halting problem and therefore undecidable. You could only spend the cycles available in real time and that will in a certain number of cases be enough to solve the problem but there will also be instances requiring more cycles and instances being undecidable.
    - inglor 11y ago
      > How would maintaining a SSA representation of the code help detecting dead code paths? Well, if a variable assigned but never appears in a path that might have side effects it's dead. It's only the halting problem if you pretend to catch 100% of cases under all inputs. You can find lots of dead code without it. For more information about the specific technique of DCE under SSA form see http://grothoff.org/christian/teaching/2007/3353/papers/ssa.pdf http://grothoff.org/christian/teaching/2007/3353/papers/ssa....

deleted 11y ago

[deleted]

pmontra 11y ago

I used lint for C some 20 or 25 years ago, then moved to using dynamical languages (Perl, Ruby, JS.) Not much use of static analysis tools for those languages I thought (but for example check https://www.infinum.co/the-capsized-eight/articles/top-8-tools-for-ruby-on-rails-code-optimization-and-cleanup https://www.infinum.co/the-capsized-eight/articles/top-8-too...). I used Java sometimes and took advantage of Netbeans/Eclipse's hints about Java code but I use emacs for everything else (some vim too). I used jslint on a JavaScript project a few months ago. It catched a few things I overlooked, I learned a couple of things (example: it's useless to define a var inside a loop) but it's also very opinionated and insisted that I write code in a way that pleases its author. I had to refactor working code to make most of the warnings go away. I ended up with something that worked as well as the original but was much more complicated to read (at least for me). I stopped using it and regretted making all those changes to the code. There are some configuration switches but nothing that could make it work for me. I should check jshint but unfortunately jslint primed me against that kind of tools. I prefer to catch errors with tests and test coverage tools. They must be used anyway and they bend to me, not the other way around.

taeric 11y ago
It is the "opinions enforced with static analysis" that ultimately annoy me with most analysis tools out there. Things that actually cause bugs, I welcome ways of finding them. Chaining all of my variable declarations together... What? The sad thing is that the powerful analysis tools are truly amazing and do find things. They just are not what the majority of people have experience with. That does seem to be changing.
stevedonovan 11y ago
Ditto and likewise - same applies to pylint, which must have been the most opinionated piece of software I've ever used. The trouble is that there's some very useful warnings buried in the opinion spew - warnings which would be an error in other languages.
- falcolas 11y ago
  pylint is also trivially easy to configure to omit most of these stylistic warnings. I say this as someone who took 10 minutes to generate and configure the pylintrc for a new project. After taking this time, pylint has been quite useful.

scotty79 11y ago

Same reason people use email and code html in editors that are barely more capable then notepad. Sophisticated solutions tend to fail from time to time when applied. And when they fail they are tossed aside for simpler more resilient ones.

deleted 11y ago

[deleted]

deleted 11y ago

[deleted]

jokoon 11y ago

I once was told that any compiler warning message act as static analysis. I think static analysis is a complex subject, because it can touch some sensitive subject like programming style and other more expert subjects like compiler back end and how the language defines such and such code behavior. Static analysis should be made more mainstream, it would be such a great way to teach everybody how to write better code, including and especially students.

crdoconnor 11y ago

Mainly because most of the tool reports freely mix critical issues with stuff that is just opinionated bullshit (e.g. 80 character length lines). When the output is as long as your arm and you have pick through it with a fine toothcomb to find the things that matter (and even they aren't necessarily causes of bugs), the whole idea becomes substantially less appealing.

yeahdude 11y ago
grep -v
- rjaco31 11y ago
  if you have to make a dozen of grep to exclude trivial results, it might be a hint there's something wrong with the pertinence of your output or the customizability of your tool
  - yeahdude 11y ago
    From another perspective, hacking often involves making broken things work better.
    - crdoconnor 11y ago
      From yet another perspective: don't use broken tools.
      - yeahdude 11y ago
        I keep forgetting this one: don't offer help to complainers.
        crdoconnor 11y ago
        If the help constitutes telling people about this wonderful new tool you've just discovered called grep, perhaps that's for the best.

kushti 11y ago

I don't know tools for Scala/Haskell making me excited, that's why. Would be happy to see something here.

asfa124sfaf 11y ago

This is something that Checkmarx.com (checkmarx.com) does. They recently received substantial investments and seem to be popular.

franzpeterfolz 11y ago

Well, I did it the other way around. When my co-workers drove me crazy. I just launched Findbugs on their Repo/Projects and filed some bugs in the Bugtracker. That is just a matter of 5 Minutes to get them down to the ground and show that they are not that kind of Rockstar-Devs they pretend to be. But never reveal your secret tools! Well, and if they get curious about your magical Bug-Finding-Skills, they are easy to convince to use these tools. Its a kind of marketing.

omouse 11y ago
using clonedigger for python I found lots of copy/paste code and surprise! where did we find bugs? right in every spot clonedigger pointed out.

iolothebard 11y ago

Nice advertisement. It's Alt+F11 in Visual Studio. Between that and Resharper, life is good.

PVS-Studio 11y ago
Not so simple. Review John Carmack article: http://gamasutra.com/view/news/128836/InDepth_Static_Code_Analysis.php http://gamasutra.com/view/news/128836/InDepth_Static_Code_An...

watmough 11y ago

cl : Command line warning D9040: ignoring option '/analyze'; Code Analysis warnings are not available in this edition of the compiler Ooops.

tosh 11y ago

The Dart analyzer (https://pub.dartlang.org/packages/analyzer https://pub.dartlang.org/packages/analyzer) is used by various IDEs and text editors like IntelliJ, Eclipse, Sublime and Atom to provide semantic autocompletion, documentation and inline warnings/errors.

chimtim 11y ago

Static analysis tools are great for simple bugs. However, most compiler tools already fix these simple bugs. If there is a class of bugs not addressed by a compiler, most developers have a script to catch these. It may not find the harder to detect bugs (such as those arising out of nested calls), but it gets the job done. The complex tools pushed out by the static analysis guys usually has a high false positive rate that at first becomes annoying to use and later is completely ignored. As for more complex bugs, most developers are aware these bugs exist but do not want to fix them immediately. The reason is on many occasions, these bugs represent some bigger problem in the code base that requires significant re-factoring. And applying the quick fix as suggested by the code analysis tool simply buries these problems instead of fixing them the right way.

AndreyKarpov 11y ago
Yes, static analyzers mostly catch simple bugs. But it doesn't really matter if a bug is simple or complicated. You see, programmers believe they never make or make very few simple bugs: http://www.viva64.com/en/b/0116/ http://www.viva64.com/en/b/0116/ But they are wrong. They do make quite a lot of them. Here's, for instance, a bug database we have collected and keep updating: http://www.viva64.com/en/examples/ http://www.viva64.com/en/examples/. Moreover, some bugs can take quite a while to find, despite being simple. Here's a nice example: The conclusion is: the bug we had wasted about 50 hours to track was detected at once with the first run of the analyzer and fixed in less than an hour! Source: http://www.viva64.com/en/b/0221/ http://www.viva64.com/en/b/0221/ True, false positives aren't good, but they are not that much trouble. Static analysis tools provide numbers of means to suppress them. At least, we in PVS-Studio do have a lot of false positive suppression mechanisms. But it's a long story, so you'd better refer to the documentation.

AndreyKarpov 11y ago

Parallel Reddit discussion: https://www.reddit.com/r/programming/comments/3b67pi/why_dont_software_developers_use_static_analysis/ https://www.reddit.com/r/programming/comments/3b67pi/why_don...

skrowl 11y ago

Because we already have a better tool for finding bugs: Production users

AndreyKarpov 11y ago
Therac-25: https://en.wikipedia.org/wiki/Therac-25 https://en.wikipedia.org/wiki/Therac-25

shavenwarthog2 11y ago

As a Python programmer, I live and die over Pylint. Yes it's annoying to configure it, but it saves me hours every _day_. The two biggest benefits are: - syntax or undefined variables in exception handlers - showing which modules are no longer used, so we can have a clearer import block

omouse 11y ago
could you share your pylintrc for others to learn from?

GFK_of_xmaspast 11y ago

It's hard enough sometimes getting people to turn on compiler warnings.

wyldfire 11y ago

We do. (some of us do, anyways). > Mike: "Clang is my favorite. Its built into the compiler. You don't have to invoke anything special." I agree with Mike. I've also used Coverity Static Analysis and various other tools. Some of them are better than others. Also, "-Wall -Wextra" or "-Weverything" are fantastic for a simple first-pass static analysis.

nachiketn 11y ago

Additional work. Developers don't like to deal with false positives. If static analysis tools were like a laser. It's more like a shotgun that throws a bunch of shrapnel. Sure it hits some really difficult to find bugs. But developers don't like to have to go through a long list of warnings that aren't really guaranteed to find a valid bug, especially in the applications' context. For example null checking is good, but is it needed if I know it is never really going to be null? Isn't that arguably extra effort of typing and compiling and couple of extra lines to compute? I think we will truly move to better adoption if: 1) We had better configuration for customizing it for our application. 2) More education among developers about what is the correct way to modify the tool's behaviour to aid their work. Help the tool, help them in return. 3) More tools that do specific and general work. Example tools extremely focused on mobile development but also tools that not just help you with correcting design and coding problems but also security vulnerabilities.

NickNameNick 11y ago

I ended up writing my own for the bespoke language my company uses internally. The lack of tools like java findbugs had been annoying me. Luckily the server side 'workflow' language, and the client side templates are all written in xml, so its trivial to parse. The first version was painfully slow. The second version tracked the range of possible states as it did a depth first search of the AST, and then stored the requirements of each node of the tree before it moved on to the nodes next sibling or parent. That way if another part of the software later called into an equivalent subtree, I could compare the current range of possible states to the requirements of the first node in the subtree and record any mismatches, then move on. It went from taking over a minute to evaluate a fairly trivial app, to parsing the biggest apps my company has ever shipped in 1-2 seconds. I'm sure the technique is quite common. I wish I could remember if I read about it, or applied it from a different context. In any case the exercise was more useful for learning than as a finished product.