I recently read Beautiful Code which contains articles from several well known programmers about the code they consider beautiful.  In Top Down Operator Precedence, Douglas Crockford discusses the Pratt Parser (named after Vaughan Pratt who wrote the paper on it), also known as the Top Down Operator Precedence parser.  What makes this parsing technique interesting is that the syntax is defined in terms of tokens instead of grammar rules, an interesting way to define a language parser. As an example, Crockford defines the multiplication operator in terms of * token:

symbol("*", 60).led = function (left) {
    this.first = left;
    this.second = expression(60);
    this.arity = "binary";
    return this;
};

A Pratt parser works by reading through a stream of tokens and finding a symbol defined for the current token.  The symbol definition above for the * token defines how to build an abstract syntax tree (AST) node for that part of the token stream. The rest of the parser is defined similarly with symbols and functions for each significant piece of syntax in your language. I could go on about just how a Pratt parser works but someone beat me to it.

After reading about Pratt parsing I attempted my own implementation. I use F# which is a wonderful functional language supporting imperative style programming with mutable state. However, I feel a bit dirty using mutable state in a functional programming language (blame the hidden Haskell programmer in me) so I added the restriction that I will create my Pratt Parser in a pure functional manner.

Monads + Pratt?

Being purely functional meant fully embracing immutability. I manage the parser state by making use of the state monad which I have discussed previously which makes use of the computation expression feature in F#. This creates very clean looking code since the state is being passed along in the background which makes it very easy to string functions together.

To create the monadic Pratt parser I define a few key types which are used throughout the code: Symbol<’ex> and InputState<’ex>.

// Parser states consists of 'a which is the return type of any given parser combinator
// and 'ex which is the user defined type of the AST they are building
type Parser<'a, 'ex> = StateMonad<InputState<'ex>,'a>

// A symbol is the core component of the Pratt Parser. You define how the parsing works
// by defining symbols for operators/tokens
and Symbol<'ex> =
    {
        name : string;
        led : Token -> 'ex -> Parser<'ex,'ex>;
        nud : Token -> int -> Parser<'ex,'ex>;
        lbp : int;
    }

// The state type for the parser. Maintains the list of input tokens, the current token,
// the current symbol and the user defined mapping of tokens to symbols
and InputState<'ex> =
    {
        tokens : seq<Token>;
        token : Token option;
        symbol : Symbol<'ex> option;
        symbolMap : Map<string, Symbol<'ex>>
    }

The InputState<’ex> type defines all the state that is passed between the functions of the parser. It contains:

• Tokens: The sequence of tokens received from the lexer
• SymbolMap: The user defined mapping from a token’s name or value to a parser symbol.
• Token:  The current token that the parser is on
• Symbol: The corresponding symbol for the current token

The Symbol<’ex> type contain the user defined logic for how to parse the pieces of the language.It contains:

• Name: The symbol name matches either a token’s name or value
• Lbp: The left binding power of this symbol. Determines if it will grab the previous expression.
• Nud: The function called when this symbol is executed with no arguments
• Led: The function called when this symbol is executed with the previous expression’s result.

To parse a program you define several symbols and add them to InputState’s initial SymbolMap. The nud and led functions in these symbols will build up pieces of an AST. For example, given an AST defined by the Expression type:

type Expression =
    | Call of Expression * Expression list
    | Cond of Expression * Expression * Expression
    | Let of Expression * Expression
    | Fun of Expression * Expression list * Expression
    | Id of String
    | Int of int
    | Float of float
    | Bool of bool

Here is a symbol which describes how to build an identifier node using the Id data constructor:

// Error function for symbols that don't define led
let errorLed token left =
    parser {
        return! error token "Symbol does not take a left argument"
    }

// The nud function for id which returns an Expression type using the Id data constructor
let idNud token rbp =
    parser {
      return Id token.text
    };

// A symbol for identifiers. Defines a nud function but not a
// led function since identifiers don't consume neighboring tokens
let idSymbol =
    {
        name = "ID";
        lbp = 0;
        nud = idNud;
        led = errorLed;
    }

Most symbols will follow a similar pattern so I created several helper methods to create symbols and build up the symbol map. I won’t go into each here (you can read the source code) but they let you build the symbol map in a declarative way. For example, this is the definition of a symbol map for a simple language:

let languageSymbolMap = Map.empty |>  

                        // Add empty symbols
                        // Will error if called
                        addEmptySymbol ")" |>
                        addEmptySymbol "THEN" |>
                        addEmptySymbol "ELSE" |>

                        // Simple literal values
                        addLiteralSymbol "INT" Int int |>
                        addLiteralSymbol "FLOAT" Float double |>
                        addLiteralSymbol "BOOL" Bool bool  |>

                        // Binary right associative symbols
                        addInfixR "=" 10 neLed |>
                        addInfixR "!=" 10 neLed |>
                        addInfixR "&&" 30 andLed |>
                        addInfixR "||" 30 orLed |>

                        // Binary left associative symbols
                        addInfixL ">" 40 gtLed |>
                        addInfixL ">=" 40 gteLed |>
                        addInfixL "<" 40 ltLed |>
                        addInfixL "<=" 40 lteLed |>
                        addInfixL "+"  50 plusLed |>
                        addInfixL "-" 50 minusLed |>
                        addInfixL "*" 60 timesLed |>
                        addInfixL "/" 60 divideLed |>
                        addInfixL "^" 70 powerLed|>

                        // Custom symbols
                        addSymbol eqSymbol |>
                        addSymbol idSymbol |>
                        addSymbol leftParenSymbol |>
                        addSymbol letSymbol |>
                        addSymbol funSymbol |>
                        addSymbol ifSymbol |>
                        addSymbol endSymbol

Expression Parsing

The heart of the Pratt parser is the expression parsing code which calls the led and nud methods defined on the symbols.  My implementation follows the method in Crockford’s article very closely except that I use recursion instead of a loop and I extend the definition of the nud function to accept a right binding power.

let rec leftBoundExpression rbp token symbol left =
    parser {
        if (rbp < symbol.lbp) then
            do! advance()
            let! newLeft = symbol.led token left
            let! newToken, newSymbol = current()
            return! leftBoundExpression rbp newToken newSymbol newLeft
        else
            return left
    }

let expression rbp =
    parser {
        let! token, symbol = current()
        do!  advance()
        let! left = symbol.nud token rbp
        let! nextToken, nextSymbol = current()
        return! leftBoundExpression rbp nextToken nextSymbol left
    }

Adding the right binding power (rbp) parameter to the nud function makes it possible to parse a call expression like the ones found in Haskell or F#

someFunction arg1 arg2 arg2

To parse this expression the nud method for an someFunction must match the multiple expressions that come after it. This creates an issue since an identifier can be matched in two different ways: as a function call with arguments or as a stand alone identifier. We need to ensure the nud function for arg1 doesn’t try to grab arg2. Passing the right binding power to the nud method solves this since the nud for someFunction can indicate that it wants the next expressions with a high binding power. Below is an updated version of the identifier method’s nud function demonstrating this:

let idNud token rbp =
    parser {
        if rbp < 90 then
            let! args = manyExpressions 90
            if args.Length > 0
            then return Call (token, args)
            else return Id token.text
        else
            return Id token.text
    };

Parser Combinators

In the code above you may have noticed the call to manyExpressions. This function will match as many expressions as it can and then returns them in a list.

let rec manyExpressions rbp =
    parser {
        let! exp = expression rbp
        let! rest =  (manyExpressions rbp)
        return exp :: rest
    } <|> parser.Return []

What is interesting about this function is its base case. It will keep recursing trying to match expressions until it finds a symbol that does not define the nud method which causes the parser to return an error. This is where the <|> parser.Return [] expression takes over.  The <|> symbol is a function defined on the state monad which combines two monads/parsers into one. This kind of function is called a parser combinator. The first parser given to it will execute and if it eventually errors the parsing will backtrack until if finds an alternative (the right argument to <|>) or unwinds the stack completely and returns the error. In the code above the second parser is defined by  parser.Return []  which returns an empty list when the first parser errors.

Those familiar with the Haskell parser combinator library called Parsec may recognize the <|> combinator. In Parsec it is a predictive combinator and will only try the second alternative if the first didn’t consume input. This differs from my implementation which will try the second alternative even if the the first expression consumed hundreds of tokens before it errored.

Parser combinators offer great power since they can be used to effectively provide infinite look-ahead. They make it easy to parse ambiguous language constructs. I only use them in a limited way but there is much room to expand them.

Conclusion

I wasn’t sure at first what a monadic Pratt Parser would look and feel like. However, I am very pleased with how clear and readable it is. The use of computation expressions in F# enabled a simple and concise syntax. The melding of Pratt parsing with parser combinators creates really expressive and powerful parsers. I am interested in exploring this further to see what issues and pitfalls this kind of parser design may have.

All the code for my monadic Pratt parser can be found on this github page. This repository also contains an implementation of a simple functional language which demonstrates using the parser. The key files to look at are:

• Parser.fs– The code for the monadic Pratt parser
• StateMonad.fs– The state monad implementation the parser is built on
• FlangoParserDefs.fs– The definition of a simple language using the parser
• Lexer.fs – The code for a regex based lexer
• FlangoLexDefs.fs – The definition of the tokens for the simple language

This release contains the following changes:

Features

1. Chutzpah is now able to run Jasmine tests in addition to QUnit. This was a large feature and new Chutzpah contributor Ben (Qube) did an amazing job with it.

2. Added a new configuration option to set the timeout on a test file. By default this value is 3000ms but there are many cases when you may have long running tests where you need this to be longer. You can now set this timeout from the command line:

chutzpah.console.exe /timeoutMilliseconds 5000 mytest.js

You can also set this inside of Visual Studio using the newly added options menu. You can find this menu under Tools->Options->Chutzpah.

Bug Fixes

1. Chutzpah now copies over the text fixtures that you set in your html test harness.

2. Added missing doctype on the generated test harness.

3. Fixed bug where multiple references to qunit.js were copied into the generated test harness.

These PowerShell scripts assume your .resx files live in a folder named “Resources” but this can be easily changed.

RenameResource.ps1

param([String]$keyOld, [String]$keyNew)
if(-not $keyOld -or -not $keyOld) {
  echo "RenameResource.ps1 keyOld keyNew"
  return
}

$files=get-childitem Resources *.resx

foreach($file in $files) {
  $xml = [xml](Get-Content $file.FullName)
  $dataNode = $xml.root.data | Where-Object { $_.GetAttribute("name") -eq $keyOld }
  if ($dataNode -ne $null) {
    $dataNode.SetAttribute("name", $keyNew)
    $xml.Save($file.FullName)
  }
}

MoveResource.ps1

param([String]$resourceNameSource, [String]$resourceNameDestination, [string] $keyName)
if(-not $resourceNameSource -or -not $resourceNameDestination -or -not $keyName) {
  echo "MoveResource.ps1 resourceNameSource resourceNameDestination keyName"
  return
}

$sourceFiles = Get-ChildItem "Resources\$resourceNameSource*.resx"
$destFiles = Get-ChildItem "Resources\$resourceNameDestination*.resx"
$mapping = @{}

$sourceFiles | foreach {
  $parts = $_ -split "\."
  $list = New-Object "system.collections.arraylist"
  $list.Add($_) > $null
  if($parts.Length -eq 2) {
    $mapping["en-us"] = $list
  }
  else {
    $mapping[$parts[1]] = $list
  }
}

$destFiles | foreach {
  $parts = $_ -split "\."
  if($parts.Length -eq 2) {
    $mapping["en-us"].Add($_ ) > $null
  }
  else {
    $mapping[$parts[1]].Add($_ ) > $null
  }
}

foreach($pair in $mapping.Values) {
  $sourcePath = $pair[0]
  $destPath = $pair[1]
  $source = [xml](Get-Content $sourcePath)
  $dest = [xml](Get-Content $destPath)

  $keyNodeSource = $source.root.data | Where-Object { $_.GetAttribute("name") -eq $keyName }
  $keyNodeDest = $dest.root.data | Where-Object { $_.GetAttribute("name") -eq $keyName }
  if ($keyNodeSource -eq $null) {
      echo "Key does not exist in source"
      return;
  }
  if($keyNodeDest -ne $null) {
    echo "Key already exists in destination"
    return;
  }
  try
  {
    $newNode = $dest.ImportNode($keyNodeSource.Clone(), $true)
    $source.root.RemoveChild($keyNodeSource) > $null
    $dest.root.AppendChild($newNode) > $null
    $dest.Save($destPath)
    $source.Save($sourcePath)
  }
  catch {
    Write-Host "Error text: " $_
    return
  }
}

Usage

Renaming a resource key:

.\RenameResource.ps1 oldKey newKey

Moving a resource with key “keyName”  from a file named “ResourceFile1.resx” to “ResourceFile2.resx”:

.\MoveResource.ps1 ResourceFile1 ResourceFile2 keyName

This release contains the following changes.

1. Added the Chutzpah console runner as a NuGet package. Once installed the Chutzpah.Console.exe file will be located in the Tools directory of the Chutzpah package.

2. Added ability from command line and Visual Studio to have Chutzpah scan for test files when you execute it on a folder. This helps alleviate a pain point that arises when you break your JavaScript tests into multiple files. Before this change you would have to specify each file individually in the call to the console runner. Now it can take a folder name instead of a file name.

chutzpah.console.exe someFolder/jsTests

When Chutzpah sees that you provided a folder it will scan recursively within that folder for .js files and run any it believes are QUnit test files.

3. Fixed a bug that caused Chutzpah to error on read-only files. This can be quite common since many source control systems can put files in this state.

4. Added a command line flag /OpenInBrowser which makes Chutzpah open the test files in your default browser.  This can be helpful since it allows you to debug the tests more easily.

RequestReduce works by examining the resources in an HTTP request and optimizes them before sending to the user. It will optimize them in the following ways (Matt Wrock’s own words):

• Look for background images that it can sprite. This is the process of combining multiple images into a single image and using some CSS syntax to pull in specific images from that single file into a CSS class’s background.
• Merge these images into a single PNG that is quantized down to 256 colors and then run through optipng for lossless compression. Unsatisfied with the quality I was getting from the popular opensource quantizers, I created a quantizer based on the Wu quantization algorithm and have released that separately as nQuant on codeplex. This often reduces the image size up to 3x smaller than the original.
• Merges all CSS in the head and minifies it.
• Manages the downloads of these CSS and image requests using ETag and expires headers to ensure optimal caching on the browser.

One of the nicest aspects of RequestReduce is how simple it is to start using. Just download the binaries to your website bin folder and add the following to your web.config:

<system.webServer>
 <modules runAllManagedModulesForAllRequests="true">
  <add name="RequestReduce" type="RequestReduce.Module.RequestReduceModule, RequestReduce, Version=1.0.0.0,
  Culture=neutral" />
 </modules>
</system.webServer>

If you are interested I would definitely head over to the RequestReduce website to read the detailed documentation (including advanced configuration options) and the source code (yay for open source ).

Mapper.CreateMap<SourceBaseClass, DestBaseClass>()
    .ForMember(x => x.BasePropTwo, m => m.MapFrom(x => x.BaseProp2));
 
Mapper.CreateMap<SourceChildClass, DestChildClass>()
    .ForMember(x => x.ChildPropTwo, m => m.MapFrom(x => x.ChildProp2))
    .InheritMappingFromBaseType();

However, there are scenarios where you may have one type that is mapping to both a parent and child type and would still want to inherit the parent mapping for the child mapping. If you try this with my previous code it would look like this but not work.

Mapper.CreateMap<SourceClass, DestBaseClass>()
    .ForMember(x => x.BasePropTwo, m => m.MapFrom(x => x.BaseProp2));
 
Mapper.CreateMap<SourceClass, DestChildClass>()
    .ForMember(x => x.ChildPropTwo, m => m.MapFrom(x => x.ChildProp2))
    .InheritMappingFromBaseType();

In order to support this scenario I updated the extension method to take an optional enum which specifies if you want to inherit a mapping that has a base type for the source type, destination type or both.

public enum WithBaseFor
{
    Source,
    Destination,
    Both
}

public static class Inheritance
{
    public static void InheritMappingFromBaseType<TSource, TDestination>(this IMappingExpression<TSource, TDestination> mappingExpression,
                                                                         WithBaseFor baseFor = WithBaseFor.Both)
    {
        var sourceType = typeof (TSource);
        var destinationType = typeof (TDestination);
        var sourceParentType = baseFor == WithBaseFor.Both || baseFor == WithBaseFor.Source
                                   ? sourceType.BaseType
                                   : sourceType;

        var destinationParentType = baseFor == WithBaseFor.Both || baseFor == WithBaseFor.Destination
                                        ? destinationType.BaseType
                                        : destinationType;

        mappingExpression
            .BeforeMap((x, y) => Mapper.Map(x, y, sourceParentType, destinationParentType))
            .ForAllMembers(x => x.Condition(r => NotAlreadyMapped(sourceParentType, destinationParentType, r)));
    }

    private static bool NotAlreadyMapped(Type sourceType, Type desitnationType, ResolutionContext r)
    {
        return !r.IsSourceValueNull &&
               Mapper.FindTypeMapFor(sourceType, desitnationType).GetPropertyMaps().Where(
                   m => m.DestinationProperty.Name.Equals(r.MemberName)).Select(y => !y.IsMapped()).All(b => b);
    }
}

Using this new code the above mapping becomes

Mapper.CreateMap<SourceClass, DestBaseClass>()
    .ForMember(x => x.BasePropTwo, m => m.MapFrom(x => x.BaseProp2));

Mapper.CreateMap<SourceClass, DestChildClass>()
    .ForMember(x => x.ChildPropTwo, m => m.MapFrom(x => x.ChildProp2))
    .InheritMappingFromBaseType(WithBaseFor.Destination);

There is one caveat to using my InheritMappingFromBaseType extension method that was discovered since my original post … it is not compatible with the Mapper.AssertConfigurationIsValid() call. It will cause this function to fail even though your mapping will work fine. I haven’t had a chance to figure out if there is a way around this but if anyone has an idea I would love to hear it.

I published the updated code and a sample project showing its use to the InheritedAutoMapper GitHub page. Feel free to grab the code and fork it to your liking.

This release contains the following changes:

• Added a “Run JS Tests in Browser” menu option inside of Visual Studio. This will open your default browser and run the selected QUnit test file.
• Automatically save the test file in Visual Studio when you choose “Run JS Tests”
• Added keyboard shortcut support for Visual Studio
  • Bind a shortcut to the ProjectAndSolutionsContextMenus.Project.RunJSTests command to run JS tests
• Return line and column position for failed tests when you run a test JS file directly.
• Upgraded to PhantomJS 1.2

Here is the updated code:

if (test-path function:\prompt) {
   $oldPrompt = ls function: | ? {$_.Name -eq "prompt"}
   remove-item -force function:\prompt
 }
 function prompt {
  function getGitStatus {
  $branch = git branch 2>&1
  if($branch.Exception -eq $null) {
    $status = "git"
    $branch | foreach {
      if ($_ -match "^\*(.*)"){
        $status += $matches[1]
      }
    }

    $untracked = 0
    $updates = 0
    $deletes = 0
    $addsIndex = 0
    $deletesIndex =0
    $updatesIndex = 0

    git status --porcelain | foreach {
      if($_ -match "^([\w?]|\s)([\w?])?\s*") {
        switch ($matches[1]) {
          "A" {$addsIndex++ }
          "M" {$updatesIndex++ }
          "D" {$deletesIndex++ }
          "?" {$untracked++ }
        }
        switch ($matches[2]) {
          "A" {$adds++ }
          "M" {$updates++ }
          "D" {$deletes++ }
         }
      }
    }
    $status += " a:" +$addsIndex
    if($adds -gt 0) {
      $status += "($adds)"
    }

    $status += " m:" +$updatesIndex
    if($updates -gt 0) {
      $status += "($updates)"
    }

    $status += " d:" +$deletesIndex
    if($deletes -gt 0) {
      $status += "($deletes)"
    }     

    $status += " ?:$untracked"
    return $status
  }
  else {
    return $false
  }
}

  function getHgStatus {
    $summary = hg summary 2>&1
    if($summary.Exception -eq $null) {
      $regex = "(?si)(parent:(?<parent>.*?)(\n|\r)+.*?)(branch:(?<branch>.*)\s)(commit:(?<commit>.*)\s)(update:(?<update>.*))";
      $summary = [System.String]::Join([System.Environment]::NewLine,$summary)
      $res = $summary -match $regex
      $status = "hg {0} c:{1}" -f $matches["branch"].Trim(), $matches["commit"].Trim()
      return $status
   }
   else {
    return $false
   }
  }

  $status = getGitStatus
  if(-not $status) {
      $status = getHgStatus
  }
  $host.ui.rawui.WindowTitle = (get-location).Path
  if($status) {
    write-host ($status) -NoNewLine -ForegroundColor Green
    write-host (">") -NoNewLine -ForegroundColor Green
  }
  else {
    & $oldPrompt
  }
  return " "
}

After adding this prompt to your profile when you are in a git repository you will see this:

This is more complex than the Mercurial prompt since git has the concept of a staging area. The number not in parentheses is the “staged” value and the number in parentheses is the unstaged value. So in the prompt above the repository has 1 modification staged and one unstaged.

When you are in a Mercurial repository you will see this:

I worked around this limitation by adding the following code to my IFrame (my implementation uses jQuery) which will override the anchor link functionality and scroll the window programmatically. This code makes use of the window.parent property which means it is subject to the Same Origin Policy.

$(function(){
  $("a").each(function (){
    var link = $(this);
    var href = link.attr("href");
    if(href && href[0] == "#")
    {
      var name = href.substring(1);
      $(this).click(function() {
        var nameElement = $("[name='"+name+"']");
        var idElement = $("#"+name);
        var element = null;
        if(nameElement.length > 0) {
          element = nameElement;
        } else if(idElement.length > 0) {
          element = idElement;
        }

        if(element) {
          var offset = element.offset();
          window.parent.scrollTo(offset.left, offset.top);
        }

        return false;
      });
    }
  });
});

Backstory

About nine months ago I asked a question on StackOverflow about whether there were any tools/extensions which integrated into Visual Studio to run JavaScript unit tests. At that time there were no good solutions provided which led me to investigate creating my own tool. I explored many options but eventually I found the PhantomJS headless browser to help drive the tests.  After a couple weeks of development Chutzpah was born.

What does Chutzpah do?

Chutzpah is both a Visual Studio extension and a command line utility.

As a Visual Studio extension:

It allows you to run your JavaScript tests without leaving the IDE. It adds a context menu option to run tests directly from a source file.

It logs test results to both the Error list and the Output window.

As a command line utility:

It allows you to easily integrate test results into your build

It also has support for the TeamCity continuous integration server so that you get detailed test output on every build.

How to use it?

Chutzpah is really easy to use, given QUnit tests (it only supports QUnit for now) you can run Chutzpah on the test harness HTML file and it will output the results. Chutzpah also supports running the tests directly from the JavaScript file as long as you add reference comments to the top of your test file.

For example given two files test.js (QUnit tests file) and code.js (implementation file).

code.js

var mathLib = {
    add5: function (a) {
        return a + 5;
    }
}

test.js

/// <reference path="code.js" />

test("will add 5 to number", function () {
    var res = mathLib.add5(10)

    equals(res, 15, "should add 5");
});

You can run the tests by right clicking and choosing “Run JS Test” if you are using the Visual Studio plugin, otherwise you can execute Chutzpah from the command line:

.\chutzpah.console.exe test.js

Community Support

I am really excited about releasing Chutzpah as an open source project with the hope of garnering support from the community. I would love to get feedback, bug reports, feature requests and code contributions. If you are interested in working on Chutzpah fork the code and get hacking.

Future Plans Ideas

At this stage I have many ideas of what features should come next for Chutzpah but outside of bug fixes I have no solid plans yet. Here are several ideas floating around in my head…

1. Support other JavaScript unit test frameworks besides QUnit
2. Expand past only using PhantomJS as the headless browser, possibly working with things like JsTestDriver or EnvJS.
3. Be able to run individual tests instead of just a whole file.
4. Add better IDE support like the Resharper 6 QUnit functionality.
5. Add scanning for test files within a whole project hierarchy
6. Support proxy servers
7. Capture more detailed information from each test
8. Integrate with existing test runners like MSTest or TestDriven.NET
9. Add NuGet support