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  * @namespace
 29  */
 30 xmldom.RNG = {};
 31 /**
 32  * @typedef {!{e:!Array.<xmldom.RNG.Name>,name:string}}
 33  */
 34 xmldom.RNG.Name;
 35 /**
 36  * @typedef {!{ns:string, name:string}}
 37  */
 38 xmldom.RNG.Attr;
 39 /**
 40  * @typedef {!{
 41  *     id:    number,
 42  *     e:     (undefined|?|!Array.<xmldom.RNG.Element>),
 43  *     name:  string,
 44  *     names: (undefined|!Array.<string>),
 45  *     a:     (undefined|?|!xmldom.RNG.Attr),
 46  *     text:  string
 47  * }}
 48  */
 49 xmldom.RNG.Element;
 50 
 51 /**
 52  * RelaxNG can check a DOM tree against a Relax NG schema
 53  * The RelaxNG implementation is currently not complete. Relax NG should not
 54  * report errors on valid DOM trees, but it will not check all constraints that
 55  * a Relax NG file can define. The current implementation does not load external
 56  * parts of a Relax NG file.
 57  * The main purpose of this Relax NG engine is to validate runtime ODF
 58  * documents. The DOM tree is traversed via a TreeWalker. A custom TreeWalker
 59  * implementation can hide parts of a DOM tree. This is useful in WebODF, where
 60  * special elements and attributes in the runtime DOM tree.
 61  * @constructor
 62  */
 63 xmldom.RelaxNGParser = function RelaxNGParser() {
 64     "use strict";
 65     var self = this,
 66         rngns = "http://relaxng.org/ns/structure/1.0",
 67         xmlnsns = "http://www.w3.org/2000/xmlns/",
 68         start,
 69         /**@type{!Object.<string,string>}*/
 70         nsmap = { "http://www.w3.org/XML/1998/namespace": "xml" },
 71         /**@type{function(...):?xmldom.RNG.Element}*/
 72         parse;
 73 
 74     /**
 75      * @constructor
 76      * @param {!string} error
 77      * @param {Node=} context
 78      */
 79     function RelaxNGParseError(error, context) {
 80         /**
 81          * return {!string}
 82          */
 83         this.message = function () {
 84             if (context) {
 85                 error += (context.nodeType === 1) ? " Element " : " Node ";
 86                 error += context.nodeName;
 87                 if (context.nodeValue) {
 88                     error += " with value '" + context.nodeValue + "'";
 89                 }
 90                 error += ".";
 91             }
 92             return error;
 93         };
 94     }
 95     /**
 96      * @param {!xmldom.RNG.Name} e
 97      * @return {!xmldom.RNG.Name}
 98      */
 99     function splitToDuos(e) {
100         if (e.e.length <= 2) {
101             return e;
102         }
103         var o = { name: e.name, e: e.e.slice(0, 2) };
104         return splitToDuos({
105             name: e.name,
106             e: [ o ].concat(e.e.slice(2))
107         });
108     }
109     /**
110      * @param {!string} name
111      * @return {!Array.<string>}
112      */
113     function splitQName(name) {
114         var r = name.split(":", 2),
115             prefix = "",
116             /**@type{string}*/
117             i;
118         if (r.length === 1) {
119             r = ["", r[0]];
120         } else {
121             prefix = r[0];
122         }
123         for (i in nsmap) {
124             if (nsmap[i] === prefix) {
125                 r[0] = i;
126             }
127         }
128         return r;
129     }
130 
131     /**
132      * @param {!{names:!Array.<string>}} def
133      * @return {undefined}
134      */
135     function splitQNames(def) {
136         var i, l = (def.names) ? def.names.length : 0, name,
137             localnames = [],
138             namespaces = [];
139         for (i = 0; i < l; i += 1) {
140             name = splitQName(def.names[i]);
141             namespaces[i] = name[0];
142             localnames[i] = name[1];
143         }
144         def.localnames = localnames;
145         def.namespaces = namespaces;
146     }
147 
148     /**
149      * @param {!string} str
150      * @return {!string}
151      */
152     function trim(str) {
153         str = str.replace(/^\s\s*/, '');
154         var ws = /\s/,
155             i = str.length - 1;
156         while (ws.test(str.charAt(i))) {
157             i -= 1;
158         }
159         return str.slice(0, i + 1);
160     }
161 
162     /**
163      * @param {?NamedNodeMap} atts
164      * @param {!string} name
165      * @param {!Array.<string>} names
166      * @return {!Object.<string,string>}
167      */
168     function copyAttributes(atts, name, names) {
169         var a = {}, i, att;
170         for (i = 0; atts && i < atts.length; i += 1) {
171             att = /**@type{!Attr}*/(atts.item(i));
172             if (!att.namespaceURI) {
173                 if (att.localName === "name" &&
174                         (name === "element" || name === "attribute")) {
175                     names.push(att.value);
176                 }
177                 if (att.localName === "name" || att.localName === "combine" ||
178                         att.localName === "type") {
179                     att.value = trim(att.value);
180                 }
181                 a[att.localName] = att.value;
182             } else if (att.namespaceURI === xmlnsns) {
183                 nsmap[att.value] = att.localName;
184             }
185         }
186         return a;
187     }
188 
189     /**
190      * @param {?Node} c
191      * @param {!Array.<*>} e
192      * @param {!Array.<*>} elements
193      * @param {!Array.<string>} names
194      * @return {string}
195      */
196     function parseChildren(c, e, elements, names) {
197         var text = "", ce;
198         while (c) {
199             if (c.nodeType === Node.ELEMENT_NODE && c.namespaceURI === rngns) {
200                 ce = parse(/**@type{!Element}*/(c), elements, e);
201                 if (ce) {
202                     if (ce.name === "name") {
203                         names.push(nsmap[ce.a.ns] + ":" + ce.text);
204                         e.push(ce);
205                     } else if (ce.name === "choice" && ce.names &&
206                             ce.names.length) {
207                         names = names.concat(ce.names);
208                         delete ce.names;
209                         e.push(ce);
210                     } else {
211                         e.push(ce);
212                     }
213                 }
214             } else if (c.nodeType === Node.TEXT_NODE) {
215                 text += c.nodeValue;
216             }
217             c = c.nextSibling;
218         }
219         return text;
220     }
221 
222     /**
223      * @param {*} combine
224      * @param {string} name
225      * @param {!xmldom.RNG.Element} e
226      * @param {undefined|!Array.<!xmldom.RNG.Element>} siblings
227      * @return {?xmldom.RNG.Element}
228      */
229     function combineDefines(combine, name, e, siblings) {
230         // combineDefines is called often enough that there can only be one
231         // other element with the same name
232         var i, ce;
233         for (i = 0; siblings && i < siblings.length; i += 1) {
234             ce = siblings[i];
235             if (ce.name === "define" && ce.a && ce.a.name === name) {
236                 ce.e = [ { name: combine, e: ce.e.concat(e) } ];
237                 return ce;
238             }
239         }
240         return null;
241     }
242 
243     /**
244      * @param {!Element} element
245      * @param {!Array.<*>} elements
246      * @param {!Array.<*>|undefined} siblings
247      * @return {?}
248      */
249     parse = function parse(element, elements, siblings) {
250         // parse all elements from the Relax NG namespace into JavaScript
251         // objects
252         var e = [],
253             /**@type{Object}*/
254             a,
255             ce,
256             i,
257             text,
258             name = element.localName,
259             names = [];
260         a = copyAttributes(element.attributes, name, names);
261         a.combine = a.combine || undefined;
262         text = parseChildren(element.firstChild, e, elements, names);
263 
264         // 4.2 strip leading and trailing whitespace
265         if (name !== "value" && name !== "param") {
266             text = /^\s*([\s\S]*\S)?\s*$/.exec(text)[1];
267         }
268         // 4.3 datatypeLibrary attribute
269         // 4.4 type attribute of value element
270         if (name === "value" && a.type === undefined) {
271             a.type = "token";
272             a.datatypeLibrary = "";
273         }
274         // 4.5 href attribute
275         // 4.6 externalRef element
276         // 4.7 include element
277         // 4.8 name attribute of element and attribute elements
278         if ((name === "attribute" || name === "element") &&
279                 a.name !== undefined) {
280             i = splitQName(a.name);
281             e = [{name: "name", text: i[1], a: {ns: i[0]}}].concat(e);
282             delete a.name;
283         }
284         // 4.9 ns attribute
285         if (name === "name" || name === "nsName" || name === "value") {
286             if (a.ns === undefined) {
287                 a.ns = ""; // TODO
288             }
289         } else {
290             delete a.ns;
291         }
292         // 4.10 QNames
293         if (name === "name") {
294             i = splitQName(text);
295             a.ns = i[0];
296             text = i[1];
297         }
298         // 4.11 div element
299         // 4.12 Number of child elements
300         if (e.length > 1 && (name === "define" || name === "oneOrMore" ||
301                 name === "zeroOrMore" || name === "optional" ||
302                 name === "list" || name === "mixed")) {
303             e = [{name: "group", e: splitToDuos({name: "group", e: e}).e}];
304         }
305         if (e.length > 2 && name === "element") {
306             e = [e[0]].concat({
307                 name: "group",
308                 e: splitToDuos({
309                     name: "group",
310                     e: e.slice(1)
311                 }).e
312             });
313         }
314         if (e.length === 1 && name === "attribute") {
315             e.push({name: "text", text: text});
316         }
317         // if node has only one child, replace node with child
318         if (e.length === 1 && (name === "choice" || name === "group" ||
319                 name === "interleave")) {
320             name = e[0].name;
321             names = e[0].names;
322             a = e[0].a;
323             text = e[0].text;
324             e = e[0].e;
325         } else if (e.length > 2 && (name === "choice" || name === "group" ||
326                 name === "interleave")) {
327             e = splitToDuos({name: name, e: e}).e;
328         }
329         // 4.13 mixed element
330         if (name === "mixed") {
331             name = "interleave";
332             e = [ e[0], { name: "text" } ];
333         }
334         // 4.14 optional element
335         if (name === "optional") {
336             name = "choice";
337             e = [ e[0], { name: "empty" } ];
338         }
339         // 4.15 zeroOrMore element
340         if (name === "zeroOrMore") {
341             name = "choice";
342             e = [ {name: "oneOrMore", e: [ e[0] ] }, { name: "empty" } ];
343         }
344         // 4.17 combine attribute
345         if (name === "define" && a.combine) {
346             ce = combineDefines(a.combine, a.name, e, siblings);
347             if (ce) {
348                 return null;
349             }
350         }
351 
352         // create the definition
353         ce = { name: name };
354         if (e && e.length > 0) { ce.e = e; }
355         for (i in a) {
356             if (a.hasOwnProperty(i)) {
357                 ce.a = a;
358                 break;
359             }
360         }
361         if (text !== undefined) { ce.text = text; }
362         if (names && names.length > 0) { ce.names = names; }
363 
364         // part one of 4.19
365         if (name === "element") {
366             ce.id = elements.length;
367             elements.push(ce);
368             ce = { name: "elementref", id: ce.id };
369         }
370         return ce;
371     };
372 
373     function resolveDefines(def, defines) {
374         var i = 0, e, defs, end, name = def.name;
375         while (def.e && i < def.e.length) {
376             e = def.e[i];
377             if (e.name === "ref") {
378                 defs = defines[e.a.name];
379                 if (!defs) {
380                     throw e.a.name + " was not defined.";
381                 }
382                 end = def.e.slice(i + 1);
383                 def.e = def.e.slice(0, i);
384                 def.e = def.e.concat(defs.e);
385                 def.e = def.e.concat(end);
386             } else {
387                 i += 1;
388                 resolveDefines(e, defines);
389             }
390         }
391         e = def.e;
392         // 4.20 notAllowed element
393         // 4.21 empty element
394         if (name === "choice") {
395             if (!e || !e[1] || e[1].name === "empty") {
396                 if (!e || !e[0] || e[0].name === "empty") {
397                     delete def.e;
398                     def.name = "empty";
399                 } else {
400                     e[1] = e[0];
401                     e[0] = { name: "empty" };
402                 }
403             }
404         }
405         if (name === "group" || name === "interleave") {
406             if (e[0].name === "empty") {
407                 if (e[1].name === "empty") {
408                     delete def.e;
409                     def.name = "empty";
410                 } else {
411                     name = def.name = e[1].name;
412                     def.names = e[1].names;
413                     e = def.e = e[1].e;
414                 }
415             } else if (e[1].name === "empty") {
416                 name = def.name = e[0].name;
417                 def.names = e[0].names;
418                 e = def.e = e[0].e;
419             }
420         }
421         if (name === "oneOrMore" && e[0].name === "empty") {
422             delete def.e;
423             def.name = "empty";
424         }
425         // for attributes we need to have the list of namespaces and
426         // localnames readily available, so we split up the qnames
427         if (name === "attribute") {
428             splitQNames(def);
429         }
430         // for interleaving validation, it is convenient to join all
431         // interleave elements that touch into one element
432         if (name === "interleave") {
433             // at this point the interleave will have two child elements,
434             // but the child interleave elements may have a different number
435             if (e[0].name === "interleave") {
436                 if (e[1].name === "interleave") {
437                     e = def.e = e[0].e.concat(e[1].e);
438                 } else {
439                     e = def.e = [e[1]].concat(e[0].e);
440                 }
441             } else if (e[1].name === "interleave") {
442                 e = def.e = [e[0]].concat(e[1].e);
443             }
444         }
445     }
446 
447     /**
448      * @param {!xmldom.RNG.Element} def
449      * @return {undefined}
450      */
451     function resolveElements(def, elements) {
452         var i = 0, e;
453         while (def.e && i < def.e.length) {
454             e = def.e[i];
455             if (e.name === "elementref") {
456                 e.id = e.id || 0;
457                 def.e[i] = elements[e.id];
458             } else if (e.name !== "element") {
459                 resolveElements(e, elements);
460             }
461             i += 1;
462         }
463     }
464 
465     /**
466      * @param {!Document} dom
467      * @param {!Function} callback
468      * @return {?Array.<!RelaxNGParseError>}
469      */
470     function main(dom, callback) {
471         var elements = [],
472             grammar = parse(dom && dom.documentElement, elements, undefined),
473             i,
474             e,
475             defines = {};
476 
477         for (i = 0; i < grammar.e.length; i += 1) {
478             e = grammar.e[i];
479             if (e.name === "define") {
480                 defines[e.a.name] = e;
481             } else if (e.name === "start") {
482                 start = e;
483             }
484         }
485         if (!start) {
486             return [new RelaxNGParseError(
487                 "No Relax NG start element was found."
488             )];
489         }
490         resolveDefines(start, defines);
491         for (i in defines) {
492             if (defines.hasOwnProperty(i)) {
493                 resolveDefines(defines[i], defines);
494             }
495         }
496         for (i = 0; i < elements.length; i += 1) {
497             resolveDefines(elements[i], defines);
498         }
499         if (callback) {
500             self.rootPattern = callback(start.e[0], elements);
501         }
502         resolveElements(start, elements);
503         for (i = 0; i < elements.length; i += 1) {
504             resolveElements(elements[i], elements);
505         }
506         self.start = start;
507         self.elements = elements;
508         self.nsmap = nsmap;
509         return null;
510     }
511     /**
512      * @param {!Document} dom
513      * @param {!Function} callback
514      * @return {?Array}
515      */
516     this.parseRelaxNGDOM = main;
517 };
518