Bug Vanquisher

23 October 2009

Story of a Parser

Filed under: Dev inside!, Tips — Tanveer Badar @ 8:31 AM

A quick and dirty, precedence parser I wrote in about 2 hours. Minimal error handling, (may be) able to parse expressions of the form

expr := expr combiner expr | expr op ( expr | list ) | term
combiner := AND | OR
op := ‘=’ | in
list := ( term ) | ( term , list )
term := ‘identifer or literal’

op will include usual comparison operators soon. List can only be specified if op is ‘in’. Code follows, you should be able to add the missing pieces yourself as not much more can be revealed.:

public static partial class Parser
{
    static Expression BuildTree( string expr )
    {
        int startIndex = 0;
        Stack<Expression> stack = new Stack<Expression>( );
        BuildTreeRecursive( expr , ref startIndex , stack );
        return stack.Pop( );
    }

    private static void BuildTreeRecursive( string expr , ref int startIndex , Stack<Expression> stack )
    {
        string combiner = null;
        while( startIndex < expr.Length )
        {
            Expression expr1 = null;
            if( string.IsNullOrEmpty( combiner ) )
            {
                expr1 = RecognizeExpression( expr , ref startIndex );
                EatWhiteSpace( expr , ref startIndex );
                combiner = RecognizeOperator( expr , ref startIndex );
            }
            Expression expr2 = null;
            switch( combiner.ToUpper( ) )
            {
                case "AND":
                    expr2 = RecognizeExpression( expr , ref startIndex );
                    stack.Push( new BinaryExpression
                    {
                        LeftSide = expr1 ,
                        RightSide = expr2 ,
                        Type = Expression.Operator.And
                    } );
                    EatWhiteSpace( expr , ref startIndex );
                    combiner = RecognizeOperator( expr , ref startIndex );
                    EatWhiteSpace( expr , ref startIndex );
                    break;
                case "OR":
                    BuildTreeRecursive( expr , ref startIndex , stack );
                    if( stack.Count > 0 )
                        expr2 = stack.Pop( );
                    if( stack.Count > 0 )
                        expr1 = stack.Pop( );
                    stack.Push( new BinaryExpression
                    {
                        LeftSide = expr2 ,
                        RightSide = expr1 ,
                        Type = Expression.Operator.Or
                    } );
                    EatWhiteSpace( expr , ref startIndex );
                    combiner = RecognizeOperator( expr , ref startIndex );
                    EatWhiteSpace( expr , ref startIndex );
                    break;
            }
        }
    }

    private static Expression RecognizeExpression( string expr , ref int startIndex )
    {
        EatWhiteSpace( expr , ref startIndex );
        string attrib = RecognizeAttribute( expr , ref startIndex );
        EatWhiteSpace( expr , ref startIndex );
        string op = RecognizeOperator( expr , ref startIndex );
        EatWhiteSpace( expr , ref startIndex );
        switch( op.ToUpper( ) )
        {
            case "=":
                string value = RecognizeWord( expr , ref startIndex );
                return new BinaryExpression
                {
                    LeftSide = new ConstantExpression( attrib ) ,
                    RightSide = new ConstantExpression( value ) ,
                    Type = Expression.Operator.Equal
                };
            case "IN":
                List<string> values = RecognizeList( expr , ref startIndex );
                return new BinaryExpression
                {
                    LeftSide = new ConstantExpression( attrib ) ,
                    Type = Expression.Operator.In
                };
        }
        return new Expression( );
    }

    private static List<string> RecognizeList( string expr , ref int startIndex )
    {
        List<string> values = new List<string>( );
        if( expr.Length <= startIndex || expr [ startIndex ] != ‘(‘ )
            return values;

        ++startIndex;

        do
        {
            EatWhiteSpace( expr , ref startIndex );
            values.Add( RecognizeWord( expr , ref startIndex ) );
            if( expr.Length <= startIndex || expr [ startIndex ] != ‘,’ )
                break;
        } while( startIndex < expr.Length );

        EatWhiteSpace( expr , ref startIndex );

        if( expr.Length <= startIndex || expr [ startIndex ] != ‘)’ )
            return values;

        ++startIndex;

        return values;
    }

    private static string RecognizeAttribute( string expr , ref int startIndex )
    {
        return RecognizeWord( expr , ref startIndex );
    }

    private static string RecognizeOperator( string expr , ref int startIndex )
    {
        int start = startIndex;
        while( startIndex < expr.Length && !char.IsWhiteSpace( expr [ startIndex ] ) )
            ++startIndex;
        if( start != startIndex )
            return expr.Substring( start , startIndex – start );
        return string.Empty;
    }

    private static void EatWhiteSpace( string expr , ref int startIndex )
    {
        while( startIndex < expr.Length && char.IsWhiteSpace( expr [ startIndex ] ) )
            ++startIndex;
    }

    private static string RecognizeWord( string expr , ref int startIndex )
    {
        int first = expr.IndexOf( "’" , startIndex ) , second = first != -1 ? expr.IndexOf( "’" , first + 1 ) : -1;
        if( first != -1 )
            if( second != -1 )
            {
                startIndex = second + 1;
                return expr.Substring( first , second – first );
            }
            else
            {
                startIndex = expr.Length;
                return expr.Substring( first );
            }
        return string.Empty;
    }
}

This is what you should pass.

string expr = "’attribute1′ = ‘value1’ and ‘attribute2’ = ‘value2’ or ‘attribute3’ in (‘value3’) or ‘attribute4’ = ‘value4’";

Expression expression = Parser.BuildTree( expr );

21 October 2009

Extension Method Abuse

Filed under: Dev inside! — Tanveer Badar @ 4:03 PM

public static <Return Type> GetColumns( this int column , IList< Conditions > conditions ) { /* blah blah blah */ }

10 October 2009

The Composition Which Isn’t

Filed under: Dev inside!, Tips — Tanveer Badar @ 5:11 PM

Imagine someone trying to write a class which composes two streams together. You better make it a stream itself, meaning something like this:

class CompositeStream : IStream
{
public:
    CompositeStream( IStream* first , IStream* second );
    // blah blah blah
};

Or people will find it amusing that your class isn’t a stream itself.

Similarly, for a mathematical library if you provide a composing function it better be a math-op itself or someone is going to end up in a sticky situation.

class SuperDuperComposingFunction : MathOp
{
public:
    SuperDuperComposingFunction( const std::vector< MathOp* >& operations );
    // blah blah blah
};

Or a cache manager for that matter. It is easy to provide default implementations for simple cache algorithms like LFU, LRU, FIFO etc. But things get interesting if you provide an extensibility point for others to compose them together. Who knows whether I want to archive emails which are older than 3 weeks and I haven’t read them more than once. Things are even more interesting if people need to sub-class your cache manage in order to use composite cache policies.

In the end, it helps to read these things instead of arguing when someone says “yeah sure, great idea. Just one thing, make it a ICachePolicy itself.”.

This post was brought to you by “Working with goons”.

16 September 2009

When Oracle Met A Computer Architect

Filed under: Bugz, Dev inside!, Tips — Tanveer Badar @ 7:49 PM

Oracle can’t handle more than 1000 expressions in a single in clause. (Really stupid restriction, I know and here’s the tip: you can do (, ,,,,,) or abc in (,,,,,,) ad infinitum).

When compilers software pipeline a loop, they calculate two things at first. The remainder and the dividend.

(This post got too keyword heavy. Matrix fans will curse me that its the other Oracle. That Oracle’s users will not find all ORA-xyz error descriptions here. Architects may not have any interest in writing computer code. Computer architects will not see any processors discussed. One post to rule them all. ]:) )

The problem at hand was hand generating a query with in clause in its where section. Number of expressions was unbounded. And the genius who came up with the loop did this:

for( int i = 0 , n = 0 ; i < count ; ++i )
{
    n++;
    if( n == 1000 )
    {
        quwry += " ) or in ( ";
        n = 0;
    }
    query += list [ i ] + ‘,’;
}
query = query.Remove( query.Length – 1 , 1 );

Remember this is the work of someone who has never heard about software pipeline and may never know what gcc or cl are. Thinking one level above will help us arrive at the correct solution (notice, there is nothing wrong functionally with the above code either. It does what it says it does.):

int n = numbers.Count / stride , k = numbers.Count % stride;
StringBuilder builder = new StringBuilder( );
if( n > 0 )
{
    builder.AppendFormat( "'{0}’" , numbers [ 0 ] );
    for( int j = 1 ; j < stride ; j++ )
        builder.AppendFormat( " , ‘{0}’ " , numbers [ j ] );
    for( int i = 1 ; i < n ; ++i )
    {
        builder.Append( separator );
        builder.AppendFormat( "'{0}’" , numbers [ i * stride ] );
        for( int j = i * stride + 1 ; j < ( i + 1 ) * stride ; j++ )
            builder.AppendFormat( " , ‘{0}’ " , numbers [ j ] );
    }
}
if( k > 0 )
{
    if( n > 0 )
        builder.Append( separator );
    builder.AppendFormat( "'{0}’" , numbers [ n * stride ] );
    for( int j = n * stride + 1 ; j < numbers.Count ; ++j )
        builder.AppendFormat( " , ‘{0}’ " , numbers [ j ] );
}

No repetitive checking of one variable which also displays off-by-1 error. And which is also mission the other correction in first line of this post in bold.

13 September 2009

is This Beautiful?

Filed under: Dev inside!, Rant vs Vent — Tanveer Badar @ 10:01 PM

CodeTypeDeclaration tablerow = new CodeTypeDeclaration
{
    IsClass = true ,
    Name = ( row [ "TABLE_NAME" ] + "Row" ) ,
    IsPartial = true ,
    BaseTypes = { datarowref } ,
    Members =
    {
        new CodeMemberField( ( row [ "TABLE_NAME" ].ToString( ) + "DataTable" ) , "table" + row [ "TABLE_NAME" ] ),
        new CodeConstructor
        {
            Attributes = MemberAttributes.Public ,
            Parameters = { parameter } ,
            BaseConstructorArgs = { buildervar } ,
            Statements =
            {
                new CodeAssignStatement( new CodeFieldReferenceExpression( thisref , "table" + row [ "TABLE_NAME" ] ) , new CodeCastExpression( row [ "TABLE_NAME" ].ToString( ) + "DataTable" , tablefield ) )
            }
        }
    }
};

To some, it may be but for me it is nauseating. What happened to all those .Add and .Insert calls?

CodeDom Fun

Filed under: Dev inside! — Tanveer Badar @ 5:52 PM

Writing CodeDom statements by hand is no fun. Visual studio team members who wrote the code to generate data sets must be the finest. For example, guess what would be the output of this statement:

constructor.Statements.Add( new CodeAssignStatement( new CodeFieldReferenceExpression( new CodeThisReferenceExpression( ) , "table" + row [ "TABLE_NAME" ] ) , new CodeCastExpression( row [ "TABLE_NAME" ].ToString( ) + "DataTable" , new CodeFieldReferenceExpression( new CodeThisReferenceExpression( ) , "Table" ) ) ) );

Just something like

this.tableDT = ( DTDataTable ) (this.Table );

Side note:

I am back!

24 April 2009

Tales From Interviewer’s Desk

Filed under: Dev inside!, Fun, Tips — Tanveer Badar @ 8:24 PM

Part 1:

How to reverse a string in-place?

Take 1: (Fresh)

string reverse( string str )
{
    char ch = str [ 0 ];
    foreach( int i = 0 ; i < str.length ; ++i )
        Response.RedirectWrite( str [ str.length – i ] ) + ch.tostring( );
}

Take 2: (Big words, no knowledge)

string reverse( object obj )
{
    string str = TypeCaste.tostring( obj );
    stack< ch > s;
    for( int i = 0 ; i < length ; ++i )
        s.push( str.charat( i ) );
    for( i = 0 ; i < length ; ++i )
        str.insertat( 0 , s.pop( ) );
}

Take 3: (2.5  year experience in C#)

string reverse( object obj )
{
    if( typeof( obj ) == "string" )
    {
        for( int i = 0 ; i < obj.length ; ++I )
        {
            char ch = str [ i ];
            str [ i ] = str [ length – i ];
            str [ length – i ] = ch;
        }
    }
    return obj.tostring( );
}

Take 4: (Fresh)

string reverse( object obj )
{
    if( obj == "string" )
    {
        char ch = str [ 0 ];
        for( int i = 0 ; i < obj.length ; ++I )
            str [ i ] = str [ length – i ];
        str [ str.length ] = ch;
    }
}

26 March 2009

From ntddk.h

Filed under: Dev inside! — Tanveer Badar @ 3:02 AM

//
// This section is specified/returned if the
// ContextFlags word contians the flag CONTEXT_FLOATING_POINT.
//

FLOATING_SAVE_AREA FloatSave;

//
// This section is specified/returned if the
// ContextFlags word contians the flag CONTEXT_SEGMENTS.
//

ULONG   SegGs;
ULONG   SegFs;
ULONG   SegEs;
ULONG   SegDs;

//
// This section is specified/returned if the
// ContextFlags word contians the flag CONTEXT_INTEGER.
//

ULONG   Edi;
ULONG   Esi;
ULONG   Ebx;
ULONG   Edx;
ULONG   Ecx;
ULONG   Eax;

//
// This section is specified/returned if the
// ContextFlags word contians the flag CONTEXT_CONTROL.
//

ULONG   Ebp;
ULONG   Eip;
ULONG   SegCs;              // MUST BE SANITIZED
ULONG   EFlags;             // MUST BE SANITIZED
ULONG   Esp;
ULONG   SegSs;

.
.
.

volatile ULONG DismountCount;

//
// This field indicates the status of the 64-bit COM+ package on the
// system. It indicates whether the Itermediate Language (IL) COM+
// images need to use the 64-bit COM+ runtime or the 32-bit COM+ runtime.
//

Bhahaha!

24 January 2009

New Goodies in Windows 7

Filed under: Dev inside! — Tanveer Badar @ 6:44 PM

To do any development work in Windows 7, you must first get the latest Windows SDK.

Upon reading, things will reveal themselves in the native land enough to cause this (and very few technical things invoke this reaction in me). I am talking about the Ribbon and Animations and Web Services for Windows. And more goodies.

[Edit: Few hours later… I had forgotten to mention Direct2D and DirectWrite.]

Try this stuff!

14 December 2008

CCXML Meets ASP.NET

Filed under: Dev inside! — Tanveer Badar @ 12:50 AM

Oh! Not this:

<%@ Page Language="C#" AutoEventWireup="true" CodeBehind="CallManager.aspx.cs" Inherits="VoiceSite.CallManager" %>
<ccxml version="1.0" xmlns:voxeo="http://community.voxeo.com/xmlns/ccxml">
</ccxml>

But this:

CCXML.CCXMLControl control1 = new CCXML.CCXMLControl( );
control1.Controls.Add( new CCXML.Transition( CCXML.CCXMLEvents.Alerting , "evt" , "init" ) );
System.IO.StringWriter sw = new System.IO.StringWriter( );
control1.RenderControl( new HtmlTextWriter( sw ) );

which results in

<ccxml version="1.0">
<eventhandler>
  <transition name="evt" state="’init’" event="connection.CONNECTION_ALERTING"></transition>
</eventhandler>
</ccxml>

A work in progress. :)

Older Posts »

Blog at WordPress.com.