Filtering TextBox

Hi All,


Today I want to present a nice control that I wrote called the Filtering TextBox (FTB for short). Consider the following case: You have a known (static) list of items, each item represents some sort of operation (the basic operation can be selecting this item but it is not mandatory) and you want to allow the user to see the entire list of items but also filter the shown items based on a text input from the user (similar to city selection in any maps site). Some extra features that my control allows:

1. Categorizing items - Each item is assigned to a category and these categories are displayed in the list box (above the items).
2. Disabling items - Each item may be disabled. It appears in the filtered list but the user cannot select it.
3. Invisible items - Each item may be invisible to the user even if it corresponds to the input text.
4. Hint Text - Each item may contain a hint text which will be displayed in a slightly grayed out text next to the item display text.
5. Any class items - An item can be any class as long as it implements a predefined interface.

An example of how the Filtering TextBox works.

I will not show all the implementation details but describe a few interesting points.

There are two type of items in the list. A category and a selectable item. The user distributes items per categories by providing a property getter for the Category property. The control maps all items into the given categories automatically.

Each item added to the FTB must implement the IFilteringTextBoxItem interface and all items must be added in a single call to the Add method. All subsequent calls will simply remove all the previous items.

The SearchTextBox custom control is a simple TextBox with a background text added to it. I got the idea for the implementation from Kevin and his Bag of tricks. At first I thought I would use his control directly but I didn't like his implementation so I implemented my own.

The filter uses two search methods -

1. Simple string "contains" (CIAI) for each word in the input TextBox.
2. Something like CamelCase notation for words  (I saw this method was popular so I added it) i.e. you can type the first letters in the string you search.

You can download the full source code from my SkyDrive here. The code is as usual under the COPL (The Code Project Open License 1.02).

Feel free to leave comments.

Boris.

On a sick leave

Hi All,


Due to sickness of myself and all the members of my family there was no post last week and no post this week.
I hope next week everyone feels better and I will have time to write my post.


Stay tuned,
Thanks,
Boris.

JIT/Compiler Optimization of Fibonacci calculation

[intermediate-high level]
Hi All,


Today I want to consider the following case:
In my application I want to use some Fibonacci numbers (this is just a hypothetical example :)). I want to see if I can make the JIT/C++ Compiler to put the actual number instead of calling the calculation method. I made two implementations of the calculation but I will show only one, recursive and horribly slow implementation (don't ever use it or even consider of using it!):

    static int FibonacciRecursive(int level)
    {
      if (level == 0)
        return 0;
      if (level == 1)
        return 1;
      return FibonacciRecursive(level - 1) + FibonacciRecursive(level - 2);
    }

And my code for the tests is:

    static void Main(string[] args)
    {
      Console.ReadLine();
      int result = FibonacciRecursive(45);
      Console.Out.WriteLine(result);
    }
I added the ReadLine so that I will have time to attach a debugger when I run the code. The 45th Fibonacci number, if you were wondering, is 1134903170 and not long after that it overflows int :).
I will save you the reading time and not try my code in debug mode. I will first run my code from Visual Studio by pressing "Run" and here is the result (I added comments in case your assembly is a little rusty):

;      int result = FibonacciRecursive(45);
00000022  mov         ecx,2Dh ;put 45 in the ecx register (this is how methods in .net expect their first argument)
00000027  call        dword ptr ds:[006C1F34h] ;call the FibonacciRecursive method 
0000002d  mov         dword ptr [ebp-0Ch],eax ;get the return value from eax register and put it in the "result" variable
00000030  mov         eax,dword ptr [ebp-0Ch] 
00000033  mov         dword ptr [ebp-8],eax 

As you can see there was no optimization in this case, in fact we can see the two lines 
0000002d  mov         dword ptr [ebp-0Ch],eax 
00000030  mov         eax,dword ptr [ebp-0Ch] 
Which copy the return value of the function (stored in eax) to the result variable and then copy it back to eax.

Now I will run the same code but attach the debugger at a later stage (after JIT generated the code) here is the result (again I added some comments):
00000013  mov         ecx,2Ch ;put 44 in ecx register
00000018  call        dword ptr ds:[001A37F8h] ;call the FibonacciRecursive method
0000001e  mov         esi,eax ;put the result in esi register
00000020  mov         ecx,2Bh ;put 43 in the ecx register
00000025  call        dword ptr ds:[001A37F8h] ;call the FibonacciRecursive method
0000002b  add         eax,esi ;add the results of the two calls into eax register

As you can see the code is much more optimized. Which means JIT generates different code if it sees a debugger attached so even when you compile in Release with optimization and run in VS you don't see the most optimized code. 
You can also see that the JIT compiler unwinded the recursion and put its code inline but again the JIT compiler called the method and did not generate the result directly as I wanted. If you are beginning to doubt this is at all possible, keep reading.

Now I will change the call to 
int result = FibonacciRecursive(1);
 and run it without VS. Here is the result:
00000019  mov         edx,1 
Just as we wanted! Instead of calling the method it simply put 1 as the result.
Lets try running it with 
int result = FibonacciRecursive(2);
The result is quite interesting:
00000013  mov         ecx,1 ;put 1 in the ecx register
00000018  call        dword ptr ds:[001937F8h] ;call FibonacciRecursive
0000001e  mov         esi,eax ;put the result in esi register
00000020  mov         ecx,0 ;put 0 in the ecx register
00000025  call        dword ptr ds:[001937F8h] ;call FibonacciRecursive
0000002b  add         eax,esi ;add the results of the two calls
This is really nice. Now we have two calls which are non recursive. This makes me wonder why it didn't run the same logic as it did in the previous run and replaced the method calls with the actual values. My guess would be to speed up the compilation time as it is done in runtime.

These are all my tries in .NET and as you can see I failed to achieve my goal. One could say that this is not possible but I want to look at a little C++ trick which can achieve just what I want. This trick is taken from a programming paradigm known as Generic Programming. This is the C++ code:

#include <iostream>

template <int N>
struct Fibonacci
{
  static const long result = Fibonacci<N-1>::result+Fibonacci<N-2>::result;
};

template <>
struct Fibonacci<0>
{
  static const long result = 0;
};

template <>
struct Fibonacci<1>
{
  static const long result = 1;
};


int main()
{
  std::cout << Fibonacci<45>::result;
  return 0;  
}

and when run, it compiles into this:

01001000  mov         ecx,dword ptr [__imp_std::cout (1002048h)] 
01001006  push        43A53F82h  ; 1134903170 decimal == 43A53F82 hexadecimal
0100100B  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (1002044h)]  

This is exactly what I wanted. The compiler simply pushes the 45th Fibonacci element onto the stack and calls cout. (In C++ arguments are passed using stdcall convention where all the arguments are pushed to the stack.)

That's it for this week.
Thank you for reading.

Boris.

A text based, unparsed, context sensitive Xml viewer

Hi All,


Most modern programs today (in .NET) use Xml at some point of the other. If you have a configuration file it is written in Xml format. If you use human readable persistence or data transferal you probably do it using Xml. Many times you want to review a received XML with no real need to edit it. This was exactly the problem I was facing. 
In my application a user may receive some Xml data which he cannot edit but wants to view in a nice way. The user may interact with the Xml in a context sensitive manner meaning, if the user selected an Element he may get a different UI than when he selects an attribute. Previously I used a WebBrowser control which shows the Xml in a nice form (with folding) but it was not too customizeable (and to tell the truth I wanted to avoid COM and do something which is WPF based). The obvious solution was to use a tree. The Xml is organized in a tree based form anyway so a tweaked TreeView can be exactly what I needed. I looked around the internet and found this example: http://www.codeproject.com/KB/WPF/XMLViewer.aspx
The code in this example worked really well and I tweaked it a little to get the context sensitive nature I needed but there was one major drawback. It was not text editor based which made selections and other related interaction a hell. 
At this point I decided to write a simple text based viewer for my Xml. Before I continue I want to note that since I don't want to support editing I don't actually need a parser for my Xml. If full editing was needed then a parser would create the context sensitive functionality I need.


The editor I will be using is AvalonEdit which comes as a stand alone component in the SharpDevelop IDE. Whats nice about AvalonEdit is that I can get all the folding and coloring customization directly from the editor by setting SyntaxHighlighting="XML". For loading the Xml I am using XmlDocument (you can use XDocument if you like it better). I build a tree structure which represents the Xml where each node represents a single Xml element and the text range it takes within the text editor.


The base class for the ranges is:

 public abstract class BaseXmlTextRange : IComparable<BaseXmlTextRange>, IXPathProvider
  {
 
    protected const string IndentationString = "\t";
    /// <summary>
    /// The underlying node of the current range
    /// </summary>
    public XmlNode Node
    {
      get;
      protected set;
    }
 
    /// <summary>
    /// The start position of the current range
    /// </summary>
    public int Start
    {
      get;
      protected set;
    }
 
    /// <summary>
    /// The end position of the current range
    /// </summary>
    public int Length
    {
      get;
      protected set;
    }
 
    /// <summary>
    /// The last index of the range
    /// </summary>
    public int End
    {
      get
      {
        return Start + Length - 1;
      }
    }
 
    /// <summary>
    /// Represents the range that contains this range
    /// </summary>
    public BaseXmlTextRange Parent
    {
      get;
      set;
    }
 
    protected SortedSet<BaseXmlTextRange> _innerRanges;
 
    public BaseXmlTextRange(XmlNode node, int start)
    {
      _innerRanges = new SortedSet<BaseXmlTextRange>();
      Start = start;
      Node = node;
      Parent = null;
    }
 
    public ReadOnlyCollection<BaseXmlTextRange> InnerRanges
    {
      get
      {
        return new ReadOnlyCollection<BaseXmlTextRange>(_innerRanges.ToList());
      }
    }
 
    #region IComparable<BaseXmlTextRange> Members
 
    public int CompareTo(BaseXmlTextRange other)
    {
      if (other.Start > this.End) //other after this
        return this.End - other.Start;
 
      if (other.End < this.Start) //other before this
        return this.Start - other.End;
 
      throw new ArgumentException(String.Format("Ranges cannot overlap {0}-{1} and {2}-{3}", Start, End, other.Start, other.End));
    }
 
    #endregion
 
    public bool OffsetInRange(int offset)
    {
      if (offset >= Start && offset <= End)
        return true;
      return false;
    }
 
 
    #region IXPathProvider Members
 
    public IXPathProvider GetParent()
    {
      return Parent;
    }
 
 
    public abstract XPathData AppendXPathData(XPathData xPathData);
    #endregion
 
    public BaseXmlTextRange GetInnerRange(XmlNode xmlNode)
    {
      foreach (BaseXmlTextRange range in _innerRanges)
      {
        if (range.Node == xmlNode)
          return range;
      }
 
      return null;
    }
 
    /// <summary>
    /// Returns the smallest range corresponding to the given offset or null if the offset does not correspond to any range
    /// </summary>
    /// <param name="offset">The offset to look for</param>
    /// <returns></returns>
    public BaseXmlTextRange GetRangeByOffset(int offset)
    {
      if (!OffsetInRange(offset))
        return null;
 
      foreach (BaseXmlTextRange innerRange in _innerRanges)
      {
        if (innerRange.OffsetInRange(offset))
          return innerRange.GetRangeByOffset(offset);
      }
 
      return this;
    }
 
 
  }

I will give a brief explanation on most elements and you can fill in the details by examining the code. Each range holds the XmlNode which it represents. This can be either an Element, an Attribute, or a Value (the specific implementations are exactly for these node types). Each range holds the list of its inner ranges to create a tree like structure. The text editor "talks" with the ranges by providing an offset within the text therefore I provide a simple API method to locate a given node by the offset. Since Xml is a tree, I have the root node to start searching from.

Building the ranges is simple and is done through the following method:

    /// <summary>
    /// Builds the subtree of this range and returns the string that represents the associated node XML
    /// </summary>
    /// <param name="indentationLevel">The indentation level of this element</param>
    /// <returns></returns>
    public string BuildSubtree(int indentationLevel)
    {
      StringBuilder result = new StringBuilder();
 
      int count = 0; //Tracks the number of chars in this range
      result.Append(StringUtils.Repeat(IndentationString, indentationLevel));
      count += (indentationLevel * IndentationString.Length);
 
      result.Append("<");
      count++;
 
      result.Append(Node.Name);
      count += Node.Name.Length;
 
      result.Append(" ");
      count++;
 
      foreach (XmlAttribute attributeNode in Node.Attributes)
      {
        AttributeXmlTextRange attributeRange = new AttributeXmlTextRange(attributeNode, Start + count) { Parent = this };
        result.Append(attributeRange.BuildString());
        count += attributeRange.Length;
        _innerRanges.Add(attributeRange);
      }
 
      if (Node.ChildNodes.Count == 0) //No subelements!
      {
        result.Append("/>");
        count += 2;
 
        result.Append(Environment.NewLine);
        count += Environment.NewLine.Length;
      }
      else
      {
        //Close the element;
        result.Append(">");
        count++;
 
        result.Append(Environment.NewLine);
        count += Environment.NewLine.Length;
 
        foreach (XmlNode innerNode in Node.ChildNodes)
        {
          if (innerNode.NodeType == XmlNodeType.Element)
          {
            ElementXmlTextRange tempRange = new ElementXmlTextRange(innerNode, Start + count) { Parent = this };
            string innerElementString = tempRange.BuildSubtree(indentationLevel + 1);
            result.Append(innerElementString);
            _innerRanges.Add(tempRange);
            count += tempRange.Length;
          }
          else
            if (innerNode.NodeType == XmlNodeType.Text)
            {
              ValueXmlTextRange tempRange = new ValueXmlTextRange(innerNode, Start + count) { Parent = this };
              string innerElementString = tempRange.BuildString(indentationLevel + 1);
              result.Append(innerElementString);
              _innerRanges.Add(tempRange);
              count += tempRange.Length;
            }
        }
        //Append end element tag
        result.Append(StringUtils.Repeat(IndentationString, indentationLevel));
        count += indentationLevel;
 
        result.Append("</");
        count += 2;
 
        result.Append(Node.Name);
        count += Node.Name.Length;
 
        result.Append(">");
        count++;
 
        result.Append(Environment.NewLine);
        count += Environment.NewLine.Length;
      }
      Length = count;
      return result.ToString();
    }
I think the code speaks for itself but basically this is a recursive construction of Elements, Attributes, and Values using the ranges. The indentation level allows nice formatting of the text within the text editor. You can see the result in the following image:
An example application that uses the XmlTextViewer control

If you are interested in the code you can get it from my skydrive here.
Please note that while my code is under the CPOL license, AvalonEdit is under LGPL license.

Thank you for reading,
Boris

Macros in C#

[beginner level, originally posted on an internal company blog on Feb 1st]

Hi,


Today I want to talk about C# macros. Those are not macros in the
sense of C's #define statements but instead a syntactic sugar which
enables us to write simple, more readable and shorter code. My point
is that all those macros can be avoided by writing other code which
will result in the exact same IL. You might have not noticed these macros before or took them for C# keywords but in this article I will use Reflector (edit: Reflector was still free back then) to see what the compiler does in the case of four commonly used statements.

Extension Method

An extension method is a method defined on an existing class which can
be called using the dot operator. For example I can define the
following extension method on the string class:

public static class StringExtensions
{
  public static void MyStringExtensionMethod(this string input, int number)
  {
    Console.Out.WriteLine(String.Format(input, number));
  }
}

Then I call it in my code

string s = "My number is {0}";
s.MyStringExtensionMethod(10);

And the output is: My number is 10

Well, we don't expect the compiler to edit the existing string class
and add a method to it nor do we think a new class is created which
inherits the string class (it is sealed!).
So what did the compiler do? A hint to that is the definition of an
extension method. It is static in a static class. In fact the only
thing that makes this method an extension is the fact we added the
"this" keyword in the definition. The simple answer is that the
compiler did nothing. The only thing happened is that the "this"
keyword enabled the dot syntax but the call remained the same. In this
case the actual call to the method is
MyStringExtensionMethod(s,10);

Let's compare the following code with Reflector

static void Main(string[] args)
{
   string s = "My number is {0}";
   s.MyStringExtensionMethod(10);
   StringExtensions.MyStringExtensionMethod(s, 10);
}

The disassembly is somewhat strange:

private static void Main(string[] args)
{
   string s = "My number is {0}";
   s.MyStringExtensionMethod(10);
   s.MyStringExtensionMethod(10);
}

But we see that the IL code is exactly the same and that this is only
the interpretation of the tool

   L_0007: ldloc.0
   L_0008: ldc.i4.s 10
   L_000a: call void
Macros.StringExtensions::MyStringExtensionMethod(string, int32)
   L_000f: nop
   L_0010: ldloc.0
   L_0011: ldc.i4.s 10
   L_0013: call void
Macros.StringExtensions::MyStringExtensionMethod(string, int32)
   L_0018: nop
"using" statement 

The "using" statement is used to create, work with, and dispose an
IDisposable object. Probably the most common case to meet this
statement is when working with streams.
Lets look at a typical piece of code that uses the "using" statement.

using (StreamReader reader = new StreamReader("MyFile.txt"))
{
    Console.Out.WriteLine(reader.ReadToEnd());
}

In this code we print the content on a text file onto the console. We
don't want to lock the file after we finish reading so we free it.
This is exactly what the using statement does for us. We could simply
write the following code and not use the using statement:

    StreamReader myReader = new StreamReader("MyFile.txt");
    try
    {
      Console.Out.WriteLine(myReader.ReadToEnd());
    }
    finally
    {
      myReader.Dispose();
    }

Lets view the result in Reflector:

    using (StreamReader reader = new StreamReader("MyFile.txt"))
    {
      Console.Out.WriteLine(reader.ReadToEnd());
    }
    using (StreamReader myReader = new StreamReader("MyFile.txt"))
    {
      Console.Out.WriteLine(myReader.ReadToEnd());
    }

Again, the tool was smarter and formatted the code to the same statement.


"event" statement

Yes, you might not have noticed this but the "event" keyword is actually a
macro. I will not try to recreate the code because, as you will soon
see, it is quite complex but it is nice to have a look at it.

We will include this simple statement in our code and see the resulting IL code:

public event EventHandler<EventArgs> MyEvent;

This is a shorthand notation for an event with the signature void
Func(object sender, EventArgs args)
Now lets look at the resulting C# code:

  // Fields
   private EventHandler<EventArgs> MyEvent;
 
   // Events
   public event EventHandler<EventArgs> MyEvent;

First of all the compiler added an additional member of type
EventHandler<EventArgs> with the same name as the event (this is the
member you are actually using).
If we check further we can see that this is simply a MulticastDelegate
(the IL of its definition is):
.class public auto ansi serializable sealed
EventHandler<(System.EventArgs) TEventArgs> extends
System.MulticastDelegate


 So we are actually working with a MulticastDelegate but we also get
two custom method for adding and removing event handlers to it:

public void add_MyEvent(EventHandler<EventArgs> value)
{
   EventHandler<EventArgs> handler2;
   EventHandler<EventArgs> myEvent = this.MyEvent;
   do
   {
       handler2 = myEvent;
       EventHandler<EventArgs> handler3 = (EventHandler<EventArgs>)
Delegate.Combine(handler2, value);
       myEvent =
Interlocked.CompareExchange<EventHandler<EventArgs>>(ref this.MyEvent,
handler3, handler2);
   }
   while (myEvent != handler2);
}

and

public void remove_MyEvent(EventHandler<EventArgs> value)
{
   EventHandler<EventArgs> handler2;
   EventHandler<EventArgs> myEvent = this.MyEvent;
   do
   {
       handler2 = myEvent;
       EventHandler<EventArgs> handler3 = (EventHandler<EventArgs>)
Delegate.Remove(handler2, value);
       myEvent =
Interlocked.CompareExchange<EventHandler<EventArgs>>(ref this.MyEvent,
handler3, handler2);
   }
   while (myEvent != handler2);
}

And this is the code that get executed when you call "+= " or "-=" on
your event member.

[edit: The next section was not in the original post]

"lock" statement

Perhaps the most well known macro in C# is the lock statement. The lock statement is used to create a critical section in your code which relies on some object which is used as a lock on that section of code. The "lock" keyword is just a macro for a try-finally block which uses the Monitor class to create a critical section.

For example the following code:

      object myLock = new object();
      lock (myLock)
      {
        Console.WriteLine("Inside MyLock");
      }
 
      Monitor.Enter(myLock);
      try
      {
        Console.WriteLine("Inside MyLock");
      }
      finally
      {
        Monitor.Exit(myLock);
      }
 

When compiled and decompiled using Telerik justDecompile will result in the following code:

 object myLock = new object();
 Monitor.Enter(object obj = myLock);
 try
 {
  Console.WriteLine("Inside MyLock");
 }
 finally
 {
  Monitor.Exit(obj);
 }
 Monitor.Enter(myLock);
 try
 {
  Console.WriteLine("Inside MyLock");
 }
 finally
 {
  Monitor.Exit(myLock);
 }

We can clearly see that the two statements are identical (except this somewhat strange syntax generated by Mono.Cecil in the first Monitor.Enter call.

I hope you enjoyed this post.

Thank you for reading,

Boris

Helpful tools for the weary programmer Part 2

Hi All,


This is the second part of my review of the tools I use in my daily work. If you likes the first part you will surely like the second.


Code decompilation or disassembly

The third category of useful tools are disassembly tools. If I were to make this post couple of months ago it would probably contain only Red-Gate Reflector but recently Red-Gate decided to charge money for even the basic version of Reflector so I will survey two alternative tools which are currently in the beta stage. 

The first tool comes from the guys at #Develop and is called ILSpy. ILSpy can take a compiled .NET assembly and regenerate the original code (or at least something close to the original). In the current beta it can show you the code in both C# and IL and it is quite accurate in the generated code. You can save the generated code to a code file easily from the menu. ILSpy supports search and navigation directly from the code editor and browsing of dependent dlls. One of the big tests of a decompiler is the ability to decompile itself which ILSpy does perfectly.

Another contender to the crown comes from the guys at JetBrains (the ones who make ReSharper) in the form of dotPeek. The UI of dotPeek looks similar to ILSpy (and to Reflector) but offers richer menus. I found it somewhat difficult to navigate through the code editor and had to search through the context menu items. At times the navigation didn't work at all. The generated code was quite accurate and at some places clearer than the code generated by ILSpy. It had no difficulty in decompiling itself 


The third tool comes from Telerik and is called justDecompile. Currently it is in the Beta stage and free. The UI is again similar although somewhat slick. I didn't manage to get any useful data with this tool as it failed to decompile even the simplest of codes. It is clearly not ready for real user but definitively worth to keep in mind.


This list cannot be complete without ILDasm (the tool that comes with .NET, search ildasm in your Everything). I like this tool because you are able to view the manifest of a dll in a convenient way. You can also use it to check the dependencies of a specific dll but only for one level. The biggest disadvantages of this tool is that the code is decompiled into IL and there is no easy navigation between assemblies or even within the same assembly.

ILSpy decompilation of the Object class

dotPeek decompilation of the Object class

justDecompile decompilation of the Object class

Snooping/Spying a running application
You probably know the following scenario: you add some control to your application and see it well in the designer but when the application is run it is nowhere to be found,or a scrollbar appears out of nowhere and you have no idea which control shows it. It is simple to see the dynamic structure of your running application while it runs using one of the following tools:
Spy++ for Win32 based applications (anything which is GDI based and not drawn by DirectX). This tool is installed with Visual Studio and is easy to use. When you run it, it shows all the window handles of your top level windows in a tree and you can drill down to the smallest of windows (in GDI everything is a window). You can highlight a certain window by using its handle or find a certain window by pointing at it with the mouse (using the find target tool). When the window is found you can track all the messages sent to that window.


If you try to use Spy on a WPF application you will have a surprise on your hands. Any WPF Window contains only one GDI window because the rendering is done internally using DirectX. In order to inspect a WPF application I use a different tool called Snoop. This tool is essentially like Spy (but somewhat closer to Firebug). Pointing Snoop on a WPF application will give you the full Visual Tree of this application. For each item in this tree you will be able to see and sometimes edit its properties. Snoop will also tell you who set each property so you will finally be able to see which animation stuck the height of your button.

Snooping justDecompile which decompiles the Object class

These are the main tools I use in my daily work. I very much recommend that you try each of the mentioned tools at least once to see if it is useful for you.


Thank you for reading
Boris.