Friday, February 29, 2008

Linq to Object vs Linq to SQL and custom predicates

One of the most interesting issues of Linq is the ability to use arbitrarily complicated predicates inside linq expressions. You are also aware of the fact that the there are two equivalent syntax possibilities:

List<int> l = new List<int> { 1, 2, 3, 4, 5 };
 
/* linq-style syntax */
foreach ( int v in
    from i in l
    where i > 2
    orderby -i
    select i )
    Console.Write( v );
 
/* is translated to method invocation sequence */
foreach ( int v in l.Where( i => i > 2 ).OrderBy( i => -i ) )
    Console.Write( v );

No matter what syntax you prefer, sooner or later you will realize that expressing filtering and ordering clauses in an explicit form inside linq expression is not a good way to write reusable code.


What if you actually have defined some filtering/sorting clauses in the business logic of the application and you wish to be able to use them both in application logic and in linq expressions?


Let's write a predicate and try to use it in linq-style syntax and method-invocation-sequence syntax.

static Func<int, bool> NumberIsGreaterThan( int K )
{
    return i => i > K;
}


The latter is easy:

foreach ( int v in l.Where( NumberIsGreaterThan( 2 ) ).OrderBy( i => -i ) )
    Console.Write( v );


The former can be expressed in two different ways, using method invocation inside linq-style expression:

foreach ( int v in
    from i in l.Where( NumberIsGreaterThan( 2 ) )
    orderby -i
    select i )
    Console.Write( v );


or the application of the predicate to the parameter:

foreach ( int v in
    from i in l
    where NumberIsGreaterThan( 2 )(i)
    orderby -i
    select i )
    Console.Write( v );


It is interesting to explain the last example. Well, the NumberIsGreaterThan predicate is of type Func<int,bool> and in the where part of linq expression the compiler expects bool expression which I create by applying the parameter to the predicate.

The bubble breaks when you realize that predicates in the way we express them above do not work in Linq to Sql. You'll just end with the nice exception saying that the "method WhateverYouCallIt has no supported translation to SQL".

Why this is so? You see, there are in fact two different linq approaches.

First one is built into the .NET, works on IEnumerable collections and you know it as Linq to Objects. The other one has few example implementations built into the .NET but rather operates on IQueryable collections.

In the latter case, instead of executing a sequence of methods, the compiler rather builds the expression tree for the whole linq expression and passes the tree to the IQueryable implementation saying: "do whatever you like with this expression tree, it's up to you".

(one specific implementation known as Linq to SQL just traverses the expression tree and builds a sql clause that correspond to the tree)

What's the relation of this to our example with custom predicates in linq expressions?

Well, it seems that if instead of passing Func<T, bool>  as a filtering predicate you'll pass it's expression tree, Linq to SQL will be able to step into this tree and build a SQL clause for it.

And how do you build an expression tree from the function? Well, you'll be surprised:



static Expression<Func<int, bool>> NumberIsGreaterThan( int K )
{
    return i => i > K;
}


Compare it with the former definition:



static Func<int, bool> NumberIsGreaterThan( int K )
{
    return i => i > K;
}


Is that all? Does it really make such a huge difference to put Expression<...> over the method's signature?

Well, yes, it does. By putting Expression<...> over method's signature you inform the compiler to automatically build the expression tree of the method rather than just to return the method body.

(you can also build Expressions directly in the code but it's beyond the scope of this post).

This tiny change has significant difference for the Linq to SQL and other Linq to IQueryable implementations - now, as the expression tree is placed in linq expression, the tree walker will likely correctly handle the tree structure for the predicate (even though the predicate body is defined outside of the linq expression).

Is it all?

Unfortunately, no. Defining predicates as Expression<...>  helps the Linq to IQueryable but confuses Linq to Objects!

Why?! Well, Linq to Objects expects predicates to be defined as Func<T,bool> not Expression<Func<T,bool>>! Is there a way to fix it?

Fortunately, yes, there is. You can "deexpression" the expression tree by compiling it using the Compile() method:



static Expression<Func<int, bool>> NumberIsGreaterThan( int K )
{
     return i => i > K;
}
 
...
 
/* all three syntax possibilities */
 
foreach ( int v in
     from i in l
     where NumberIsGreaterThan( 2 ).Compile()(i)
     orderby -i
     select i )
     Console.Write( v );
 
 foreach ( int v in
     from i in l.Where( NumberIsGreaterThan( 2 ).Compile() )
     orderby -i
     select i )
     Console.Write( v );
 
 foreach ( int v in l.Where( NumberIsGreaterThan( 2 ).Compile() ).OrderBy( i => -i ) )
     Console.Write( v );


Be aware of these differences between Linq to Objects and Linq to something-implementing-IQueryable and remember that in both cases you can use clauses defined as methods or properties in the business logic layer of your application.

Friday, February 22, 2008

Using LinQ to find largest group of anagrams in a given set of words

A friend of mine, PaweĊ‚ R., who is an academic lecturer once gave following task to his students:

Two words are anagrams if they contain the exactly same number of the same letters. Write a program which, for given a set of words, will find a largest group of anagrams from this set. If more than one set exists with the same number of words, write the contents of each set.

A large set of words to play with this problem can be downloaded from my friend's page.

The task is not difficult at all - you just have to group words which are anagrams and then find the largest group. The easiest way to group is to split each word, sort letters ascending to get the hash key that uniquely identifies the word and then store the word in a hashtable using the key.

For example, having "leaf", "flea", "shore" and "horse", you split each word, sort letters and you get two distinct hash keys "aefl" and "ehors" and each hash group containst exactly two words. Let's call such hash a norm of a word.

It is easy to write a program in C# just few dozens of lines long but if are you a LinQ guy you would probably love to try to solve this task using LinQ.

I strongly recommend to stop reading now. Try to solve this task by yourself. You can start with sligtly simplified version: do not find all largest groups of anagrams, find just any largest group.

Are you ready:

// from the collection of words
( from slowo in File.ReadAllLines( "slowa.txt", Encoding.GetEncoding( "iso-8859-2" ) )
      group slowo by
          // group by the anagram "norm"  
          new string(
                // split the word into letters
              ( from letter in slowo.ToLower().ToCharArray()
                // and sort letters
                orderby letter
                select letter ).ToArray() )
          // so we have groups indexed by "norm"
          into anagramy
      // order this groups so the largest group is the first  
      orderby anagramy.Count() descending
      select anagramy.ToArray()
    ).First()

You probably came up with something similar to this. When I test it on the large set of words from the link given above, I get a group of seven words, just foreach the result and you will see them.


Now something more complicated - let's find all largest groups, not just the first one. To accomplish this we just group these groups of words by the size of the group and take the first groupped group of words. Sounds funny? Well, take a look:



foreach ( string[] tablicaanagramow in
    // tablica is a list of groups of words
    ( from tablica in
        // return list of groups
        ( from slowo in File.ReadAllLines(
                        "slowa.txt", Encoding.GetEncoding( "iso-8859-2" ) )
          group slowo by
              new string(
                  ( from letter in slowo.ToLower().ToCharArray()
                    orderby letter
                    select letter ).ToArray() )
              into anagramy
              // we do not have to orderby anagramy.Count() descending
              // since groups of anagrams are groupped
              select anagramy.ToArray()
        )
     // group by the group size
     group tablica by tablica.Count() into tablicatablic
     // and order by the size of any group from the group :)
     orderby tablicatablic.First().Count() descending
     select tablicatablic.ToArray()
     ).First() )
 {
        foreach ( string slowo in tablicaanagramow )
            Console.Write( slowo + "," );
        Console.WriteLine();
 }

Isn't LinQ amazing?

Thursday, February 21, 2008

Unable to cast object of type 'iTextSharp.text.Paragraph' to type 'iTextSharp.text.Table'

If you dig around the issue you will quickly discover that there are two possible solutions:

  • use <ignore> attribute
  • delete whitespaces between iTextXML tags

Luckily, another simple solution exists: the Parse method of ITextHandler accepts XmlTextReader as a parameter. You just use this feature:

XmlTextReader xmlTemplateReader = new XmlTextReader( source );
/* 
 *  this is crucial for iText to work correctly 
 *  WITHOUT <ignore> and
 *  WITH whitespaces
 *  since whitespaces are automatically removed from the xml
 *
 *  remove the line to see the exception
 */
xmlTemplateReader.WhitespaceHandling = WhitespaceHandling.None;
 
/* iTextSharp stuff follows */
ITextHandler xmlHandler = new ITextHandler( document );
xmlHandler.Parse( xmlTemplateReader );

There is also another possibility that leads to this exception - it is when the XML document contains table data that do not match the schema. For example if you have:



<itext author="Bruno Lowagie" title="curriculum vitae">
  <chapter numberdepth="0">
    <section numberdepth="0">
      <title font="Times New Roman" encoding="CP1250" size="13" align="Center" 
       leading="13">Title</title>
      <table width="100%" widths="70;70;70" cellspacing="0" cellpadding="2" columns="3" 
       borderwidth="1" left="true" right="true" top="true" bottom="true" >
        <row>
          <cell borderwidth="1" left="true" right="true" top="true" bottom="true" horizontalalign="Center" verticalalign="Default" colspan="3" grayfill="0.65">
            <phrase font="Times New Roman" encoding="CP1250" size="12" style="bold"></phrase >
          </cell>
        </row>
        SOMETEXTHERE
      </table>
    </section>
  </chapter>
</itext>
Note the misplaced "SOMETEXTHERE".

Friday, February 8, 2008

Web Application vs ClickOnce + WebService - how to share Forms Authentication

One of the most powerful technologies available on the .NET platform is the ClickOnce which makes it possible to implement selected components of a web application as desktop applications.

It is a common architectural pattern to build a web service for the clickonce desktop component so that no matter which user interface technology runs on the client side (web or desktop), the application logic is always executed on the server side. It is also a common pattern to secure the web application using Forms Authentication.

This artice focuses on following issue: sharing the forms authentication between web and desktop components of the application.

The Ultimate Goal

My goal is to build a typical web application secured with Forms Authentication. The application will expose selected parts of its functionality as a ClickOnce application. What I'd like to have is a way to run the ClickOnce application from within the web application and share the identity a user is logged as. In other words - when a user authenticates via the login page of the web application, he/she should not be forced to reauthenticate when the ClickOnce application starts but rather the ClickOnce application should automatically share the user credentials with the web application.

The solution should be also secured in a sense that users who are not authenticated in a web application should not be able to execute any methods in the ClickOnce application that require the web service call.

In yet other words - both web application and the ClickOnce application should share the same Forms Authentication.

The Solution

The solution is based solely on the Forms Authentication semantics, specifically - the FormsAuthenticationModule.

You see, on succesfull login, a cookie is appended to the server's response and the cookie is passed between a web browser and the application server. However, from the application server's perspective there's no difference between a web browser call to a web page and a ClickOnce application call to a web service. In both cases the FormsAuthenticationModule checks if the authentication cookie is properly passed by the HTTP protocol and if this is so, the application server treats the incoming request as authenticated.

If we would be able to somehow pass the authentication cookie from the web page to the ClickOnce application (so that the authentication cookie would be appended to any web service calls) the issue would be solved. Fortunately, this is not difficult at all!

First, build your web application as usual. Implement your MembershipProvider and the login page. Then, on a selected web page put a link to invoke the ClickOnce application.

<asp:HyperLink ID="TheLinkButton" runat="server">
    Run my ClickOnce application</asp:HyperLink>

The hyperlink will be dynamically evaluated so that the authentication cookie would be passed to the ClickOnce application:



protected void Page_Load( object sender, EventArgs e )
 {
     this.TheLinkButton.NavigateUrl = GenerateUrl;
 }
 
 protected string GenerateUrl
 {
     get
     {
         // if the authentication cookie is set within the web application
         // (it should be since a user is authenticated)
         if ( this.Request.Cookies[FormsAuthentication.FormsCookieName] != null )
         {
             string LinkParams =
                 string.Format(
                     "SIGMA={0}",
                     this.Request.Cookies[FormsAuthentication.FormsCookieName].Value );
 
             // pass the authentication cookie to the ClickOnce application
             return this.ResolveUrl( string.Format( "~/co/WindowsApplication1.application?{0}", LinkParams ) );
         }
         else
             return string.Empty;
     }
 }

Second, create a web service for the ClickOnce application and secure each method with declarative check against not authenticated calls:



[WebService( Namespace = "http://tempuri.org/" )]
[WebServiceBinding( ConformsTo = WsiProfiles.BasicProfile1_1 )]
[ToolboxItem( false )]
public class Service1 : System.Web.Services.WebService
{
 
    [WebMethod]
    // this is crucial to secure the call 
    [PrincipalPermission( SecurityAction.Demand, Authenticated = true )]
    public string HelloWorld()
    {
        // dummy method so return anything, for example the user name
        if ( this.User != null )
            return this.User.Identity.Name;
        else
            return string.Empty;
    }
}

Third, in your ClickOnce application invoked from the web page read the form authentication cookie parameter:



public static Dictionary<string, string> UriArgs()
{
    Dictionary<string, string> nameValueTable = new Dictionary<string, string>();
    if ( System.Deployment.Application.ApplicationDeployment.IsNetworkDeployed )
    {
        string url = 
          System.Deployment.Application.ApplicationDeployment.CurrentDeployment.ActivationUri.AbsoluteUri;
        string queryString = ( new Uri( url ) ).Query;
        if ( queryString != "" )
        {
            string[] nameValuePairs = queryString.Split( '&' );
            bool firstVar = true;
            foreach ( string pair in nameValuePairs )
            {
                string[] vars = pair.Split( '=' );
                if ( firstVar )
                {
                    firstVar = false;
                    if ( vars[0].Contains( "?" ) )
                    {
                        vars = new string[] { vars[0].Trim( '?' ), vars[1] };
                    }
                }
                if ( !nameValueTable.ContainsKey( vars[0] ) )
                {
                    nameValueTable.Add( vars[0], vars[1] );
                }
            }
        }
    }
 
    return ( nameValueTable );
}

Fourth, pass the authentication cookie (available now to the ClickOnce application) to each Web Service call:



// create web service proxy and pass authenticaiton cookie to it
TheService.Service1 serv
 {
     get
     {
         TheService.Service1 s = new WindowsApplication1.TheService.Service1();
 
         // demonstration only
         s.Url = textBox1.Text;
 
         // initialize the proxy's cookie container
         s.CookieContainer = new System.Net.CookieContainer();
 
         // pass anything available in ClickOnce uri parameters to the web service call
         // as cookie
 
         // remember that forms authentication cookie will be passed here since
         // its name and value were passed as uri parameters by the web page
         // the ClickOnce application had been invoked from 
         foreach ( string CookieName in Program.UriArgs().Keys )
         {
             System.Net.Cookie cookie =
                 new System.Net.Cookie(
                     CookieName,
                     Program.UriArgs()[CookieName],
                     "/",
                     "yourdomain.here" );
             // ciacho z aspnet_sessionid
             s.CookieContainer.Add( cookie );
         }
 
         return s;
     }
 }

And this is it - the identity is shared between the web application and its ClickOnce component. Even if the ClickOnce component is invoked by an unauthenticated user, any web service call from within the ClickOnce component will fail since the application service is protected by the PrincipalPermission attribute.


Download the source code here. Description inside.