Using F# Active Patterns to encapsulate complex conditions

In this post I'm going to show a little of example of using F# Active Patterns to encapsulate complex conditions.


While working on AbcExplorationLib I needed way to generate "friendly" labels for branch instruction destinations. According to the ActionScript Virtual Machine 2 Overview document, the branch instructions (jump,ifgt,ifeq,etc.) have a S24(signed 24 bit value) offset that specifies the destination. What I wanted to do was to modify the original instruction list to add a special(non existent ) instruction called ArtificalCodeBranchLabel which has a name which is referenced in the in the branch instruction.

Every branch instruction in the library representation has an object of type:

type JumpLabelReference =
   | UnSolvedReference of int
   | SolvedReference of string

Every instruction in the library is described in a big discriminated union like this:

type AbcFileInstruction =
    | ArtificalCodeBranchLabel of string
    | Add        
    | AsType of int
    | BitAnd
    | BitNot
    | BitOr
    | BitXor
    ...
    | IfEq of JumpLabelReference
    | IfFalse of JumpLabelReference
    | IfGe of JumpLabelReference
    | IfGt of JumpLabelReference     
    | IfLe of JumpLabelReference     
    ...

Notice that essentially, every branch instruction(except for lookupswitch) have a single JumpLabelReference instance as its argument, and in order to write the process of solving the branch destination we can have to write code for each instruction.

So in order to assist the process of solving the reference the following active pattern was created:

let (|UnsolvedSingleBranchInstruction|_|)(pair:int64*AbcFileInstruction) =
   let (instructionOffset,instruction) = pair in
   let absoluteOffset(relativeOffset:int) = int64(3 + 1 + relativeOffset) + instructionOffset in
   let result(offset,createFunction) =  Some(absoluteOffset <| offset,createFunction) 
   in
      match instruction with
         | IfEq(UnSolvedReference offset) -> result(offset,fun o -> IfEq(o))
         | IfFalse(UnSolvedReference offset) -> result(offset,fun o -> IfFalse(o))
         | IfGe(UnSolvedReference offset) -> result(offset,fun o -> IfGe(o))
         | IfGt(UnSolvedReference offset) -> result(offset,fun o -> IfGt(o))
         | IfLe(UnSolvedReference offset) -> result(offset,fun o -> IfLe(o))
         | IfLt(UnSolvedReference offset) -> result(offset,fun o -> IfLt(o))
         | IfNGe(UnSolvedReference offset) -> result(offset,fun o -> IfNGe(o))
         | IfNGt(UnSolvedReference offset) -> result(offset,fun o -> IfNGt(o))
         | IfNLe(UnSolvedReference offset) -> result(offset,fun o -> IfNLe(o))
         | IfNLt(UnSolvedReference offset) -> result(offset,fun o -> IfNLt(o))
         | IfNE(UnSolvedReference offset) -> result(offset,fun o -> IfNE(o))
         | IfStrictEq(UnSolvedReference offset) -> result(offset,fun o -> IfStrictEq(o))
         | IfStrictNEq(UnSolvedReference offset) -> result(offset,fun o -> IfStrictNEq(o))
         | IfTrue(UnSolvedReference offset) -> result(offset,fun o -> IfTrue(o))
         | Jump(UnSolvedReference offset) -> result(offset,fun o -> Jump(o))
         | _ -> None

This active pattern is used for a couple of things. First, it matches every branch instruction and provides a function to rebuild the instruction with a new destination. Also it calculates the absolute offset of the branch instruction.

Now we can use it in the process of solving the references:

member this.UpdateCodeWithDestinations(destinations:Map<int64,string>,
                                    instructions,
                                    resultingInstructions) =
   let processedInstructions = 
         match instructions with
         | (((offset,_) & UnsolvedSingleBranchInstruction( jumpOffset,f))::rest) 
                                when (destinations.ContainsKey(jumpOffset)) ->
              (offset,f(SolvedReference(destinations.[jumpOffset])))::rest
         | _ -> instructions
   in                                                                                      
      match processedInstructions with         
      | ((offset,instruction)::rest) when (destinations.ContainsKey(int64(offset))) ->
          this.UpdateCodeWithDestinations(destinations,
                                          rest,
                                          instruction::ArtificalCodeBranchLabel(destinations.[int64(offset)])::resultingInstructions)
      | ((_,instruction)::rest)  ->
          this.UpdateCodeWithDestinations(destinations,
                                          rest,
                                          instruction::resultingInstructions)
      | [] -> List.rev(resultingInstructions)

Although this problem could be expressed using other strategies (for example a separate class for each instruction and branch instructions inheriting from the same base class) the use of Active Patterns was very useful to write a simpler implementation of the UpdateCodeWithDestinations method.

Mutiple representations of an object with Tom mappings

This post shows an example of how Tom object mappings could be used to provide multiple pattern matching representations of objects of the same class.

Introduction

As shown in previous posts, I really like F# Active Patterns and Scala Extractors. Among other things these features allows to create multiple pattern matching representations of objects . One of the ideas behind these concepts is "Views" presented by Philip Wadler in the Views: A way for pattern matching to cohabit with data abstraction paper.

It is possible to use Tom object mappings(explained here) to get a similar effect.

Example

For this example, an alternative representation for a Complex number will be created. A complex number could be represented by Cartesian coordinates (real and imaginary parts) and by Polar coordinates (angle and modulus).

This example is used to present Views, Extractors and Active Patterns.

The Apache Commons Complex class will be used as the complex number implementation.

First, a mapping for the Complex sort needs to be created.

%include { double.tom }

%typeterm Complex {
   implement { org.apache.commons.math.complex.Complex }
   is_sort(t) { t instanceof org.apache.commons.math.complex.Complex }
   equals(t1,t2) { t1.equals(t2) }
}

Then, a mapping for the Complex number with Cartesian coordinates is created. Since the Complex class is in Cartesian coordinates only the getReal and getImaginary accessors are required.

%op Complex Complex(real:double,img :double ) {
   is_fsym(t) { t instanceof org.apache.commons.math.complex.Complex }
   get_slot(real, t) { t.getReal() }    
   get_slot(img, t) { t.getImaginary() }
   make(real,img) { new org.apache.commons.math.complex.Complex(real,img) }  
} 

Finally a mapping for the Polar representation. Since the Complex class stores the number in Cartesian coordinates a conversion must be applied to get the angle and modulus slots. Also the polar2Complex method is used to create a Complex instance using the Polar symbol.

%op Complex Polar(m:double,a :double ) {
   is_fsym(t) { t instanceof org.apache.commons.math.complex.Complex }
   
   get_slot(a, t) {  Math.atan2(t.getImaginary(), t.getReal()) }
       
   get_slot(m, t) { 
         Math.sqrt(t.getReal() * t.getReal() +
                   t.getImaginary() * t.getImaginary()) }
                   
   make(radial,modulus) { 
      org.apache.commons.math.complex.ComplexUtils.polar2Complex(
          radial,
          modulus) }  
}

A use of these mappings is the following:

Complex c = new Complex(3,3);

%match(c) {
    Polar(m,a) -> {
        System.out.println(
           String.format("%f,%f",`m,`a ));
    }
}

Also given that a make declaration was added to the mappings we can use the object creation syntax as follows:

Complex c2 = `Polar(3,Math.PI/2.0);
            
%match ( c2){
   Complex(r,i) -> {
      System.out.println(
               String.format("%f,%f",`r,`i)); 
   }
}

Pattern matching on Java objects with Tom

This post presents a quick overview of the mechanism that Tom provides to enable pattern matching on plain Java objects.

Mappings

Tom performs pattern matching on special data structures defined using Gom. However there's a mechanism that allows the mapping parts of an object to data structure that could be used to perform pattern matching.

In section 8.1 Hand-written mappings, a nice explanation of this mechanism . Also there's a very interesting video available from Tom's site where Tom is used to manipulate Java Persistence API objects.

Mappings for java.io.File

For this example we will create mappings for the java.io.File class . The first step is to create the sort definition for the File class.

%typeterm FileSystemElement {
   implement { java.io.File }
   is_sort(t) { t instanceof java.io.File }
   equals(t1,t2) { t1.equals(t2) }
}

Inside of Tom constructs the sort that represents files will be called FileSystemElement. Basic operations must be provided in order to specify: the class that is being mapped (implement), a predicate to determine if is a valid element (is_sort) and an equals criteria (equals).

Now we need to create a operator or constructor that represents files. Here's the definition for that element.

%op FileSystemElement File(name:String, parent:FileSystemElement) { 
   is_fsym(t) { (t instanceof java.io.File) &&  
                ((java.io.File)t).isFile()  }
   get_slot(name, t) { t.getName() }    
   get_slot(parent, t) { t.getParentFile() }
   make(name,parent) { new java.io.File(parent,name) } 
}

This %op definition says that we're defining a File which belongs to the FileSystemElement sort. In particular we're going to use this definition to represent java.io.File instances that refer to a file, the is_fsym definition verifies this. Now we define two slots one for the name of the file and another to the java.io.File definition of the parent. Finally a make allows us to use the backquote(`) syntax to create instances of File.

A use of this definition is the following:

File f = new File("/tmp/test.txt");

%match(f) {
  File(name,parent) -> {
     System.out.println("File name "+`name);
     System.out.println("Parent "+`parent+" "+`parent.getClass());
  }
}

By running this program we get:

File name test.txt
Parent /tmp class java.io.File

Notice that by calling getClass on parent we get java.io.File.

Mapping for directories

Using handwritten mappings allows you to expose only the parts of an object that are interesting for a certain problem. This powerful notion is present in other languages like Scala with the use of Extractors or F# with Active Patterns and originally from Views in Haskell.

For example now we're going to create a definition that represents directories which is another mapping from java.io.File.

%op FileSystemElement Directory(name:String,
                                parent:FileSystemElement, 
                                children:Children ) 
{ 
  is_fsym(t) { (t instanceof java.io.File) &&  
                ((java.io.File)t).isDirectory() }
  get_slot(name, t) { t.getName() }    
  get_slot(parent, t) { t.getParentFile() }
  get_slot(children, t) { createFromArray(t.listFiles()) }      
  make(name,parent, children) { new java.io.File(parent,name) } 
}

Notice that the is_fsym definition checks identifies a java.io.File instance that refers to a directory. Also notices that for this definition we're exposing the child files and directories.

In order to expose a sequence of elements we need to create a separate mapping. For example the above example mentions the Children sort which is defined as:

%typeterm Children {
   implement { java.util.ArrayList<java.io.File> }
   is_sort(t) { t instanceof java.util.ArrayList }
   equals(t1,t2) { t1.equals(t2) }
}

%oparray Children Children(FileSystemElement*) {
   is_fsym(t) { t instanceof ArrayList }
   get_element(l,n) { l.get(n) }
   get_size(l)      { l.size() }
   make_empty(n)    { new ArrayList<java.io.File>(n) }
   make_append(e,l) { addToFileArrayList(e,l) }
}

Notice that the %oparray definition contains special mapping for array-like collections. In section 8.1.4 Using list-matching there's more information about this element and about the %oplist element which allows the mapping of list-like collections.

The addToFileArrayList is a static method that creates an ArrayList from the result of calling java.io.File.listFiles().

Example: listing a directory

With the definitions available above we can write a small program that lists a directory:

File homeDirectory = new File("/home/ldfallas");

%match(homeDirectory) {
   Directory(_,_,Children(_*,f,_*)) -> {
     %match(f) {
        File(name,_) -> { System.out.println("File: "+`name); }
        Directory(name,_,_) -> { System.out.println("Directory: "+`name); }
       }
   }
}

As explained in a previous post, since Children(_*,f,_*) has no restriction on f then the body of the case will be executed for all possible child file of the specified directory.


Example: Files with same name

The following example tries to find two files stored in two separate directories in the same level.

...
%match(homeDirectory) {
   Directory(_,_,Children(_*,Directory(dir1,_,Children(_*,File(name,_),_*)),
                        _*,Directory(dir2,_,Children(_*,File(name,_),_*)),
                        _*)) -> {

     System.out.println("File name "+`name);
     System.out.println(`dir1);
     System.out.println(`dir2);
  }
}

Notice that this little example will show all the pairs of files with the same name stored in two different directories at the same level.

Pattern matching with Tom

In this post I'm going to show a small overview to the Tom pattern matching compiler for Java.

Tom

Tom is an extension to the Java language which adds a constructs for describing data structures and powerful pattern matching features for manipulating those data structures.

Tom distribution includes a command line compiler and a Eclipse plugin. Also nice documentation is found and examples are found in its website.

The documentation available from the website includes a nice step by step introduction to the features available in the product. Here I'm going to show a little overview of some of them.

All the snippets for this post were created using the Eclipse plugin.

Data structure definition

Tom provides a way for data structures that could be easily instantiated and manipulated with pattern matching. These data types are also called algebraic data types which are very similar to those available in languages such as Haskell.

These data types could be defined inside a Java class by using the %gom { } block or defining the types in a file with .gom extension. Instructions on how to do this are available in the Separating Gom from Tom section of the documentation.

For the rest of this post we're going to use the following definitions to show examples with Tom.

module Company
   imports int   String
   abstract syntax
   
   Person = Person(companyId:int,name:String,age:int)
      
   Persons = Persons(Person*)   
   
   Worker =  Employee(personId:int)
           | Contractor(name:String)
   
   Workers = Workers(Worker*)
   
   Group =  DepartmentGroup(department:Department)
          | Committee(name:String, members:Workers)
          
   Department = SimpleDepartment(name:String, leader:Worker, members:Workers)
              | MultiDepartment(name:String, leader:Worker, subDepartments:Departments)
              
   Departments = Departments(Department*)
              
   Groups = Groups(Group*)
   
   Company = Company(name:String,members:Persons,groups:Groups)

Reading for the bottom to the top, these definitions describe a Company data structure which has name, a collection of persons and a collection of groups inside the company. Groups could be Departments or a Committees. Departments could be simple (SimpleDepartment) or have sub departments(MultipleDepartment). Also the members of the Committees or Departments could be employees or contractors.

In order to use these definitions we need to create a file with .t extension. This file will have both Java and Tom elements mixed together. For example here's the creation of an instance of the data structures defined above in Main.t :

   
import langexplr.tomtests.company.types.*;

public class Main{
    %include{ int.tom }
    %include{ company/Company.tom }

    static Company createCompanyData() {
      return `Company("MyCompany",
                Persons(Person(1,"John",43),
                        Person(2,"Kim",33),
                        Person(3,"Maria",27),
                        Person(4,"Luis",34),
                        Person(5,"Mary",34),
                        Person(6,"Bill",24)),
                 Groups(
                     DepartmentGroup(
                         SimpleDepartment(
                               "HR",
                               Employee(2),
                               Workers(Employee(1),
                                       Employee(6),
                                       Contractor("Lisa")))),
                     DepartmentGroup(
                         SimpleDepartment(
                               "Finance",
                               Employee(5),
                               Workers(Contractor("William")))),
                     DepartmentGroup(
                         MultiDepartment(
                               "Systems",
                               Employee(5),
                               Departments(
                                  SimpleDepartment(
                                     "Development",
                                     Employee(3),
                                     Workers(Contractor("Charlie"))),
                                  SimpleDepartment(
                                     "QA",
                                     Employee(4),
                                     Workers(Contractor("Lily")))))),
                     Committee("Party",Workers(Employee(2),Employee(5)))
                   ));
}
...

Notice the backquote character used at the beginning of the call to the Company constructor. This element is used to differentiate the Java and Tom syntax elements.

Matching

Tom provides a powerful pattern matching mechanism that eases the manipulation of complex tree structures. In order to use this feature, a %match statement is provided. This statement is barely similar to a switch statement in Java or C# but using patterns instead of literals. A simple example of this feature is the following:

static void nameTest(Company c) {
   String name = "";
   %match (c){
       Company(theName,_,_) -> { name = `theName; }
   }       
   System.out.println(name);  
}

In this example the name of the company is extracted and assigned to the name variable. The %match statement receives an element, in this case the instance of the Company datatype. This element is tested against one or more patterns, in this case only one pattern is provided. If the pattern matches, then the code on the left of the arrow ( -> ) is executed.

The pattern Company(theName,_,_) says, that we're expecting an instance of the Company datatype and that the name( the first argument of the constructor) will be assigned to the theName variable. It also says that we will ignore the other two elements of the Company datatype. The variable theName could be used at the left side of this entry by using a backquote character at the beginning of the name.

List matching

One of the most interesting pattern matching elements provided by Tom is list matching which allows the creation of patterns on sequences of elements.

For example, say that we want to create a function that retrieves the name of an Person given its id and an instance of the Company. As a first version of this function, we can write:

static String getPersonNameByIdV1(int id,Company c) {
   String name = null;       
   %match (c){
       Company(_,Persons(_*,Person(empId,empName,_),_*),_) -> {
          if (id == `empId) {               
             name = `empName;
          }               
       }
   }
   return name;  
}

It is important to remember that in the definitions of the data structures, the Persons element is defined as Persons = Persons(Person*) which means that its constructor receives a any number of Person instances.

Now the Company(_,Persons(_*,Person(empId,empName,_),_*),_) pattern says: match a person inside a company and assign empId and empName to its id and name .

Given that "_*" is a wildcard, notice that there are many ways to match this pattern. As explained in the List matching section of the documentation, since there's several ways to match this pattern, the block will be executed with every possible match. This means that empId and empName will be bound to the id and the name of every person. Given this we can ask if (id == `empId) { ... } and assign the name that we found.

Non-linear patterns

Another powerful pattern matching element that Tom provides is the ability to use one variable several times in the same pattern.The first use will bind the variable to a value, the other uses will compare the current element with the bound value. This feature, called Non-linear patterns, introduced here. It allows the creation of more expressive patterns, for example we can rewrite the previous method the following way:

static String getPersonNameByIdV2(int id,Company c) {
   String name = null;       
   %match (int id,c){
       empId,Company(_,Persons(_*,Person(empId,empName,_),_*),_) -> {               
             name = `empName;               
       }
   }
   return name;  
}

Here we specify two arguments to the %match construct. The first is the requested id and the second is the Company instance. Notice that in the pattern we match the id with the empId free variable the first time, and then we use it to match the requested person. Now we're putting a restriction on the Person we're looking for, so we can remove the if statement from the body.


A final example

For the final example I'll write a function that prints the names of all the members of a given department . Here's the code:

static void printNameOfPeopleWorkingInDepartment(String departmentName,Company c) {
  System.out.println("People working in "+departmentName);
  %match(String departmentName,c) {
    deptName,
    Company(_,
            persons,
            Groups(_*,
                   DepartmentGroup(
                     SimpleDepartment(
                         deptName,
                         _,
                         Workers(_*,worker,_*))),
                   _*)) -> {            
        %match(worker) {
           Employee(id) -> { System.out.println(getEmployeeNameById(`id,c));}
           Contractor(name) -> { System.out.println(`name);}
        }             
    }
  }
}

This pattern will first look for a SimpleDepartment with the specified name. Then for each worker it will extract the name given if it is an Employee or a Contractor.

MultiDepartment instances are not considered. In future posts another Tom feature will be used to deal with these elements.

Code for this post can be found here.

Tom provides lots of features not covered here. Its distribution includes documentation and a lot of examples.

Creating Netbeans Ruby Hints with Scala, Part 1

In this post I'm going to show a little experiment of creating a Netbeans Ruby Hint using the Scala language. This is the first of a two-part series of posts on this topic.

Netbeans Ruby Hints and Quick Fixes is a very nice feature that will be part of Netbeans 6.0 Ruby integration. This feature can be used to identify potential problems or to promote best practices in Ruby programs. I first learned about it by reading Tor Norbye's blog.

I really like the idea of mixing languages to accomplish something. This is the main reason I chose Scala to do this experiment. Also I wanted to try to apply some ideas from previous posts. For a future experiment it will be very nice to write this code using JRuby.

For this post I'm using Netbeans 6.0 Beta 2. As described below the APIs for writing hints are still not officially public because they're still under development. Again, as with previous posts, this is only an experiment to see how different programming languages could be used solve special tasks.

Motivation

Several weeks ago I wrote a post on Ruby's yield statement, there I showed a function that calculates the Fibonacci sequence using a while statement in a pretty traditional way. Then someone posted a comment with a much compact version of it by using some nice Ruby features. That got me thinking how Netbeans Ruby Hints could also be used to help Ruby beginners(like me) to find out about alternative ways to do something.

The Hint

One of the things I like about Ruby is statement modifiers. That's one of the first things you notice while reading the Why's (Poignant) Guide to Ruby.

I think statement modifiers makes the code look nice if used carefully.

So the hint that will be implement it's going to identify opportunities to apply the if or unless statement modifiers. For example:

table = Hash.new
...
if table.empty? then
   puts "No items" 
end
...

Could also be written as:

table = Hash.new
...
puts "No items" if table.empty?
...

Creating the Netbeans module

The biggest challenge I had was to create a Netbeans module using only Scala. The main issue is not having all the nice GUI facilities available to create to module.

Luckily there's a series of articles in Geertjan's Weblog called NetBeans Modules for Dummies Part 1,2,3,4. These articles provided a lot of information on how to create an NBM file using Ant tasks .

I also had to create a some Netbeans modules using Java to dissect the resulting NBM file and to provide some of the missing arguments. The resulting Ant file is can be found here.

Another challenge that I had was that some of the classes that I needed to access were only available to friend packages, this mainly because I was trying to access APIs that are still changing. Luckly, Tor Norbye from the Netbeans Ruby development list, provided a solution for this issue which could be found here. Again this is a consequence of using API's that are still not public.

The last issue that I had was to add the Scala Runtime Jar file as part of the package. The How do module dependencies/classloading work? Netbeans Faq entry was very helpful to solve this.

The code

By reading the code of existing hints, I learned that, the way to define hints (which is still under development) is very nice and very simple. Also there's useful documentation in the Writing New Ruby Hints entry from the Netbeans wiki.

Here's the code:

class IfToStatementModifierHint extends AstRule {

    def appliesTo(info : CompilationInfo) = true

    def getKinds() : Set = {
        val nodeKinds = new HashSet()
        nodeKinds.add(NodeTypes.IFNODE)
        nodeKinds
    }

    def run(info :CompilationInfo,
            node : Node,
            path : AstPath ,
            caretOffset : int,
            result : java.util.List) : unit = {

        node match {
           case IfStatement(callNode : CallNode,
                            NewlineNode(thenStat),
                            null) => {
              
              val range = AstUtilities.getRange(node)
 
              val desc = 
                   new Description(this,
                                   recomendationText,
                                   info.getFileObject,range,
                                   Collections.emptyList,
                                   600)
              result.add(desc)
       }
           case IfStatement(NotNode(EqualComparison(x,_ : NilNode)),
                            NewlineNode(thenStat),
                            null) => {
              
              
              val range = AstUtilities.getRange(node)
 
              val desc = 
                   new Description(this,
                                   recomendationText,
                                   info.getFileObject,range,
                                   Collections.emptyList,
                                   600)
              result.add(desc)
           }
           case _ =>
               {
               }
        } 
    }

    def getId() = "TestHint1"
 
    def getDisplayName() = "If statement as statement modifier"
 
    def getDescription() = "Identifies certain ..."

    def getDefaultEnabled() = true
  
    def getDefaultSeverity() = HintSeverity.WARNING 

    def getCustomizer(node: Preferences) : JComponent = null

    def showInTasklist() = true     

    def recomendationText = "Consider changing..."
   
}

The most interesting methods of this class are getHints and run.

The getHints method defines the kinds of AST nodes this method applies to. The run method identifies which kinds of if statement apply to this hint. To do this a couple of extractor objects defined in previous posts are used. Two special cases are identified:

• One if statement with a method call as condition, one statement in the then section and no statements in the else section.


• One if statement with an equal comparison to nil as condition, one statement in the then section and no statements in the else section.

This Hint is shown as a WARNING because it's the how severity that seems to apply. Although it will be very nice to have a RECOMMENDATION severity which seems to be more appropriate for this hint.

I really like this way of defining hints because you have to write exactly the code related to your problem.

Here's and example in action:




Code for this experiment can be found here.

For the next post I'll try to implement a quick fix for this hint.

Exploring JRuby Syntax Trees With Scala, Part 2

In this post I'm going to show a couple of examples of using Scala to extract elements of Ruby programs.

Because of its functional influence Scala provides nice features to manipulate tree structures. As I mentioned in previous posts, I think one of the most interesting features provided by Scala is pattern matching. Among other pattern matching constructs, Scala provides one that I particularly like : Extractors.

The Matching Object With Patterns paper by Burak Emir , Martin Odersky , and John Williams, describes several techniques for exploring complex object data structures. One of this techniques is the Visitor design pattern which is one of the most used techniques that is used to navigate a syntax tree structure. I think the pattern matching approach can be combined with the visitors to solve different tasks.

In this post I'm interested in showing pattern matching using Scala extractors on the JRuby AST. The JRuby AST seems to provide nice visitor mechanism which will be explored in future posts.

Scala extractor objects allow existing Scala or Java Platform classes to participate in pattern matching just as case classes. Extractor objects can be used to expose only interesting elements for a certain problem and also makes the definition of the class independent of the way it is used in a match construct. A nice description of this feature for Scala is provided in the Matching Object With Patterns paper. A similar feature is implemented in F# as active patterns.This concept was originated by work on Views by Philip Walder .

I'm going to show a couple of examples of using this feature with the JRuby AST.

Example 1:

Say that you want to identify the key value that is given to Hash assignment: (here highlighted in red)

x["a"] = 1

We need to define extractors for related objects. In order to do this I'm going to use the tool from the previous post to see which classes we need to represent.



By reading this code we noticed that we need at least extractors for

• BlockNode


• NewlineNode


• AttrAssignNode


• LocalVarNode


• ArrayNode


• StrNode


• FixnumNode

Basic extractors for the child nodes of these elements could be defined as follows:

object NewlineNode {
  def unapply(astNode : Node) =
    if (astNode.isInstanceOf[NewlineNode]) {      
      Some(astNode.asInstanceOf[NewlineNode].getNextNode)
    } else {
      None
    }
}

object LocalVarNode {
  def unapply(astNode : Node) = {
    if (astNode.isInstanceOf[LocalVarNode])  {
      Some (astNode.asInstanceOf[LocalVarNode].getName)
    } else {
      None
    }
  }
} 

object StrNode {
  def unapply(astNode : Node) = {
    if (astNode.isInstanceOf[StrNode]) {
      Some (astNode.asInstanceOf[StrNode].getValue)
    } else {
      None
    }
  }
}

object BlockNode {
  def unapply(astNode : Node) = {
     if (astNode.isInstanceOf[BlockNode]) {              
       Some (List.fromIterator(
               new JavaIteratorWrapper[Node](
                     astNode.asInstanceOf[BlockNode].childNodes.iterator())))
     } else {
       None
     }
  }
}

object FixnumNode {
  def unapply(astNode : Node) = {
    if (astNode.isInstanceOf[FixnumNode]) {
      Some (astNode.asInstanceOf[FixnumNode].getValue)
    } else {
      None
    }
  }
}


object AttrAssignNode {
  def unapply(astNode : Node) = {
    if (astNode.isInstanceOf[AttrAssignNode]) {
      val attAsgn = astNode.asInstanceOf[AttrAssignNode]
      Some (attAsgn.getReceiverNode,attAsgn.getArgsNode)
    } else {
      None
    }
  }
}

object ArrayNode {
  def unapply(astNode : Node) =
    if (astNode.isInstanceOf[ArrayNode]) {
      val theArrayNode = astNode.asInstanceOf[ArrayNode]
      Some(List.fromIterator(new JavaIteratorWrapper[Node](theArrayNode.childNodes.iterator)))
    } else {
      None
    }
}

By defining these extractors we can combine them with existing Scala pattern matching constructs to create the required pattern:

val rubyCode2 = "x = Hash.new\n"+"x[\"a\"] = 1"    
val rootNode2 = r.parse(rubyCode2,"dummy.rb",r.getCurrentContext.getCurrentScope,0).asInstanceOf[RootNode]

rootNode2.getBodyNode match {
  case BlockNode(
           List(_,
                NewlineNode(
                     AttrAssignNode(
                         LocalVarNode("x"),
                         ArrayNode(
                             List(key,
                                  FixnumNode(1))))))) =>
     System.out.println("Matches for: "+ key.toString())
  case _ => System.out.println("No Match!")
}

Example 2:

For the next example say that we want to extract the identifier which is compared to some number in the condition of an if statement. For example:

if the_variable == 1 then
  ...
else
  ...
end

The tree representation of a code similar to this looks like:



The following extractors will be used to identify this pattern:

object IfStatement {
  def unapply(astNode : Node) =
    if (astNode.isInstanceOf[IfNode]) {
      val theIfNode = astNode.asInstanceOf[IfNode]
      Some (theIfNode.getCondition,theIfNode.getThenBody,theIfNode.getElseBody)
    } else {
      None
    }
}


object EqualComparison {
   def unapply(astNode : Node) =
     if (astNode.isInstanceOf[CallNode]) {
       val theCallNode = astNode.asInstanceOf[CallNode]
       if (theCallNode.getName.equals("==") &&
           theCallNode.getArgsNode.isInstanceOf[ArrayNode] &&
           theCallNode.getArgsNode.asInstanceOf[ArrayNode].size == 1) {
           Some (theCallNode.getReceiverNode,
                 theCallNode.getArgsNode.asInstanceOf[ArrayNode].get(0))
       } else {
           None
       }
     } else {
       None
     }
}

Note that in this case I'm using a shortcut, instead of defining an extractor for CallNode and using it with ArrayNode a single extractor is used to identify the binary equal comparison.

By using this extractors we can define the pattern as follows:

val rubyCode3 = "if the_variable == 30 then\n puts 2\nelse\n puts 3\nend"    
val rootNode3 = r.parse(rubyCode3,"dummy.rb",r.getCurrentContext.getCurrentScope,0).asInstanceOf[RootNode]
val nodeToMatch = rootNode3.getBodyNode.asInstanceOf[NewlineNode].getNextNode
nodeToMatch match {
    case IfStatement(EqualComparison(leftSide,_ : FixnumNode),
                     _,
                     _) =>
       System.out.println("Matches for: "+ leftSide.toString())
    case _ => System.out.println("No Match!")
}

For future post I'm going to be using these extractors to create more examples in other contexts.

Creating Java refactorings with Scala and Eclipse LTK - Part 2

This is the second of a two-part series of posts on creating a simple Java refactoring using the Scala programming language and the Eclipse Language Toolkit.

As mentioned in the first part, the refactoring is implemented by inheriting from the Refactoring class. This is an abstract class, in order to implement it we need to override the following methods:

• abstract RefactoringStatus checkFinalConditions(IProgressMonitor pm)


• abstract RefactoringStatus checkInitialConditions(IProgressMonitor pm)


• abstract Change createChange(IProgressMonitor pm)


• abstract String getName()

According to Unleashing the Power of Refactoring the checkInitialConditions method is used to verify that the refactoring can be performed. The checkFinalConditions is used to "perform long running checks before change generation...", but also can contain most of the work involved in the change generation. The createChange method is used to create the Change object that represents the actual change that will be performed in the code.

class InvertIfStatementRefactoring extends Refactoring {
   var propagateNegation : boolean = false
   var compilationUnit : ICompilationUnit = null
   var selection : ITextSelection = null
   var textChange : TextFileChange  = null
   
   override def  checkInitialConditions( pm : IProgressMonitor) : RefactoringStatus = {
      val status = new RefactoringStatus
      if (compilationUnit == null || selection == null) {
        status.merge(
            RefactoringStatus.createFatalErrorStatus(
                "Expression not identified yet!"));
      }
      return status
   }
   override def checkFinalConditions(pm : IProgressMonitor) : RefactoringStatus = {
       val status  = new RefactoringStatus
       val requestor = 
            new ASTRequestor() {
               override def acceptAST(source : ICompilationUnit, 
                                      ast : CompilationUnit) = 
                            performRewrite(source,ast,status)
            }
       
        val parser = ASTParser.newParser(AST.JLS3);
        parser.setResolveBindings(false);
        
        try {
                parser.createASTs(
                                Array[ICompilationUnit](this.compilationUnit),
                                new Array[String](0),                        
                                requestor, 
                                pm)
        } catch { 
          case ex : RuntimeException => {
                  status.merge(
                      RefactoringStatus.createFatalErrorStatus(
                          ex.getMessage()));
           }
        }
        return status
       
   }

   override def createChange(pm : IProgressMonitor) : Change =
     return textChange
   
   
   override def getName() = "Invert if statement"

  ...
}

For this experiment most of the work is done from checkFinalConditionsMethod, in this method the code is parsed and the resulting AST is manipulated to generate a TextChange object that will be returned by the createChange method. The performRewrite and rewriteIfStatement methods do this by identifying the elements of the IF statement that will be manipulated.

   
   def performRewrite(source : ICompilationUnit,
                     ast : CompilationUnit, 
                     status : RefactoringStatus) : Unit = {
     
      val rewrite = ASTRewrite.create(ast.getAST())
      val theAst = ast.getAST()
      val n  = NodeFinder.perform(ast,
                                  selection.getOffset(),
                                  selection.getLength())
      
      n match {
        case ifStatNode@IfStatement(_,_,_) =>
             rewriteIfStatement(
                      rewrite, 
                      theAst,
                      ifStatNode.asInstanceOf[IfStatement])
        case _ => 
             throw new RuntimeException("Expecting IfStatement found: "+n.getClass().toString()+n.toString()) 
      }

      textChange = new TextFileChange(source.getElementName(), 
                                      source.getResource().asInstanceOf[IFile])
      textChange.setTextType("java")
      textChange.setEdit(rewrite.rewriteAST())
   }
   
   
   def rewriteIfStatement(rewrite : ASTRewrite,
                          theAst : AST, 
                          ifStatement : IfStatement ) : Unit = {
     
     val newIfStatement = theAst.newIfStatement
     
     val resultIfCondition =
       if (this.propagateNegation) { 
         propagateNegationInCondition(ifStatement.getExpression,rewrite,theAst) } 
       else  { 
         val pExpr = theAst.newParenthesizedExpression
         pExpr.setExpression(            
             rewrite.createCopyTarget(
                ifStatement.getExpression()).asInstanceOf[Expression]
                )

         val negatedExpression = theAst.newPrefixExpression()
         negatedExpression.setOperand(pExpr)
         negatedExpression.setOperator(PrefixExpression.Operator.NOT)
         negatedExpression 
       } 
                         
     newIfStatement.setExpression( resultIfCondition )
             
     if (ifStatement.getElseStatement != null) {
        newIfStatement.setThenStatement(
            rewrite.createMoveTarget(
               ifStatement.getElseStatement()).asInstanceOf[Statement])
     } else {
       newIfStatement.setThenStatement(
           theAst.newBlock)
     }
     
     newIfStatement.setElseStatement(
         rewrite.createMoveTarget(
             ifStatement.getThenStatement()).asInstanceOf[Statement])
     rewrite.replace(ifStatement,newIfStatement,null) 
   }
   

The changes in the AST are recorded using the ASTRewrite class. More details on how to manipulate JDT AST trees can be found in AST Syntax Tree.

The NodeFinder class is used although its use is not encouraged because of its visibility. This class identifies the selected node under the tree of the compilation unit. In future posts I'll try to replace the use of this class.

If the propagate negation check box is not checked the only thing that we need to do with the condition expression is to wrap it with parenthesis (ParenthesizedExpression) and with a NOT expression(PrefixExpression with the NOT operator).

In order to propagate negation several scenarios must be considered. For example if the original expression is (x == 1) the desired resulting expression must be (x != 1) , also if the condition is (x == 1) && (y == 4) then it can be transformed to (x != 1) || (y != 4). Inspired by the arithmetic simplification examples presented in Matching Objects With Patterns paper, this was implemented using Scala extractors . The following definitions of extractors were defined:

object NotExpression {
   def unapply(e : ASTNode) =
     if (e.isInstanceOf[PrefixExpression] &&
         e.asInstanceOf[PrefixExpression].getOperator == PrefixExpression.Operator.NOT) {       
        Some(e.asInstanceOf[PrefixExpression].getOperand)
     }
     else {       
       None
     }
}

object AndExpression {
  def unapply(e : ASTNode) =
      Utilities.identifyInfixExpression(e,InfixExpression.Operator.CONDITIONAL_AND)
}

object OrExpression {
  def unapply(e : ASTNode) =
      Utilities.identifyInfixExpression(e,InfixExpression.Operator.CONDITIONAL_OR)
}

object EqualsExpression {
  def unapply(e : ASTNode) =
      Utilities.identifyInfixExpression(e,InfixExpression.Operator.EQUALS)
}

object NotEqualsExpression {
  def unapply(e : ASTNode) =
      Utilities.identifyInfixExpression(e,InfixExpression.Operator.NOT_EQUALS)
}

object LessExpression {
  def unapply(e : ASTNode) =
      Utilities.identifyInfixExpression(e,InfixExpression.Operator.LESS)
}

object GreaterExpression {
  def unapply(e : ASTNode) =
      Utilities.identifyInfixExpression(e,InfixExpression.Operator.GREATER)
}

object LessEqualsExpression {
  def unapply(e : ASTNode) =
      Utilities.identifyInfixExpression(e,InfixExpression.Operator.LESS_EQUALS)
}

object GreaterEqualsExpression {
  def unapply(e : ASTNode) =
      Utilities.identifyInfixExpression(e,InfixExpression.Operator.GREATER_EQUALS)
}

object Parenthesis {
  def unapply(node : ASTNode) =
    if (node.isInstanceOf[ParenthesizedExpression])  {
        Some(node.asInstanceOf[ParenthesizedExpression].getExpression)
    }
    else {       
       None
    }
}

object IfStatement {
   def unapply(node : ASTNode) =
     if (node.isInstanceOf[IfStatement]) {
       val ifStatement = node.asInstanceOf[IfStatement]
        Some(ifStatement.getExpression,
             ifStatement.getThenStatement,
             ifStatement.getElseStatement)             
     } else {
       None
     }
}

Given this definition we can implement the propagateNegationInCodition method by checking every case that we want to transform:

   def propagateNegationInCondition(condition : Expression, rewrite : ASTRewrite,ast : AST) : Expression = {
     condition match {
       case EqualsExpression(x,y) =>  
              Utilities.createInfixExpression(
                  rewrite.createMoveTarget(x).asInstanceOf[Expression],
                  rewrite.createMoveTarget(y).asInstanceOf[Expression],
                  InfixExpression.Operator.NOT_EQUALS,
                  ast)           
                  
      case NotEqualsExpression(x,y) =>  
        Utilities.createInfixExpression(
            rewrite.createMoveTarget(x).asInstanceOf[Expression],
            rewrite.createMoveTarget(y).asInstanceOf[Expression],
            InfixExpression.Operator.EQUALS,
            ast)
      
      case OrExpression(x,y) => 
        Utilities.createInfixExpression(
            propagateNegationInCondition(x,rewrite,ast),
            propagateNegationInCondition(y,rewrite,ast),
            InfixExpression.Operator.CONDITIONAL_AND,
            ast)
            
      case AndExpression(x,y) => 
        Utilities.createInfixExpression(
            propagateNegationInCondition(x,rewrite,ast),
            propagateNegationInCondition(y,rewrite,ast),
            InfixExpression.Operator.CONDITIONAL_OR,
            ast)
            
      case NotExpression(negatedExpression) =>  
         rewrite.createMoveTarget(negatedExpression).asInstanceOf[Expression]

      case x if x.isInstanceOf[InfixExpression] => {
         val parenthesis = ast.newParenthesizedExpression
         parenthesis.setExpression(
             rewrite.createMoveTarget(condition).asInstanceOf[Expression])
         val notExpression = ast.newPrefixExpression
         notExpression.setOperand(parenthesis)
         notExpression.setOperator(PrefixExpression.Operator.NOT)
         notExpression
       }
       case _ => {
         val notExpression = ast.newPrefixExpression
         notExpression.setOperand(
             rewrite.createMoveTarget(condition).asInstanceOf[Expression])
         notExpression.setOperator(PrefixExpression.Operator.NOT)
         notExpression
       }
     }
   }

Given the following code

if(goo(3) && !(x < 3))  {
    System.out.print(2);
} else {
    System.out.println(4);
}

By executing the refactoring without propagating the negation:


By executing the refactoring propagating the negation:




Code for this experiment can be found here.

Creating FxCop rules with F#

In this post I'm going to show a little example of an FxCop rule created with F#. My goal is to show that F# features can be used to define code rules.

The purpose of the post is not to show how to create FxCop rules, a nice explanation can be found in this useful blog entry: FxCop This (also useful links are provided).

The rule that I'm going to show is used to detect assignments from a field to itself. For example:

public class AClass {

   int aValue;
   public void AMethod(int aValeu){
      this.aValue = aValue;
      ...
   }
   ...
}

In this example, an error typing the name of the first argument of AMethod leads to an incorrect assignment of field aValue to itself. The C# compiler gives you a warning on this, however the code is generated because it is a valid program.

In order to create an FxCop rule that detects this, we have to identify the IL code sequence that represents the assignment. By using ILDASM we can see this:

.method public hidebysig instance void  AMethod(int32 aValeu) cil managed
{
  // Code size       14 (0xe)
  .maxstack  8
  IL_0000:  nop
  IL_0001:  ldarg.0
  IL_0002:  ldarg.0
  IL_0003:  ldfld      int32 AClass::aValue
  IL_0008:  stfld      int32 AClass::aValue
  ...
} // end of method AClass::AMethod

So what we need to find is the simple pattern of a LDFLD opcode followed by a STFLD to the same field. The code for this rule looks like this:

type SameFieldAssignment = class
    inherit BaseIntrospectionRule
    new() = {inherit BaseIntrospectionRule("SameFieldAssignment","SameFieldAssignment",Assembly.GetExecutingAssembly());}

    override x.Check(m : Member) =  
       match m with 
          | (:? Method as meth) -> 
                 let instrs = instructions_to_list meth.Instructions
                   in 
                      x.find_assignment instrs
          | _ -> x.Problems 
   
    member x.find_assignment (instructions : Instruction list) =
        match instructions with
           | (load::store::r) when 
                 (load.OpCode  = OpCode.Ldfld && 
                  store.OpCode = OpCode.Stfld && 
                  load.Value = store.Value)
                   -> x.Problems.Add(new Problem(x.GetNamedResolution("SameFieldAssignment",[||]),store.SourceContext))  
                      x.find_assignment r
           | (_::r) -> x.find_assignment r
           | _ -> x.Problems
end

The find_assignment method is used to search for the desired pattern. The IL code sequence is converted to a F# list (via the instructions_to_list utility function), then a list pattern is the used to identify the desired pattern.

We can improve this code by using active patterns. For example we can define the following patterns:

let (|Ldfld|_|) (i : Instruction) = 
   if (i.OpCode = OpCode.Ldfld) then
      Some ((i.Value :?> Field) , i.SourceContext)
   else
      None

let (|Stfld|_|) (i : Instruction) = 
   if (i.OpCode = OpCode.Stfld) then
      Some((i.Value :?> Field),i.SourceContext)
   else
      None

let (|MethodContent|_|) (m : Member) =
    match m with
       | (:? Method as meth) ->
               Some (meth.FullName, 
                     instructions_to_list meth.Instructions)
       | _ -> None

Now we can write:

type SameFieldAssignmentAp = class
    inherit BaseIntrospectionRule
    new() = {inherit BaseIntrospectionRule("SameFieldAssignmentAp","SameFieldAssignmentAp",Assembly.GetExecutingAssembly());}

    override x.Check(m : Member) =  
       match m with 
          | MethodContent(_,instrs) ->  x.find_assignment instrs
          | _ -> x.Problems 
   
    member x.find_assignment (instructions : Instruction list) =
        match instructions with
           | (Ldfld(lField,_)::Stfld(sField,source)::r) when (lField = sField)
                   -> let p = new Problem(x.GetNamedResolution("SameFieldAssignmentAp",[|lField.FullName|]),source) in
                         x.Problems.Add(p)  
                      x.find_assignment r
           | (_::r) -> x.find_assignment r
           | _ -> x.Problems
end

Code for this experiment can be found here.

Using Scala Extractors with the XSD Schema Infoset Model

In this post I'm going to use Scala extractor objects with the Eclipse XML Schema Infoset Model to identify common ways of defining XML Schemas.

Hopefully I'm going to show that complex patterns on common Java objects can be identified using Scala extractors.

The Eclipse Schema Infoset Model is a complex EMF model the represents the W3C XML Schema. The Analyzing XML schemas with the Schema Infoset Model and Analyze Schemas with the XML Schema Infoset Model articles provide a nice explanation on how to work with this model.

For this post I wanted to create Scala patterns that identify common design patterns in Xml Schemas. There are four common patterns for XML Schemas: Russian Doll, Salami Slice, Venetian Blind and Garden of Eden.

The article Introducing Design Patterns in XML Schemas provide a nice explanation on each of this patterns. Also the article talks about a nice feature of NetBeans Enterprise Pack that allows the user to move a schema from one design pattern to another. More information on these design patterns can be found on the article Global vs Local from the xFront site.

The W3C XML Schema model is huge, but for this post I'm going to consider only a small subset.

The first step is the definition of the extractor objects that will be used to have access to certain properties of the Xml Schema Infoset model.

package langexplr.scalaextractorexperiments;

import org.eclipse.emf.ecore.resource._
import org.eclipse.emf.ecore.resource.impl._
import org.eclipse.xsd._
import org.eclipse.xsd.impl._
import org.eclipse.xsd.util._
import org.eclipse.emf.common.util.URI

object XSDSchemaParts {
    def unapply(schema : XSDSchema) = 
      Some ((schema.getTargetNamespace(),
            List.fromIterator(
                  new JavaIteratorWrapper[XSDTypeDefinition](
                           schema.getTypeDefinitions().iterator())),
            List.fromIterator(
               new JavaIteratorWrapper[XSDElementDeclaration](
                   schema.getElementDeclarations().iterator()))))
                       
}

object XSDElementParts {
  def unapply(elementDeclaration : XSDElementDeclaration) =  
    Some((elementDeclaration.getName(),elementDeclaration.getTypeDefinition()))
  
   
}

object XSDComplexType {
  def unapply(typeDefinition : XSDTypeDefinition) = 
      if (typeDefinition.isInstanceOf[XSDComplexTypeDefinition]) {
        val complexType = typeDefinition.asInstanceOf[XSDComplexTypeDefinition];       
        Some((complexType.getName(),complexType.getContent()))
      } else {
        None      
      }
  
}

object XSDSimpleType {
  def unapply(typeDefinition : XSDTypeDefinition) = {
      if (typeDefinition.isInstanceOf[XSDSimpleTypeDefinition]) {
        Some(typeDefinition.asInstanceOf[XSDSimpleTypeDefinition])
      } else {
        None      
      }
  }
}

object XSDParticleContent {
  def unapply(p : XSDParticle) = Some(p.getContent())
}

object XSDSimpleSequenceModelGroup {
  def unapply(complexTypeContent : XSDComplexTypeContent) = {
    complexTypeContent match {
      case XSDParticleContent(mg : XSDModelGroup) 
            if (mg.getCompositor().getName == "sequence") => 
              Some(
                  List.fromIterator(
                        new JavaIteratorWrapper[XSDParticle](
                            mg.getContents.iterator())))
      case _ => None
    }        
  }
 

The XSDSchemaParts, XSDElementParts, XSDComplexType, XSDSimpleType, and XSDParticleContent extractor objects provide access to some properties of a model object. For example the XSDSchemaParts returns a tuple with the target namespace, the complex type definitions and the element definitions.

Also the XSDSimpleSequenceModelGroup provide an easy way to identify a common pattern that is the use of a XSD sequence as the type main element.

A class will be created for each design pattern. The following trait is the base for all of them:

trait XsdDesignPattern {
    def name : String
    def identify(schema:XSDSchema) : boolean   
}

Now we can define each pattern:

Russian Doll

This design pattern says that the structure of the XML Schema is similar to the document structure. Only one public element is defined and all other elements are defined inside of it.

For example:

<?xml version="1.0" encoding="UTF-8"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema"
   targetNamespace="http://langexplr.blogspot.com/DocsRussianDoll"
   xmlns:p="http://langexplr.blogspot.com/DocsRussianDoll"
    xmlns="http://langexplr.blogspot.com/DocsRussianDoll"
   elementFormDefault="qualified">
   <xs:element name="page">
      <xs:complexType>
         <xs:sequence>
            <xs:element name="header">
               <xs:complexType>
                  <xs:sequence>
                     <xs:element name="content" type="xs:string" />
                  </xs:sequence>
                  <xs:attribute name="margin"
                     type="xs:integer" />
               </xs:complexType>

            </xs:element>
            <xs:element name="body">
               <xs:complexType>
                  <xs:sequence>
                     <xs:element name="paragraph"
                        type="xs:string" minOccurs="0" maxOccurs="unbounded" />
                  </xs:sequence>
               </xs:complexType>
            </xs:element>
            <xs:element name="footer">
               <xs:complexType>
                  <xs:sequence>
                     <xs:element name="content" type="xs:string" />
                  </xs:sequence>
                  <xs:attribute name="margin"
                     type="xs:integer" />
               </xs:complexType>
            </xs:element>
         </xs:sequence>
      </xs:complexType>
   </xs:element>
</xs:schema>

The Scala code to identify this design pattern looks like this:

class RussianDoll extends XsdDesignPattern {
  def name = "Russian Doll"
  def identify(schema : XSDSchema) =
    schema match {
            case XSDSchemaParts( 
                   namespace,
                   List(),
                   List(XSDElementParts(
                       name,
                       XSDComplexType(
                            null,
                            XSDSimpleSequenceModelGroup(elements))))) => {                           
                         true                     
                       }
            case _ => false
   }   
}

Salami Slice

This design pattern says that all elements must be declared at the top level with the type declaration inside of them.

For example:

<?xml version="1.0" encoding="UTF-8"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema"
   targetNamespace="http://langexplr.blogspot.com/DocsSalamiSlice"
   xmlns:tns="http://langexplr.blogspot.com/DocsSalamiSlice"
    xmlns="http://langexplr.blogspot.com/DocsSalamiSlice"
   elementFormDefault="qualified">

   <xs:element name="content" type="xs:string" />
   <xs:element name="paragraph" type="xs:string" />

   <xs:element name="header">
      <xs:complexType>
         <xs:sequence>
            <xs:element ref="tns:content" />
         </xs:sequence>
         <xs:attribute name="margin" type="xs:integer" />
      </xs:complexType>
   </xs:element>

   <xs:element name="footer">
      <xs:complexType>
         <xs:sequence>
            <xs:element ref="tns:content" />
         </xs:sequence>
         <xs:attribute name="margin" type="xs:integer" />
      </xs:complexType>
   </xs:element>
   
   <xs:element name="body">
      <xs:complexType>
         <xs:sequence>
            <xs:element ref="tns:paragraph" minOccurs="0"
               maxOccurs="unbounded" />
         </xs:sequence>
      </xs:complexType>
   </xs:element>

   <xs:element name="page">
      <xs:complexType>
         <xs:sequence>
            <xs:element ref="tns:header" />
            <xs:element ref="tns:body" />
            <xs:element ref="tns:footer" />
         </xs:sequence>
      </xs:complexType>
   </xs:element>
</xs:schema>

The Scala code to identify this design pattern looks like this:

class SalamiSlice extends XsdDesignPattern {
  def name = "Salami Slice"
  def identify(schema : XSDSchema) =
    schema match {
      case XSDSchemaParts( 
             namespace,
             List(),
             elements) => { 
              elementsWithReferences(elements)
                 }
      case _ => false 
  }
  // Utility methods
  
  def forAllInnerElements(l : List[XSDElementDeclaration],
                         pred : XSDElementDeclaration => boolean) = 
      l.forall{
        case XSDElementParts(
            _,
            XSDComplexType(null,XSDSimpleSequenceModelGroup(particles))) => 
                 particles.forall({
                      case XSDParticleContent(e:XSDElementDeclaration) => pred(e)
                      case _ => false })                   
        case XSDElementParts(_,XSDComplexType(null,null)) => true
        case XSDElementParts(_,XSDSimpleType(_)) => true
        case _ => false
     }
  
  def elementsWithReferences(x : List[XSDElementDeclaration]) = 
    forAllInnerElements(
         x,
         (e:XSDElementDeclaration) => e.isElementDeclarationReference) 

}

Venetian Blind

This design pattern says that there one global element and all other elements use types declared at the top level.

For example:

<?xml version="1.0" encoding="UTF-8"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema"
   targetNamespace="http://langexplr.blogspot.com/DocsVenetianBlind"
   xmlns:tns="http://langexplr.blogspot.com/DocsVenetianBlind"
   xmlns="http://langexplr.blogspot.com/DocsVenetianBlind"
   elementFormDefault="qualified">

   <xs:complexType name="sectionType">
      <xs:sequence>
         <xs:element name="content" type="xs:string" />
      </xs:sequence>
      <xs:attribute name="margin" type="xs:integer" />
   </xs:complexType>

   <xs:complexType name="bodyType">
      <xs:sequence>
         <xs:element name="paragraph" type="xs:string" minOccurs="0"
            maxOccurs="unbounded" />
      </xs:sequence>

   </xs:complexType>

   <xs:element name="page">
      <xs:complexType>
         <xs:sequence>
            <xs:element name="header" type="tns:sectionType" />
            <xs:element name="body" type="tns:bodyType" />
            <xs:element name="footer" type="tns:sectionType" />
         </xs:sequence>
      </xs:complexType>
   </xs:element>

</xs:schema>

The Scala code for this pattern looks like this:

class VenetianBlind extends XsdDesignPattern {
  def name = "Venetian Blind"
  def identify(schema : XSDSchema) =
      schema match {
        case XSDSchemaParts( 
               namespace,
               types,
               List(XSDElementParts(
                   _,
                   XSDComplexType(
                        _,
                        XSDSimpleSequenceModelGroup(elements))))) => 
                             elements.forall((e:XSDParticle) => 
                                                elementWithTypeReferences(e,types))
        case _ => false 
      }
   def elementWithTypeReferences(e : XSDParticle, types : List[XSDTypeDefinition])  =
     e match {
        case XSDParticleContent(e:XSDElementDeclaration) => 
                e.getTypeDefinition.getContainer.isInstanceOf[XSDSchema]  &&
                !(types.find ((t:XSDTypeDefinition) => t == e.getTypeDefinition)).isEmpty
        case _ => false  
     }
   
}

Garden of Eden

This design pattern says that all the elements and types must be declared global.

<?xml version="1.0" encoding="UTF-8"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema"
   targetNamespace="http://langexplr.blogspot.com/DocsGardenOfEden"
   xmlns:tns="http://langexplr.blogspot.com/DocsGardenOfEden"
   xmlns="http://langexplr.blogspot.com/DocsGardenOfEden"
   elementFormDefault="qualified">

   <xs:complexType name="sectionType">
      <xs:sequence>
         <xs:element ref="tns:content" />
      </xs:sequence>
      <xs:attribute name="margin" type="xs:integer" />
   </xs:complexType>

   <xs:complexType name="bodyType">
      <xs:sequence>
         <xs:element ref="tns:paragraph" minOccurs="0"
            maxOccurs="unbounded" />
      </xs:sequence>
   </xs:complexType>
   
   <xs:element name="content" type="xs:string" />
   
   <xs:element name="paragraph" type="xs:string"/>

   <xs:element name="header" type="tns:sectionType" />
   
   <xs:element name="body" type="tns:bodyType" />
   
   <xs:element name="footer" type="tns:sectionType" />

   <xs:complexType name="pageType">
      <xs:sequence>
         <xs:element ref="tns:header" />
         <xs:element ref="tns:body" />
         <xs:element ref="tns:footer"  />
      </xs:sequence>
   </xs:complexType>
   
   <xs:element name="page" type="tns:pageType" />
</xs:schema>

The Scala code for this pattern looks like this:

class GardenOfEden extends XsdDesignPattern {
  def name = "Garden Of Eden"
  def identify(schema : XSDSchema) =
      schema match {
        case XSDSchemaParts( 
               namespace,
               types,
               elements) =>                   
                     elements.forall((e : XSDElementDeclaration) =>                                             
                                            elementWithTypeReferences(e,types))
        case _ => false 
      }
  
   def elementWithTypeReferences(e : XSDElementDeclaration, types : List[XSDTypeDefinition])  =
         e.getTypeDefinition.getContainer.isInstanceOf[XSDSchema]  &&
         ((types.find ((t:XSDTypeDefinition) => t == e.getTypeDefinition)) match {
             case Some(XSDComplexType(_,XSDSimpleSequenceModelGroup(particles))) => 
                     particles.forall({
                         case XSDParticleContent(e:XSDElementDeclaration) => 
                                   e.isElementDeclarationReference
                         case _ => false })            
             case Some(XSDComplexType(_,null)) => true
             case Some(XSDSimpleType(_)) => true
             case None => 
                   e.getTypeDefinition.getTargetNamespace == "http://www.w3.org/2001/XMLSchema"
             case _ => false
        }) 
       
}

Finally we need a class to test all the patterns:

object XsdDesignPatterns {
    def patterns:List[XsdDesignPattern] = List(new RussianDoll,
                                               new SalamiSlice,
                                               new VenetianBlind,
                                               new GardenOfEden)
    def identify(schema : XSDSchema) =
      patterns.filter((p:XsdDesignPattern) => p identify schema).map((p:XsdDesignPattern) => p.name)
}

The code for this experiment can be found here.