1 /**
  2  * Copyright (C) 2012 KO GmbH <copyright@kogmbh.com>
  3  *
  4  * @licstart
  5  * This file is part of WebODF.
  6  *
  7  * WebODF is free software: you can redistribute it and/or modify it
  8  * under the terms of the GNU Affero General Public License (GNU AGPL)
  9  * as published by the Free Software Foundation, either version 3 of
 10  * the License, or (at your option) any later version.
 11  *
 12  * WebODF is distributed in the hope that it will be useful, but
 13  * WITHOUT ANY WARRANTY; without even the implied warranty of
 14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 15  * GNU Affero General Public License for more details.
 16  *
 17  * You should have received a copy of the GNU Affero General Public License
 18  * along with WebODF.  If not, see <http://www.gnu.org/licenses/>.
 19  * @licend
 20  *
 21  * @source: http://www.webodf.org/
 22  * @source: https://github.com/kogmbh/WebODF/
 23  */
 24 
 25 /*global Node, runtime, xmldom*/
 26 
 27 /**
 28  * RelaxNG can check a DOM tree against a Relax NG schema
 29  * The RelaxNG implementation is currently not complete. Relax NG should not
 30  * report errors on valid DOM trees, but it will not check all constraints that
 31  * a Relax NG file can define. The current implementation does not load external
 32  * parts of a Relax NG file.
 33  * The main purpose of this Relax NG engine is to validate runtime ODF
 34  * documents. The DOM tree is traversed via a TreeWalker. A custom TreeWalker
 35  * implementation can hide parts of a DOM tree. This is useful in WebODF, where
 36  * special elements and attributes in the runtime DOM tree.
 37  *
 38  * implementation according to
 39  * http://www.thaiopensource.com/relaxng/derivative.html
 40  */
 41 /**
 42  * @typedef {{
 43  *     type: string,
 44  *     nullable: boolean,
 45  *     hash: (undefined|string),
 46  *     nc: (undefined|!xmldom.RelaxNGItem),
 47  *     p: (undefined|!xmldom.RelaxNGItem),
 48  *     p1: (undefined|!xmldom.RelaxNGItem),
 49  *     p2: (undefined|!xmldom.RelaxNGItem),
 50  *     textDeriv: (undefined|function(*=,*=):xmldom.RelaxNGItem),
 51  *     startTagOpenDeriv: (undefined|function(*=):xmldom.RelaxNGItem),
 52  *     attDeriv: function(*=,*=):xmldom.RelaxNGItem,
 53  *     startTagCloseDeriv: function():xmldom.RelaxNGItem,
 54  *     endTagDeriv: (undefined|function():xmldom.RelaxNGItem)
 55  *  }}*/
 56 xmldom.RelaxNGItem;
 57 /**
 58  * @constructor
 59  */
 60 xmldom.RelaxNG = function RelaxNG() {
 61     "use strict";
 62     var xmlnsns = "http://www.w3.org/2000/xmlns/",
 63         createChoice,
 64         createInterleave,
 65         createGroup,
 66         createAfter,
 67         createOneOrMore,
 68         createValue,
 69         createAttribute,
 70         createNameClass,
 71         createData,
 72         makePattern,
 73         applyAfter,
 74         childDeriv,
 75         rootPattern,
 76         /**@type{!xmldom.RelaxNGItem}*/
 77         notAllowed = {
 78             type: "notAllowed",
 79             nullable: false,
 80             hash: "notAllowed",
 81             nc: undefined,
 82             p: undefined,
 83             p1: undefined,
 84             p2: undefined,
 85             textDeriv: function () { return notAllowed; },
 86             startTagOpenDeriv: function () { return notAllowed; },
 87             attDeriv: function () { return notAllowed; },
 88             startTagCloseDeriv: function () { return notAllowed; },
 89             endTagDeriv: function () { return notAllowed; }
 90         },
 91         /**@type{!xmldom.RelaxNGItem}*/
 92         empty = {
 93             type: "empty",
 94             nullable: true,
 95             hash: "empty",
 96             nc: undefined,
 97             p: undefined,
 98             p1: undefined,
 99             p2: undefined,
100             textDeriv: function () { return notAllowed; },
101             startTagOpenDeriv: function () { return notAllowed; },
102             attDeriv: function () { return notAllowed; },
103             startTagCloseDeriv: function () { return empty; },
104             endTagDeriv: function () { return notAllowed; }
105         },
106         /**@type{!xmldom.RelaxNGItem}*/
107         text = {
108             type: "text",
109             nullable: true,
110             hash: "text",
111             nc: undefined,
112             p: undefined,
113             p1: undefined,
114             p2: undefined,
115             textDeriv: function () { return text; },
116             startTagOpenDeriv: function () { return notAllowed; },
117             attDeriv: function () { return notAllowed; },
118             startTagCloseDeriv: function () { return text; },
119             endTagDeriv: function () { return notAllowed; }
120         };
121 
122     /**
123      * @param {function():!xmldom.RelaxNGItem} func
124      * @return {function():!xmldom.RelaxNGItem}
125      */
126     function memoize0arg(func) {
127         /**
128          * @return {function():!xmldom.RelaxNGItem}
129          */
130         function f() {
131             /**
132              * @type {xmldom.RelaxNGItem}
133              */
134             var cache;
135             /**
136              * @return {!xmldom.RelaxNGItem}
137              */
138             function g() {
139                 if (cache === undefined) {
140                     cache = func();
141                 }
142                 return cache;
143             }
144             return g;
145         }
146         return f();
147     }
148     /**
149      * @param {string} type
150      * @param {function(!xmldom.RelaxNGItem):!xmldom.RelaxNGItem} func
151      * @return {function(!xmldom.RelaxNGItem):!xmldom.RelaxNGItem}
152      */
153     function memoize1arg(type, func) {
154         /**
155          * @return {function(!xmldom.RelaxNGItem):!xmldom.RelaxNGItem}
156          */
157         function f() {
158             var /**@type{!Object.<string,!xmldom.RelaxNGItem>}*/
159                 cache = {},
160                 /**@type{number}*/
161                 cachecount = 0;
162             /**
163              * @param {!xmldom.RelaxNGItem} a
164              * @return {!xmldom.RelaxNGItem}
165              */
166             function g(a) {
167                 var ahash = a.hash || a.toString(),
168                     v;
169                 if (cache.hasOwnProperty(ahash)) {
170                     return cache[ahash];
171                 }
172                 cache[ahash] = v = func(a);
173                 v.hash = type + cachecount.toString();
174                 cachecount += 1;
175                 return v;
176             }
177             return g;
178         }
179         return f();
180     }
181     /**
182      * @param {function(!Node):!xmldom.RelaxNGItem} func
183      * @return {function(!Node):!xmldom.RelaxNGItem}
184      */
185     function memoizeNode(func) {
186         /**
187          * @return {function(!Node):!xmldom.RelaxNGItem}
188          */
189         function f() {
190             var /**@type{!Object.<string,!Object.<string,!xmldom.RelaxNGItem>>}*/
191                 cache = {};
192             /**
193              * @param {!Node} node
194              * @return {!xmldom.RelaxNGItem}
195              */
196             function g(node) {
197                 var v,
198                     /**@type{!Object.<string,!xmldom.RelaxNGItem>}*/
199                     m;
200                 if (!cache.hasOwnProperty(node.localName)) {
201                     cache[node.localName] = m = {};
202                 } else {
203                     m = cache[node.localName];
204                     v = m[node.namespaceURI];
205                     if (v !== undefined) {
206                         return v;
207                     }
208                 }
209                 m[node.namespaceURI] = v = func(node);
210                 return v;
211             }
212             return g;
213         }
214         return f();
215     }
216     /**
217      * @param {string} type
218      * @param {undefined|function(!xmldom.RelaxNGItem,!xmldom.RelaxNGItem):(undefined|xmldom.RelaxNGItem)} fastfunc
219      * @param {function(!xmldom.RelaxNGItem,!xmldom.RelaxNGItem):!xmldom.RelaxNGItem} func
220      * @return {function(!xmldom.RelaxNGItem,!xmldom.RelaxNGItem):!xmldom.RelaxNGItem}
221      */
222     function memoize2arg(type, fastfunc, func) {
223         /**
224          * @return {function(!xmldom.RelaxNGItem,!xmldom.RelaxNGItem):!xmldom.RelaxNGItem}
225          */
226         function f() {
227             var /**@type{!Object.<string,!Object.<string,!xmldom.RelaxNGItem>>}*/
228                 cache = {},
229                 /**@type{number}*/
230                 cachecount = 0;
231             /**
232              * @param {!xmldom.RelaxNGItem} a
233              * @param {!xmldom.RelaxNGItem} b
234              * @return {!xmldom.RelaxNGItem}
235              */
236             function g(a, b) {
237                 var /**@type{undefined|!xmldom.RelaxNGItem}*/
238                     v = fastfunc && fastfunc(a, b),
239                     ahash,
240                     bhash,
241                     /**@type{!Object.<string,!xmldom.RelaxNGItem>}*/
242                     m;
243                 if (v !== undefined) { return v; }
244                 ahash = a.hash || a.toString();
245                 bhash = b.hash || b.toString();
246                 if (!cache.hasOwnProperty(ahash)) {
247                     cache[ahash] = m = {};
248                 } else {
249                     m = cache[ahash];
250                     if (m.hasOwnProperty(bhash)) {
251                         return m[bhash];
252                     }
253                 }
254                 m[bhash] = v = func(a, b);
255                 v.hash = type + cachecount.toString();
256                 cachecount += 1;
257                 return v;
258             }
259             return g;
260         }
261         return f();
262     }
263     /**
264      * This memoize function can be used for functions where the order of two
265      * arguments is not important.
266      * @param {string} type
267      * @param {undefined|function(!xmldom.RelaxNGItem,!xmldom.RelaxNGItem):(undefined|!xmldom.RelaxNGItem)} fastfunc
268      * @param {function(!xmldom.RelaxNGItem,!xmldom.RelaxNGItem):!xmldom.RelaxNGItem} func
269      * @return {function(!xmldom.RelaxNGItem,!xmldom.RelaxNGItem):!xmldom.RelaxNGItem}
270      */
271     function unorderedMemoize2arg(type, fastfunc, func) {
272         function f() {
273             var /**@type{!Object.<string,!Object.<string,!xmldom.RelaxNGItem>>}*/
274                 cache = {},
275                 /**@type{number}*/
276                 cachecount = 0;
277             /**
278              * @param {!xmldom.RelaxNGItem} a
279              * @param {!xmldom.RelaxNGItem} b
280              * @return {!xmldom.RelaxNGItem}
281              */
282             function g(a, b) {
283                 var /**@type{undefined|!xmldom.RelaxNGItem}*/
284                     v = fastfunc && fastfunc(a, b),
285                     ahash,
286                     bhash,
287                     hash,
288                     /**@type{!Object.<string,!xmldom.RelaxNGItem>}*/
289                     m;
290                 if (v !== undefined) { return v; }
291                 ahash = a.hash || a.toString();
292                 bhash = b.hash || b.toString();
293                 if (ahash < bhash) {
294                     hash = ahash; ahash = bhash; bhash = hash;
295                     hash = a; a = b; b = hash;
296                 }
297                 if (!cache.hasOwnProperty(ahash)) {
298                     cache[ahash] = m = {};
299                 } else {
300                     m = cache[ahash];
301                     if (m.hasOwnProperty(bhash)) {
302                         return m[bhash];
303                     }
304                 }
305                 m[bhash] = v = func(a, b);
306                 v.hash = type + cachecount.toString();
307                 cachecount += 1;
308                 return v;
309             }
310             return g;
311         }
312         return f();
313     }
314     function getUniqueLeaves(leaves, pattern) {
315         if (pattern.p1.type === "choice") {
316             getUniqueLeaves(leaves, pattern.p1);
317         } else {
318             leaves[pattern.p1.hash] = pattern.p1;
319         }
320         if (pattern.p2.type === "choice") {
321             getUniqueLeaves(leaves, pattern.p2);
322         } else {
323             leaves[pattern.p2.hash] = pattern.p2;
324         }
325     }
326     createChoice = memoize2arg("choice", function (p1, p2) {
327         if (p1 === notAllowed) { return p2; }
328         if (p2 === notAllowed) { return p1; }
329         if (p1 === p2) { return p1; }
330     }, function (p1, p2) {
331         /**
332          * @param {!xmldom.RelaxNGItem} p1
333          * @param {!xmldom.RelaxNGItem} p2
334          * @return {!xmldom.RelaxNGItem}
335          */
336         function makeChoice(p1, p2) {
337             return {
338                 type: "choice",
339                 nullable: p1.nullable || p2.nullable,
340                 hash: undefined,
341                 nc: undefined,
342                 p: undefined,
343                 p1: p1,
344                 p2: p2,
345                 textDeriv: function (context, text) {
346                     return createChoice(p1.textDeriv(context, text),
347                         p2.textDeriv(context, text));
348                 },
349                 startTagOpenDeriv: memoizeNode(function (node) {
350                     return createChoice(p1.startTagOpenDeriv(node),
351                         p2.startTagOpenDeriv(node));
352                 }),
353                 attDeriv: function (context, attribute) {
354                     return createChoice(p1.attDeriv(context, attribute),
355                         p2.attDeriv(context, attribute));
356                 },
357                 startTagCloseDeriv: memoize0arg(function () {
358                     return createChoice(p1.startTagCloseDeriv(),
359                         p2.startTagCloseDeriv());
360                 }),
361                 endTagDeriv: memoize0arg(function () {
362                     return createChoice(p1.endTagDeriv(), p2.endTagDeriv());
363                 })
364             };
365         }
366         var leaves = {}, i;
367         getUniqueLeaves(leaves, {p1: p1, p2: p2});
368         p1 = undefined;
369         p2 = undefined;
370         for (i in leaves) {
371             if (leaves.hasOwnProperty(i)) {
372                 if (p1 === undefined) {
373                     p1 = leaves[i];
374                 } else if (p2 === undefined) {
375                     p2 = leaves[i];
376                 } else {
377                     p2 = createChoice(p2, leaves[i]);
378                 }
379             }
380         }
381         return makeChoice(p1, p2);
382     });
383     createInterleave = unorderedMemoize2arg("interleave", function (p1, p2) {
384         if (p1 === notAllowed || p2 === notAllowed) { return notAllowed; }
385         if (p1 === empty) { return p2; }
386         if (p2 === empty) { return p1; }
387     }, function (p1, p2) {
388         return {
389             type: "interleave",
390             nullable: p1.nullable && p2.nullable,
391             hash: undefined,
392             p1: p1,
393             p2: p2,
394             textDeriv: function (context, text) {
395                 return createChoice(
396                     createInterleave(p1.textDeriv(context, text), p2),
397                     createInterleave(p1, p2.textDeriv(context, text))
398                 );
399             },
400             startTagOpenDeriv: memoizeNode(function (node) {
401                 return createChoice(
402                     applyAfter(function (p) { return createInterleave(p, p2); },
403                                p1.startTagOpenDeriv(node)),
404                     applyAfter(function (p) { return createInterleave(p1, p); },
405                                p2.startTagOpenDeriv(node))
406                 );
407             }),
408             attDeriv: function (context, attribute) {
409                 return createChoice(
410                     createInterleave(p1.attDeriv(context, attribute), p2),
411                     createInterleave(p1, p2.attDeriv(context, attribute))
412                 );
413             },
414             startTagCloseDeriv: memoize0arg(function () {
415                 return createInterleave(p1.startTagCloseDeriv(),
416                     p2.startTagCloseDeriv());
417             }),
418             endTagDeriv: undefined
419         };
420     });
421     createGroup = memoize2arg("group", function (p1, p2) {
422         if (p1 === notAllowed || p2 === notAllowed) { return notAllowed; }
423         if (p1 === empty) { return p2; }
424         if (p2 === empty) { return p1; }
425     }, function (p1, p2) {
426         return {
427             type: "group",
428             p1: p1,
429             p2: p2,
430             nullable: p1.nullable && p2.nullable,
431             textDeriv: function (context, text) {
432                 var p = createGroup(p1.textDeriv(context, text), p2);
433                 if (p1.nullable) {
434                     return createChoice(p, p2.textDeriv(context, text));
435                 }
436                 return p;
437             },
438             startTagOpenDeriv: function (node) {
439                 var x = applyAfter(function (p) { return createGroup(p, p2); },
440                         p1.startTagOpenDeriv(node));
441                 if (p1.nullable) {
442                     return createChoice(x, p2.startTagOpenDeriv(node));
443                 }
444                 return x;
445             },
446             attDeriv: function (context, attribute) {
447                 return createChoice(
448                     createGroup(p1.attDeriv(context, attribute), p2),
449                     createGroup(p1, p2.attDeriv(context, attribute))
450                 );
451             },
452             startTagCloseDeriv: memoize0arg(function () {
453                 return createGroup(p1.startTagCloseDeriv(),
454                     p2.startTagCloseDeriv());
455             })
456         };
457     });
458     createAfter = memoize2arg("after", function (p1, p2) {
459         if (p1 === notAllowed || p2 === notAllowed) { return notAllowed; }
460     }, function (p1, p2) {
461         return {
462             type: "after",
463             p1: p1,
464             p2: p2,
465             nullable: false,
466             textDeriv: function (context, text) {
467                 return createAfter(p1.textDeriv(context, text), p2);
468             },
469             startTagOpenDeriv: memoizeNode(function (node) {
470                 return applyAfter(function (p) { return createAfter(p, p2); },
471                     p1.startTagOpenDeriv(node));
472             }),
473             attDeriv: function (context, attribute) {
474                 return createAfter(p1.attDeriv(context, attribute), p2);
475             },
476             startTagCloseDeriv: memoize0arg(function () {
477                 return createAfter(p1.startTagCloseDeriv(), p2);
478             }),
479             endTagDeriv: memoize0arg(function () {
480                 return (p1.nullable) ? p2 : notAllowed;
481             })
482         };
483     });
484     createOneOrMore = memoize1arg("oneormore", function (p) {
485         if (p === notAllowed) { return notAllowed; }
486         return {
487             type: "oneOrMore",
488             p: p,
489             nullable: p.nullable,
490             textDeriv: function (context, text) {
491                 return createGroup(p.textDeriv(context, text),
492                             createChoice(this, empty));
493             },
494             startTagOpenDeriv: function (node) {
495                 var oneOrMore = this;
496                 return applyAfter(function (pf) {
497                     return createGroup(pf, createChoice(oneOrMore, empty));
498                 }, p.startTagOpenDeriv(node));
499             },
500             attDeriv: function (context, attribute) {
501                 var oneOrMore = this;
502                 return createGroup(p.attDeriv(context, attribute),
503                     createChoice(oneOrMore, empty));
504             },
505             startTagCloseDeriv: memoize0arg(function () {
506                 return createOneOrMore(p.startTagCloseDeriv());
507             })
508         };
509     });
510     function createElement(nc, p) {
511         return {
512             type: "element",
513             nc: nc,
514             nullable: false,
515             textDeriv: function () { return notAllowed; },
516             startTagOpenDeriv: function (node) {
517                 if (nc.contains(node)) {
518                     return createAfter(p, empty);
519                 }
520                 return notAllowed;
521             },
522             attDeriv: function () { return notAllowed; },
523             startTagCloseDeriv: function () { return this; }
524         };
525     }
526     function valueMatch(context, pattern, text) {
527         return (pattern.nullable && /^\s+$/.test(text)) ||
528             pattern.textDeriv(context, text).nullable;
529     }
530     createAttribute = memoize2arg("attribute", undefined, function (nc, p) {
531         return {
532             type: "attribute",
533             nullable: false,
534             hash: undefined,
535             nc: nc,
536             p: p,
537             p1: undefined,
538             p2: undefined,
539             textDeriv: undefined,
540             startTagOpenDeriv: undefined,
541             attDeriv: function (context, attribute) {
542                 if (nc.contains(attribute) && valueMatch(context, p,
543                         attribute.nodeValue)) {
544                     return empty;
545                 }
546                 return notAllowed;
547             },
548             startTagCloseDeriv: function () { return notAllowed; },
549             endTagDeriv: undefined
550         };
551     });
552     function createList() {
553         return {
554             type: "list",
555             nullable: false,
556             hash: "list",
557             textDeriv: function () {
558                 return empty;
559             }
560         };
561     }
562 /*jslint unparam: true*/
563     createValue = memoize1arg("value", function (value) {
564         return {
565             type: "value",
566             nullable: false,
567             value: value,
568             textDeriv: function (context, text) {
569                 return (text === value) ? empty : notAllowed;
570             },
571             attDeriv: function () { return notAllowed; },
572             startTagCloseDeriv: function () { return this; }
573         };
574     });
575 /*jslint unparam: false*/
576     createData = memoize1arg("data", function (type) {
577         return {
578             type: "data",
579             nullable: false,
580             dataType: type,
581             textDeriv: function () { return empty; },
582             attDeriv: function () { return notAllowed; },
583             startTagCloseDeriv: function () { return this; }
584         };
585     });
586     applyAfter = function applyAfter(f, p) {
587         var result;
588         if (p.type === "after") {
589             result = createAfter(p.p1, f(p.p2));
590         } else if (p.type === "choice") {
591             result = createChoice(applyAfter(f, p.p1), applyAfter(f, p.p2));
592         } else {
593             result = p;
594         }
595         return result;
596     };
597     function attsDeriv(context, pattern, attributes, position) {
598         if (pattern === notAllowed) {
599             return notAllowed;
600         }
601         if (position >= attributes.length) {
602             return pattern;
603         }
604         if (position === 0) {
605             // TODO: loop over attributes to update namespace mapping
606             position = 0;
607         }
608         var a = attributes.item(position);
609         while (a.namespaceURI === xmlnsns) { // always ok
610             position += 1;
611             if (position >= attributes.length) {
612                 return pattern;
613             }
614             a = attributes.item(position);
615         }
616         a = attsDeriv(context, pattern.attDeriv(context,
617                 attributes.item(position)), attributes, position + 1);
618         return a;
619     }
620     function childrenDeriv(context, pattern, walker) {
621         var element = walker.currentNode,
622             childNode = walker.firstChild(),
623             childNodes = [],
624             i,
625             p;
626         // simple incomplete implementation: only use non-empty text nodes
627         while (childNode) {
628             if (childNode.nodeType === Node.ELEMENT_NODE) {
629                 childNodes.push(childNode);
630             } else if (childNode.nodeType === Node.TEXT_NODE &&
631                     !/^\s*$/.test(childNode.nodeValue)) {
632                 childNodes.push(childNode.nodeValue);
633             }
634             childNode = walker.nextSibling();
635         }
636         // if there is no nodes at all, add an empty text node
637         if (childNodes.length === 0) {
638             childNodes = [""];
639         }
640         p = pattern;
641         for (i = 0; p !== notAllowed && i < childNodes.length; i += 1) {
642             childNode = childNodes[i];
643             if (typeof childNode === "string") {
644                 if (/^\s*$/.test(childNode)) {
645                     p = createChoice(p, p.textDeriv(context, childNode));
646                 } else {
647                     p = p.textDeriv(context, childNode);
648                 }
649             } else {
650                 walker.currentNode = childNode;
651                 p = childDeriv(context, p, walker);
652             }
653         }
654         walker.currentNode = element;
655         return p;
656     }
657     childDeriv = function childDeriv(context, pattern, walker) {
658         var childNode = walker.currentNode, p;
659         p = pattern.startTagOpenDeriv(childNode);
660         p = attsDeriv(context, p, childNode.attributes, 0);
661         p = p.startTagCloseDeriv();
662         p = childrenDeriv(context, p, walker);
663         p = p.endTagDeriv();
664         return p;
665     };
666     function addNames(name, ns, pattern) {
667         if (pattern.e[0].a) {
668             name.push(pattern.e[0].text);
669             ns.push(pattern.e[0].a.ns);
670         } else {
671             addNames(name, ns, pattern.e[0]);
672         }
673         if (pattern.e[1].a) {
674             name.push(pattern.e[1].text);
675             ns.push(pattern.e[1].a.ns);
676         } else {
677             addNames(name, ns, pattern.e[1]);
678         }
679     }
680     createNameClass = function createNameClass(pattern) {
681         var name, ns, hash, i, result;
682         if (pattern.name === "name") {
683             name = pattern.text;
684             ns = pattern.a.ns;
685             result = {
686                 name: name,
687                 ns: ns,
688                 hash: "{" + ns + "}" + name,
689                 contains: function (node) {
690                     return node.namespaceURI === ns && node.localName === name;
691                 }
692             };
693         } else if (pattern.name === "choice") {
694             name = [];
695             ns = [];
696             addNames(name, ns, pattern);
697             hash = "";
698             for (i = 0; i < name.length; i += 1) {
699                 hash += "{" + ns[i] + "}" + name[i] + ",";
700             }
701             result = {
702                 hash: hash,
703                 contains: function (node) {
704                     var j;
705                     for (j = 0; j < name.length; j += 1) {
706                         if (name[j] === node.localName &&
707                                 ns[j] === node.namespaceURI) {
708                             return true;
709                         }
710                     }
711                     return false;
712                 }
713             };
714         } else {
715             result = {
716                 hash: "anyName",
717                 contains: function () { return true; }
718             };
719         }
720         return result;
721     };
722     function resolveElement(pattern, elements) {
723         var element, p, i, hash;
724         // create an empty object in the store to enable circular
725         // dependencies
726         hash = "element" + pattern.id.toString();
727         p = elements[pattern.id] = { hash: hash };
728         element = createElement(createNameClass(pattern.e[0]),
729             makePattern(pattern.e[1], elements));
730         // copy the properties of the new object into the predefined one
731         for (i in element) {
732             if (element.hasOwnProperty(i)) {
733                 p[i] = element[i];
734             }
735         }
736         return p;
737     }
738     makePattern = function makePattern(pattern, elements) {
739         var p, i;
740         if (pattern.name === "elementref") {
741             p = pattern.id || 0;
742             pattern = elements[p];
743             if (pattern.name !== undefined) {
744                 return resolveElement(pattern, elements);
745             }
746             return pattern;
747         }
748         switch (pattern.name) {
749         case 'empty':
750             return empty;
751         case 'notAllowed':
752             return notAllowed;
753         case 'text':
754             return text;
755         case 'choice':
756             return createChoice(makePattern(pattern.e[0], elements),
757                  makePattern(pattern.e[1], elements));
758         case 'interleave':
759             p = makePattern(pattern.e[0], elements);
760             for (i = 1; i < pattern.e.length; i += 1) {
761                 p = createInterleave(p, makePattern(pattern.e[i],
762                         elements));
763             }
764             return p;
765         case 'group':
766             return createGroup(makePattern(pattern.e[0], elements),
767                     makePattern(pattern.e[1], elements));
768         case 'oneOrMore':
769             return createOneOrMore(makePattern(pattern.e[0], elements));
770         case 'attribute':
771             return createAttribute(createNameClass(pattern.e[0]),
772                 makePattern(pattern.e[1], elements));
773         case 'value':
774             return createValue(pattern.text);
775         case 'data':
776             p = pattern.a && pattern.a.type;
777             if (p === undefined) {
778                 p = "";
779             }
780             return createData(p);
781         case 'list':
782             return createList();
783         }
784         throw "No support for " + pattern.name;
785     };
786     this.makePattern = function (pattern, elements) {
787         var copy = {}, i;
788         for (i in elements) {
789             if (elements.hasOwnProperty(i)) {
790                 copy[i] = elements[i];
791             }
792         }
793         i = makePattern(pattern, copy);
794         return i;
795     };
796     /**
797      * Validate the elements pointed to by the TreeWalker
798      * @param {!TreeWalker} walker
799      * @param {!function(Array.<string>):undefined} callback
800      * @return {undefined}
801      */
802     this.validate = function validate(walker, callback) {
803         var errors;
804         walker.currentNode = walker.root;
805         errors = childDeriv(null, rootPattern, walker);
806         if (!errors.nullable) {
807             runtime.log("Error in Relax NG validation: " + errors);
808             callback(["Error in Relax NG validation: " + errors]);
809         } else {
810             callback(null);
811         }
812     };
813     this.init = function init(rootPattern1) {
814         rootPattern = rootPattern1;
815     };
816 };
817