<p> 
// build a js function that can match any uri template in the graph
//
// this can be used on client or server
//  on server use acre.require('.../matcher')
//  on client http://api.freebase.com/api/trans/raw/.../matcher
//

if (typeof urit == 'undefined')
   urit = {};

(function (){


/**
 *  utility to escape characters that are special in RegExps
 */
var escape_re = function(s) {
    var specials = /[.*+?|()\[\]{}\\]/g;
    return s.replace(specials, '\\$&amp;');
};


// 
// parseUri() from http://blog.stevenlevithan.com/archives/parseuri
// 
// parseUri 1.2.2
// (c) Steven Levithan 
// MIT License

urit.parseUri = function (str) {
    var    o   = urit.parseUri.options,
        m   = o.parser[o.strictMode ? "strict" : "loose"].exec(str),
        uri = {},
        i   = 14;

    while (i--) uri[o.key[i]] = m[i] || "";

    uri[o.q.name] = {};
    uri[o.key[12]].replace(o.q.parser, function ($0, $1, $2) {
        if ($1) uri[o.q.name][$1] = $2;
    });

    return uri;
};

urit.parseUri.options = {
    strictMode: false,
    key: ["source","protocol","authority","userInfo","user","password","host","port","relative","path","directory","file","query","anchor"],
    q:   {
        name:   "queryKey",
        parser: /(?:^|&amp;)([^&amp;=]*)=?([^&amp;]*)/g
    },
    parser: {
        strict: /^(?:([^:\/?#]+):)?(?:\/\/((?:(([^:@]*)(?::([^:@]*))?)?@)?([^:\/?#]*)(?::(\d*))?))?((((?:[^?#\/]*\/)*)([^?#]*))(?:\?([^#]*))?(?:#(.*))?)/,
        loose:  /^(?:(?![^:@]+:[^:@\/]*@)([^:\/?#.]+):)?(?:\/\/)?((?:(([^:@]*)(?::([^:@]*))?)?@)?([^:\/?#]*)(?::(\d*))?)(((\/(?:[^?#](?![^?#\/]*\.[^?#\/.]+(?:[?#]|$)))*\/?)?([^?#\/]*))(?:\?([^#]*))?(?:#(.*))?)/
    }
};

// end parseUri() code


/**
 *  Construct a URI Template from a URI with {var} substrings in it.
 *
 */
urit.URITemplate = function (s, info) {
    this.template = s;
    this.info = info;
    this.uriinfo = urit.parseUri(s);
    this.host = this.uriinfo.host;

    // build this.params here
    // and pre-split the pattern?

    var params = this.params = [];

    this.rx = escape_re(s).replace(/\\\{([^}\\]+)\\\}/g, function (str, name) {
        params.push({
            name: name
        });
        switch (name) {
          case 'key':
            return '([^/?#]+)';
          case 'path':
            return '([^?#]+)';
          case 'slop':
            return '(.*)';
          default:
            return '([^/?#]+)';
        }
    });
  
    // make trailing '/' on a url optional
    if (this.rx[this.rx.length-1] == '/')
         this.rx += '?';
};

/**
 *  Apply a template to a dict of values and return a URI
 *  
 */
urit.URITemplate.prototype.run = function (args) {
    // String.replace() with a function argument can be
    // very very slow, might precompile this somehow?
    var uri = this.template.replace(/\{[0-9a-zA-Z_]+\}/, function (m) {
        var key = m.substring(1, m.length-1);
        //mjt.log('M', m, key, args[key]);
        return args[key];
    });

    return uri;
};

/**
 *  Decompose a URI into a structure.
 *
 *  ideally URI Templating should be aware of the URI structure
 *  so that it doesn't require ordered query params, for example.
 *  
 */
urit.URITemplate.parse_uri = function (url) {
    // parse the url
    //  regexp from http://badassery.blogspot.com/2007/02/parseuri-split-urls-in-javascript.html
    var url_split_re = new RegExp("^(?:([^:/?#.]+):)?(?://)?(([^:/?#]*)(?::(\\d*))?)?((/(?:[^?#](?![^?#/]*\\.[^?#/.]+(?[\\?#]|$)))*/?)?([^?#/]*))?(?:\\?([^#]*))?(?:#(.*))?");
    var url_split = url_split_re.exec(url);

    if (!url_split)
        throw new Error('bad url argument: '+ url);

    var info = {
        protocol: url_split[1],
        host: url_split[2],
        path: url_split[5],
        query: url_split[8],
        fragment: url_split[9]
    };

    info.params = acre.form.decode(info.query);

    return info;
};


//
// do a mql query to "urlts" using whatever means available,
// then pass the result to this constructor for parsing
// e.g. the response to this mqlread:
//    [{
//      "type": "/common/uri_template",
//      "id": null,
//      "template": null
//    }]
//
urit.Matcher = function (templateinfo) {
    this.templateinfo = templateinfo;
    this.parse_templates();
}

urit.Matcher.templateq = function () {
    return [{
        "type":     "/common/uri_template",
        "id":       null,
        "name":     null,
        "template": null,
        "recognized_template": [],
        "key_property": {
          id: null,
          // to avoid  /guid/9202a8c04000641f8000000008e573b8
          // until /common/uri_template/key_property is unique
          '/type/property/enumeration': {'id':null}    
        }
    }];
};

urit.Matcher.prototype.toJSON = function () {
    return {
        regexp: this.regexp,
        templates: this.templates
    };
};

/**
 *  compile a Matcher from a list of /common/uri_template responses.
 *  builds a list of URITemplate objects.
 */
urit.Matcher.prototype.parse_templates = function () {
    var templates = [];
    var rxs = [];

    for (var i = 0; i </p>