Adventures in Validating Email Addresses with Instaparse

Summary: The email address specifications are complex enough to require a full parser for proper validation.

It started simply enough. I wanted a function to validate the format of an email address.

The regex handled all the invalid cases I could think of. I just needed to test some valid addresses, to make sure I didn't have any false-negatives. So, I looked through the Wikipedia article on Email Addresses.

OK. I've covered those cases.

I didn't know TLDs were valid domains. But, the regex had that case covered.

Really? I guess that makes sense. I just needed to add a few characters to the regex.

Quoted strings?

That's valid?!

Email addresses can have comments?! Alright. Screw regex. I'm using the EBNF hammer.

Note: I'm using some of the PEG extensions for Instaparse, so this is neither pure EBNF nor a pure CFG.

With something this complex, I wanted a more extensive test suite to validate my validator. I found just that in Dominic Sayers’s project is_email(), which was built to solve the same problem in PHP. In the process, he created a test suite covering invalid, deprecated, standard specific, and other syntax cases. It looked like a good metric. And, at the time of writing, the above grammar identifies 74% of valid test cases as valid, and 100% of the invalid test cases as invalid. Since this is meant as a generic format validation function, I consider any test in the “ISEMAIL_ERR” category as an “invalid” case, and all other categories as “valid” cases, including deprecated syntax and length restrictions.

While writing my own grammar, I also ran across a similar post by George Pollard done with Ruby, in 2009. While I didn’t use any of his grammar, it’s nice to know i’m on the right track. Because, while you can use regex, you shouldn’t use regex to parse, or validate, an email address.

Improving the Clojure-Git Interface with a Nice Facade

Summary: A more composable Git interface can be built with a facade that implements standard Clojure interfaces.

In a previous post, I used clj-jgit to interact with a local Git repository. The functions, and general workflow, matched what I would have performed at the command line (git-add followed by git-commit). The workflow made it very easy to get started, and is preferable to using jgit directly, but, to me, it didn’t feel very Clojure-like. It felt like Bash.

While I was using git-add and git-commit, I wanted conj. A Git branch can almost be imagined as a very-persistent strongly-ordered hashmap. Every commit is addressable by a “key”, and has a sequence of commits behind it. I should be able to get commits, map and reduce over them, and conj on a new ones using the built-in clojure functions.

Associative, IFn, IObj, Oh My!

Dig into the Clojure (JVM) internals and you will quickly find a list of common interfaces for everything from metadata to data structure access. I only wanted the behavior of a hashmap, so my implementation list, after much exploration, shrunk to Associative, IFn, IObj, and Object. Associative accounted for most of the functionality, but did not provide map-as-function, metadata handling, or toString.

Proof of Concept

Full Source: https://gist.github.com/Jared314/6418917

Usage

Some points of interest:

• The idea of a staging area disappears because you can now construct a commit, as a hashmap, independently of Git.
• The metadata, and commit information, is queried lazily, and not cached, because the repository could be changed from outside the application.
• I have reused the TreeIterator from a previous post to allow commits without writing to the file system.

There is missing functionality (commit totals, changing branches, and a clean commit data format to name a few), but most of it was outside of my original goal of using conj to add a new commit. There are no technical hurdles to prevent those features in the future, but my application did not call for them. This might make for a nice feature to submit to the clj-jgit project, if I ever fill in the missing features.

Automating a Clojure Project's File Layout

I have come to accept the file's place in application development. In Leiningen based Clojure projects, a clean project layout has a file per namespace layout, and a directory per parent namespace. But, as a developer, I write functions, not files. The files are just artifacts. The creation and organization of code files is so systematic, it could be automated with something that maps functions/declarations into the hierarchical file structure used by project tooling.

Proof of concept: (https://gist.github.com/Jared314/6144582)

The idea behind this “object-hierarchical mapper” is to abstract out the project file layout from the functions and namespaces. There is too much tooling around files to replace them as a code storage format, but there is very little reason to think about file organization.

This code works by passing the function declarations (thing1, thing2, and thing3), with their corresponding namespace declarations (tester1.core, tester1.server), to the parse function which builds a tree whose nodes correspond to the namespace hierarchy. That tree (nested hash-maps) is then written out to the file system, using the write! function, into a valid project structure. The current issues center around optimizations, and messy code. In the generated files, the namespace declarations are not combined efficiently, and the functions are preceded by a list of declares to prevent reference ordering issues.

This is not a new concept. I would guess the idea extends as far back as the 1960s, because that really appears to be the case with most ideas in CS. I just remember the first time I was amazed by the idea after watching the Code Bubbles demo. More recently, Light Table also had a similar demo, where code was edited in a single visual workspace. I believe they plan to bring that feature back in a future version. No matter where the idea came from, it seems like a useful layer of indirection.

This might end up working best as a lein plugin, with editors saving their changes “through” it, because the project file layout is tied to lein and other lein plugins. It might also be an interesting experiment to use a git repository as an additional backend, but that would have to happen after a refactoring of the write! function to something more functionally pure.

Learning core.async: A High School Tale

The examples use the 2013-07-24 snapshot of core.async. At the time of writing, the API is still in flux and very experimental.

[org.clojure/core.async "0.1.0-SNAPSHOT"]

from:

["sonatype-oss-public" "https://oss.sonatype.org/content/repositories/snapshots/"]

Once upon a time, Alice wanted to invite Bob to an awesome party she had heard about, but she didn’t know where the party is going to be yet. So, she told Bob to wait by his phone, and she would send him the location, when she found out.

https://gist.github.com/Jared314/6043638

Unfortunately for them, the police were monitoring all the text messages. So, the police showed up, about an hour after the party had started, and arrested everyone for underage drinking.

Broadcasting

Alice, now feeling bad about the last party, decided to make it up to Bob and Carol by inviting them both to the next party she heard about. But, this time, she wanted to make sure no one else could see the message. So, she made a Facebook group, and only included Bob and Carol.

https://gist.github.com/Jared314/6047489

Unfortunately for them, the police were monitoring all the Facebook groups and messages. So, the police showed up, about an hour after the party had started, and arrested everyone for underage drinking.

Chaining Go Blocks

Alice decided to try one more time. This time also including Dave, to make up for the last failed party. But, Alice was getting slightly paranoid, so she decided to only tell Bob the location of the party, then have Bob tell Carol, and then have Carol pass it on to Dave.

https://gist.github.com/Jared314/6047624

Unfortunately for them, Dave got pulled over by the police, for a broken tail light, on his way to the party. Being within one hundred miles of the border, the police searched his car and found the handwritten note from Carol. So, the police showed up, about an hour after the party had started, and arrested everyone for underage drinking.

Timeouts

With this being the third time Alice, Bob, Carol, Dave, and Eve had appeared in his court, Judge Frank was ready to throw them in jail. In each case he decided to sentence them to several months in jail, based on their honesty (represented by a random number), with the option of letting them out early on good behavior (represented by an extra channel for each person).

https://gist.github.com/Jared314/6047789

Takeaways:

1. Go blocks will block and execute in their own thread pool or, for the cljs version, their own state-machine-context-like-thing.
2. The broadcast and multiplex (a.k.a. fan-out and fan-in) currently exist only as experiments. I hope they get rolled into the library, because I don’t want to have to write them myself.
3. There is no “wait for all channels to have a value” function. Alts! and Multiplex return on the first channel to have a value.
4. It looks like you could change the underlying channel implementation to something like a ZeroMQ (zmq-async) or RabbitMQ, but i’m not sure if it would actually be a useful abstraction.

Tree storage in Git with JGit and Clojure

Summary: You can store parse trees, or ASTs, directly in a Git repo, but then you have new problems.

Git stores a file structure as trees, using Objects for files and Tree Objects for directories. The tools usually ignore empty directories, but the internal object store has no problem handling them. So, every so often, I wonder why someone doesn’t store the full AST, or just the parse tree, in the repository, instead of just the files.

Proof of Concept

https://gist.github.com/Jared314/5655934

To summarize the code, I’m using a grammar, from the Instaparse tests, that groups 'a's and 'b's from the string “aaaaabbbaaaabb”. After parsing the text, I apply an Enlive transformation that removes the A nodes from the parse tree. I then render the result back into a tree, made of lists and hash-maps, to be stored in the Git repo using JGit and a custom JGit WorkingTreeIterator. Inside the custom tree iterator, I lazily convert each node into a JGit Entry with a FileMode of TREE or REGULAR_FILE, depending on if the node has children.

Text > Instaparse > Enlive transform > Render tree > Custom TreeIterator > AddCommand

The Enlive transform and the render function are not required, but, in this case, I wanted to manipulate the tree before saving it.

The Good

• Style Independent: The stored representation is immune to statements that parse, or even compile, equivalently. The argument of tabs versus spaces, variable declaration alignment, and other, slightly pedantic, coding style arguments become meaningless, because only the parser or compiler’s “view” of the code is stored.

The Bad

• Hard Version Dependency: The stored structure is directly dependent on a compiler version and any bugs or limitations of that version. Assuming the stored tree is tagged with language version information, the language developers would need to release a migration script, a translator, or keep previous versions available for long periods of time, as opposed to just relying on customers to change their own code.

• Code Generator Required: Assuming only the tree is stored, checking out code from a repository would require a human-readable code generator, like what most decompilers do today. While this would allow for personalized code styling, it is an additional language specific tool to build and maintain.

• Diff and Merge Tool Limitations: Most mainstream diff and merge tools focus solely on the contents of the stored blobs and assume node order independence. Whether this requires different algorithms or a different workflow, the tools will have to change to handle large trees and forests.

The Code

TinyCore x64 4.x

TinyCore linux releases pre-built ISO images for x86 platforms, but leaves remastering them for the x64 platform is up to the user. After banging around for a few hours, I built my own script to handle the remastering task. If you need a more complete tool, the wiki has a write up on remastering with ezremaster, a GUI tool run from within a TinyCore instance.
build-microcore64.sh

• 2011-10-09 - Edit: Added remastering with ezremaster
• 2011-10-08 - Initial Post

Useless Realizations

I was writing a compiler, for my own "fun", and had the realization that C# v3.5 can be very succinct. I had built out my lexer and was roughing out a target lisp-like syntax when I realized it was just like the C# I was writing.

private static Token GetToken(char p, IEnumerable validTokens)
{
return validTokens.FirstOrDefault(item => item.Value.Contains(p));
}

(define GetToken [p validTokens]
(first validTokens (define [item] (contains (value item) p)))
)

I have not decided if this is proof I have lost my imagination or C#'s progress as a language.

IOC Containers - Part 3

A little thinking after the last post lead me to the idea of persisting objects beyond the scope of a running program, a super singleton. Because an IOC container abstracts the source, and in some ways the lifespan, of an object, there is nothing stopping me from persisting the object and using it between application instances or other systems. The code would never have to know.

I used db4o in my code because of the simplicity, and native object storage. If you have never used db4o, I suggest it.

Also, this provider required explicit disposal, so I went back and implemented IDisposable on the Repository and the SingleServiceProvider.

Usage:

    var r = new Repository();

    r.RegisterServiceProvider(new SingleServiceProvider());

    r.Register<IObjectContainer, SingleServiceProvider>(() => Db4oFactory.OpenFile("test.db"));
    r.RegisterServiceProvider(new DB4OSingleServiceProvider(r.GetInstance<IObjectContainer>()));

    r.Register<IMyClass, DB4OSingleServiceProvider>(() => new MyClass("a"));

    IMyClass m = r.GetInstance<IMyClass>();

    r.Dispose();

Code:

    public class DB4OSingleServiceProvider : IRepositoryServiceProvider, IDisposable
    {
        private readonly Dictionary<Type, object> objects = new Dictionary<Type, object>();
        private readonly IObjectContainer container;

        public DB4OSingleServiceProvider(IObjectContainer container)
        {
            this.container = container;
        }

        ~DB4OSingleServiceProvider() { this.Dispose(false); }

        public void Remove(Type targetType)
        {
            var resultSet = this.container.Query(targetType);
            while (resultSet.HasNext())
            {
                this.container.Delete(resultSet.Next());
            }
            this.container.Commit();
        }

        public void Update(object o)
        {
            this.container.Store(o);
        }

        #region IRepositoryServiceProvider Members

        public void RegisterService(Type targetType, FactoryDelegate factoryMethod)
        {
            var resultSet = this.container.Query(targetType);
            if (resultSet.Count < 1)
            {
                this.container.Store(factoryMethod());
            }
        }

        #endregion

        #region IServiceProvider Members

        public object GetService(Type serviceType)
        {
            return this.container.Query(serviceType).Next();
        }

        #endregion

        [ IDisposable Members … ]
    }

I have not resolved how to handle events when the object has not been re-hydrated or dealing with multiple applications touching the same object database. Perhaps I will think about that some other time.

The biggest thing I have learned from this is that building something myself helps me understand. Now I am going to to try Autofac.

IOC Containers - Part 2

My initial IOC container was an automatic factory. When GetInstance was called it executed the stored factory method and returned. You could technically put anything you wanted into the factory method, including a singleton instance or a database call, but it is no better than a standard factory method.

While looking at some of the IOC containers listed in my last post, I noticed the user could select the lifespan of each type. So, I went back to the workbench.



I have abstracted out the lifespan from the repository, through the IRepositoryServiceProvider interface. This change also opens up the possibility for creating custom lifespans.

Usage:

    var r = new Repository();
    r.RegisterServiceProvider(new FactoryServiceProvider());
    r.Register<IMyClass, FactoryServiceProvider>(() => new MyClass("a"));
    IMyClass m = r.GetInstance<IMyClass>();

Code:

    public delegate object FactoryDelegate();
    public delegate T FactoryDelegate<T>();

    public interface IRepositoryServiceProvider : IServiceProvider
    {
        void RegisterService(Type targetType, FactoryDelegate factoryMethod);
    }

    public class RepositoryPlusOne
    {
        private readonly Dictionary<Type, IRepositoryServiceProvider> providers = 
    new Dictionary<Type, IRepositoryServiceProvider>();
        private readonly Dictionary<Type, IRepositoryServiceProvider> types = 
    new Dictionary<Type, IRepositoryServiceProvider>();

        public void Register<T, U>(FactoryDelegate<T> factoryMethod)
            where T : class
            where U : IRepositoryServiceProvider
        {
            Type u = typeof(U);
            Type t = typeof(T);

            if (!providers.ContainsKey(u)) throw new ArgumentException("Unregistered Provider", "U");

            providers[u].RegisterService(t, () => factoryMethod());
            types.Add(t, providers[u]);
        }

        public void RegisterServiceProvider(IRepositoryServiceProvider provider)
        {
            providers.Add(provider.GetType(), provider);
        }

        public TService GetInstance<TService>() where TService : class
        {
            Type t = typeof(TService);
            if (!this.factories.ContainsKey(t)) return default(TService);
            return this.factories[t]() as TService;
        }
    }

    public class FactoryServiceProvider : IRepositoryServiceProvider
    {
        private readonly Dictionary<Type, FactoryDelegate> factories = 
    new Dictionary<Type, FactoryDelegate>();

        #region IRepositoryServiceProvider Members

        public void RegisterService(Type targetType, FactoryDelegate factoryMethod)
        {
            factories.Add(targetType, factoryMethod);
        }

        #endregion

        #region IServiceProvider Members

        public object GetService(Type serviceType)
        {
            return (factories.ContainsKey(serviceType)) ? factories[serviceType]() : null;
        }

        #endregion
    }

    public class SingleServiceProvider : IRepositoryServiceProvider
    {
        private readonly Dictionary<Type, object> objects = 
    new Dictionary<Type, object>();

        #region IRepositoryServiceProvider Members

        public void RegisterService(Type targetType, FactoryDelegate factoryMethod)
        {
            objects.Add(targetType, factoryMethod());
        }

        #endregion

        #region IServiceProvider Members

        public object GetService(Type serviceType)
        {
            return (objects.ContainsKey(serviceType)) ? objects[serviceType] : null;
        }

        #endregion
    }

IOC Containers

Inversion of control is an interesting pattern, but it has a flaw. When building a system following the IOC pattern, the code bloat seems to bubble up to the top. The higher level objects start creating and managing all the required parts. This starts to fall down when you scale it up beyond a small number of objects. The accepted solution is to move most of the object creation into an IOC container, like Windsor, StructureMap, Autofac, etc.

You register a type, and dependencies, with the IOC container and then just ask for it when you need it. That is great, except I don't know how or why they work the way they do. Most people have responded to my questions with the classic open source creed, “you can look at the source.” Reading the source is like reading a scientific research paper. So, I tried building one myself.

    public delegate object FactoryDelegate();
    public delegate T FactoryDelegate<T>();

    public class Repository
    {
        private readonly Dictionary<Type, FactoryDelegate> factories = 
            new Dictionary<Type, FactoryDelegate>();

        public void Register<T>(FactoryDelegate<T> factoryMethod) where T : class
        {
            this.factories.Add(typeof(T), () => factoryMethod());
        }

        public TService GetInstance<TService>() where TService : class
        {
            Type t = typeof(TService);
            if (!this.factories.ContainsKey(t)) return default(TService);
            return this.factories[t]() as TService;
        }
    }

After a few hours of tinkering, my basic IOC container is 16 lines, including error handling.

Usage:

    var r = new Repository();
    r.Register<IMyClass>(() => new MyClass("a"));
    IMyClass m = r.GetInstance<IMyClass>();

A factory method is registered for each type you want the Repository to handle. Each time the GetInstance method is called, it retrieves the stored factory method, executes it, and returns a strongly typed result. I think I will explore this a little more.