← Back to branch summary

~ubuntu-branches/debian/wheezy/jing-trang/wheezy

« back to all changes in this revision

Viewing changes to doc/nameclass.html

  • Committer: Bazaar Package Importer
  • Author(s): Samuel Thibault
  • Date: 2009-09-01 15:53:03 UTC
  • Revision ID: james.westby@ubuntu.com-20090901155303-2kweef05h5v9j3ni
Tags: upstream-20090818
Import upstream version 20090818

Show diffs side-by-side

added added

removed removed

Lines of Context:
doc/nameclass.html
 
1
<html xmlns="http://www.w3.org/1999/xhtml">
 
2
<head>
 
3
<title>RELAX NG name class analysis</title>
 
4
</head>
 
5
 
 
6
<body>
 
7
 
 
8
<h1>Name class analysis</h1>
 
9
 
 
10
<p>A RELAX NG validator has to be able to determine whether two name
 
11
classes overlap (i.e. whether there is a name that belongs to both
 
12
name classes). This is needed for implementing sections 7.3
 
13
and 7.4 of the spec.</p>
 
14
 
 
15
<p>The basic idea is two test whether any of a representative set of
 
16
names is a member of both name classes.  The representative set of
 
17
names is chosen such that for any name <var>n</var> that occurs in one
 
18
or both name classes there is guaranteed to be at least one member
 
19
<var>r</var> of the representative set of names such that, for each of
 
20
the two name classes, <var>r</var> is a member of that name class if
 
21
and only <var>n</var> is also a member of that name class.  When
 
22
constructing a representative set of names for name classes involving
 
23
<code>anyName</code> or <code>nsName</code>, it is necessary to find a
 
24
namespace URI or a local name that is not mentioned in either name
 
25
class.  Instead of expending effort of finding such a namespace URI or
 
26
local name we instead use a string that is not legal as a namespace
 
27
URI or local name, and hence is guaranteed not to occur in either name
 
28
class.</p>
 
29
 
 
30
<p>Here's some <a href="http://www.haskell.org">Haskell</a> code that
 
31
implements this.  This uses datatypes from the <a
 
32
href="derivative.html">description</a> of derivative-based
 
33
validation.</p>
 
34
 
 
35
<pre>
 
36
overlap :: NameClass -> NameClass -> Bool
 
37
overlap nc1 nc2 =
 
38
  any (bothContain nc1 nc2) (representatives nc1 ++ representatives nc2)
 
39
 
 
40
bothContain :: NameClass -> NameClass -> QName -> Bool
 
41
bothContain nc1 nc2 qn = contains nc1 qn &amp;&amp; contains nc2 qn
 
42
 
 
43
representatives :: NameClass -> [QName]
 
44
 
 
45
illegalLocalName :: LocalName
 
46
illegalLocalName = ""
 
47
 
 
48
illegalUri :: Uri
 
49
illegalUri = "\x1"
 
50
 
 
51
representatives AnyName = [QName illegalUri illegalLocalName]
 
52
representatives (AnyNameExcept nc) =
 
53
  (QName illegalUri illegalLocalName) : (representatives nc)
 
54
representatives (NsName ns) = [QName ns illegalLocalName]
 
55
representatives (NsNameExcept ns nc) =
 
56
  (QName ns illegalLocalName) : (representatives nc)
 
57
representatives (Name ns ln) = [QName ns ln]
 
58
representatives (NameClassChoice nc1 nc2) =
 
59
  (representatives nc1) ++ (representatives nc2)
 
60
</pre>
 
61
 
 
62
<p>This approach can also be used to determine whether two name
 
63
classes are equivalent. Two name classes are equivalent if and only if
 
64
for each member of the representative set of names either both name
 
65
classes contain that representative name or neither name classe
 
66
contains it.</p>
 
67
 
 
68
<address>
 
69
<a href="mailto:jjc@jclark.com">James Clark</a>
 
70
</address>
 
71
</body>
 
72
</html>