Smart Software

Orcas Beta 2

Orcas Beta 2 is here, and it includes a go-live license. I plan a switch over (plus a clean reinstall of Vista) by the end of this month. I do prefer to use the latest tools to keep on top of technology, and, despite the installation being a distraction from my current work, I do feel rejuvenated by a sense of progress and change of scenery.

I have been developing in Orcas Beta 1 for about a month now, but haven't been using any of the new compiler features and libraries. Both Refactor Pro and Resharper have latest versions that will run on Orcas, though I don't think Resharper 3.0 supports the new language syntax yet. With the go-live license, it might even be possible to use the LINQ APIs even though the product has RTMed, but I'll wait.

It is hard for me to recall a specific benefit of using Orcas, but it is very stable and doesn't require Administrator privileges to run. Most of the benefits from using the IDE come are related to .NET 3.0/3.5 (which include WPF and LINQ).

I am not planning on using WPF in the near term, but it is something I am currently looking into the future. And if I were, it would initially be from inside a WinForms application using its interoperability features. I also don't see a compelling reason now to use it. I have seen a couple reports that WPF is not ready for prime time use, Rod Paddock, Eric Sink and Lhotka. I have seen ribbon and other components from ActiproSoftware, DevComponents and Infragistics, but the component libraries are still minimalistic and not fully developed. The runtime, required for Windows XP, also adds 2.8 Mbs to my setup package, and forecloses my ability to run in Windows 2000 (though, I must admit, I can't guarantee NStatic even runs in 2000 in its present state).

VB & Other .NET Languages

Send me mail if you are interested in beta testing experimental Visual Basic or IL+PDB support (for other .NET languages including C++/CLR--please specify language) if and when I do include it in an NStatic beta. I don't know if I'll be able to handle DLR-based languages.

There's a slight chance for support of other languages in the beta, but it will be experimental and the primary focus is C#. Any other language support will come in a minor update. I don't have much experience working with other CLR languages other than C#.

If VB support is introduced, it will likely have rich editor and intellisense, but some parts of the analysis may exhibit C# semantics except when performing the analysis indirectly through IL. All other languages will have error highlighting support.

Omniscient Debugging

Bill Lewis of Tufts University, who is a computer scientist who has worked on natural language processing, gave a fascinating Google TechTalks lecture on "Debugging Back in Time." He also has a page dedicated to this new idea of Omniscient Debugging, where the debugger knows everything.

The omniscient debugger records every state change in the entire run of the program. Bill states that omniscient debugging gives the programmer a unique view of the program that eliminates the worst aspects of breakpoints:

• No guessing where to put breakpoints
• No extra steps to debugging
• Set breapoints, start, examine, continue
• No fatal mistakes... (no, "Whoops, I went too far")
• No non-deterministic problems
• Customers can email a debugging session to developers

An omniscient debugger can be extremely effective in understanding and fixing bugs. Bill's description and walkthrough of his prototype omniscient debugger (which in his words is more already more effective than any commercial debugger) seems to offer a genuine "silver bullet" approach to debugging.

His approach to omniscient debugging logs every state change to the program. This has the obvious disadvantage of slowing down execution runs and consuming disk space. Bill claims to have a found a practical way of doing this. The disadvantages are similar to those a profiler, but even more so, because each state change is logged, not just function calls.

I noticed a long time ago that my own analysis tool, which uses a completely symbolic representation of a program's abstract state space, could in theory be able to recreate the entire run of a program with just a compact set of critical assumptions.

This could be even more effective than logging, because of the superior time and space savings of my approach. NStatic can execute a long series of nested lengthy loops in less than a millisecond; it can allocate a gigabyte-size array and fill it up with values from any algorithm, and it would still take just the few K of memory that is needed to represent the algorithm itself.

There might even be some benefit to combining my "symbolic" debugger with Mike Stall's C#/IL managed debugger sample, so that I can retroactively incorporate symbolic reasoning to an actual just-in-time debugging session. One developer actually created Deblector, which uses Reflector to decompiling and debugging IL on the fly.

I did consider at one time being able to step forward and backward through the execution history. In NStatic Directions, I did mentioned making static analysis more into a debugger than a static analysis tool.

Making C# feel more like a dynamic, interpreted, REPL language through the use of a symbolic interpreter. Code is always live and can be statically debugged. As Erik states, programming will “shake of the yoke of the dreaded (edit, compile, run, debug)* loop and replace it with a lightweight (edit=compile=run=debug) experience.”

NStatic does already feel like a debugger with ability to watch and execute code immediately, as well as the ability to apply new assumptions.

Methods, Part 1

Method handling is difficult in static analysis. I will describe in a few parts some of the issues that I have had to deal with.

I demonstrated in earlier posts my handling of recursive functions in Loops, Part 1. In this post, I will show how I elegantly handle virtual functions. Below is the code for three classes, a base class Animal and two derived classes, Cat and Dog. Animal is an abstract base class, so no implementation actually exists for one of its member function.

Each animal can make a noise and has a type.

To test the three Animal classes, a wrote the following test method below. We have three variables of type Animal, "spot," "polly," and "tabby." We know Spot is a dog through an Assert statement. We know Tabby is a cat because we just created one from scratch. However, Polly is an unknown and sounds as if it may be a parrot, a class that we actually haven't account for; or, we could be mistaken, and it could actually be a dog or cat. 

So, I run the code through NStatic and extract out all the local variables and its member variables after the scan. Here's what the resulting Locals window looks like.

Whether we assign a variable or assume it, we know through the variables of the form "isXaY" that Spot is a dog and not a cat, and Tabby is a cat and not a dog. We also know that Spot says "Bark" and Tabby saw "Meow." We can also tell each animal's type from Animal's virtual property, Type. However, the Polly variable is mysterious. Thus, the local window has to represent all information about Polly's nature and behavior through conditional expressions and possibly generated values (in the case of Animal.Say(), which has no implementation).

 

NStatic Usability

I have invested the past three weeks into the NStatic user interface, polishing it up and considering how it will eventually be used. I didn't feel that the previous user interface was acceptable.

I'll take it to beta when it feels just right; I don't think it make sense to do it when there are still bugs that I am aware of.

I have given thought to the many different areas of the product:

• Interactivity. The performance of the tool is such that it is possible to interactively modify state and execute code in the context of the error. Much of the tool such as the intellisense, the class view, the error window, and file structure view are already synchronized in real time with text editor. The error window actually incorporates syntax errors dynamically as code as being edited.
• Manipulating and viewing the data. I have also captured much more statistics and allowed many different ways of viewing the data within the tool.
• Exporting the data. There are multiple ways to send and export data.
• Fixing the bug. I have also considered the process of visiting and fixing the data, and preventing some types of errors from appearing in future scans. This process is much like how Outlook allows one to manage inbox message.

I suspect that this product will be much more pleasing to the eyes and richer in functionality than people will have been expecting.

Loops, Part 2

This is the second in a multi-part series on loop handling, which will be followed by treatments on methods, state, and other interesting areas of static analysis.

I have tried to be as general as possible in my code analysis, while still remaining efficient, such as in how I deal with state, function calls, loops and recursion.

One illustration of this is how I represent newly allocated objects or the return values of unknown functions from inside loops. There were several methods that I considered, each with different tradeoffs, but the method I ultimately decided upon because it was more composable (thereby making analysis easier) and more understandable for the user.

In the following example, I allocate elements for an array.

When allocating a new object, a new id is required to uniquely identify the object, since the "new object()" expression is not sufficient to distinguish two different allocations. Rather than incrementing a counter which could be used for generating an id number, I preferred tying the id to the object's location in the source code; this way, the id could remain a constant number without the likely risk of turning into a complex expression as would happen with the alternate method.

However, this method is not sufficient inside loops or in repeated function calls, so we need a loop identification operator to identify the iteration within the loop in which the object was allocated.

The locals window shows how the operators for object identification and loop interation appear. Object identification uses the "#" symbol and loop iteration reuses "{}". I drop the id for the array assigned to the "array" variable, since every instance of that array will be referred to by the "array" variable name; the id in that case becomes pure noise.

I have shown some examples of the values of various array elements, including one (contained in the local "w") indexed by a variable. The loop iteration is very easy to understand and just as well to analyze.

I should note the w is not fully simplified as it is possible to remove the lambda expression with a quotient and remainder operator; this will probably be fixed before I release.

In this simpler example, I show that objects allocated at different instances of the loop are not equal. I also expanded the array variable to expose the values of each of the elements of the array.

* The value produced here by the array.Length variable is a bug, which has not been fixed yet, and should actually report the number 3.