345 lines
16 KiB
Swift
345 lines
16 KiB
Swift
extension PureXML.Schema {
|
|
/// Validates a document against a RELAX NG grammar by Brzozowski-style
|
|
/// derivatives (James Clark's "An algorithm for RELAX NG validation"). The
|
|
/// pattern is repeatedly derived with respect to each event of the instance;
|
|
/// the document is valid when the residual pattern is nullable.
|
|
///
|
|
/// Bound: there is no derivative memoization (patterns are not hashable by
|
|
/// design). The simplifying constructors (`choice`/`group`/`interleave`
|
|
/// short-circuit on `notAllowed` and `empty`) keep the residual small for
|
|
/// real-world grammars, but an adversarial grammar of deeply nested
|
|
/// choices can still grow it; treat untrusted schemas accordingly.
|
|
struct RelaxNGEngine {
|
|
let defines: [String: PureXML.Schema.Pattern]
|
|
|
|
/// Whether `root` matches `start`.
|
|
func matches(start: PureXML.Schema.Pattern, root: PureXML.Model.Node) -> Bool {
|
|
nullable(childDeriv(start, root, env: Self.rootEnvironment))
|
|
}
|
|
|
|
/// The namespace bindings every instance starts with.
|
|
static let rootEnvironment: [String: String] = ["xml": "http://www.w3.org/XML/1998/namespace"]
|
|
|
|
/// `env` extended with the element's own xmlns declarations.
|
|
static func extendedEnvironment(_ env: [String: String], with element: PureXML.Model.Element) -> [String: String] {
|
|
var extended = env
|
|
for attribute in element.attributes where isNamespaceDeclaration(attribute) {
|
|
let prefix = attribute.name.prefix == "xmlns" ? attribute.name.localName : ""
|
|
extended[prefix] = attribute.value
|
|
}
|
|
return extended
|
|
}
|
|
|
|
/// Resolves an instance-side QName text against the in-scope bindings:
|
|
/// a prefix must be bound; an unprefixed name takes the default
|
|
/// namespace (the xs:QName rules).
|
|
static func resolveQNameValue(_ raw: String, env: [String: String]) -> (namespace: String, localName: String)? {
|
|
let trimmed = raw.trimmingXMLWhitespace()
|
|
guard let colon = trimmed.firstIndex(of: ":") else {
|
|
return (env[""] ?? "", trimmed)
|
|
}
|
|
let prefix = String(trimmed[..<colon])
|
|
let local = String(trimmed[trimmed.index(after: colon)...])
|
|
guard let uri = env[prefix], !uri.isEmpty else { return nil }
|
|
return (uri, local)
|
|
}
|
|
|
|
// MARK: Simplifying constructors
|
|
|
|
func choice(_ lhs: PureXML.Schema.Pattern, _ rhs: PureXML.Schema.Pattern) -> PureXML.Schema.Pattern {
|
|
if case .notAllowed = lhs {
|
|
return rhs
|
|
}
|
|
if case .notAllowed = rhs {
|
|
return lhs
|
|
}
|
|
return .choice(lhs, rhs)
|
|
}
|
|
|
|
private func group(_ lhs: PureXML.Schema.Pattern, _ rhs: PureXML.Schema.Pattern) -> PureXML.Schema.Pattern {
|
|
if case .notAllowed = lhs {
|
|
return .notAllowed
|
|
}
|
|
if case .notAllowed = rhs {
|
|
return .notAllowed
|
|
}
|
|
if case .empty = lhs {
|
|
return rhs
|
|
}
|
|
if case .empty = rhs {
|
|
return lhs
|
|
}
|
|
return .group(lhs, rhs)
|
|
}
|
|
|
|
private func interleave(_ lhs: PureXML.Schema.Pattern, _ rhs: PureXML.Schema.Pattern) -> PureXML.Schema.Pattern {
|
|
if case .notAllowed = lhs {
|
|
return .notAllowed
|
|
}
|
|
if case .notAllowed = rhs {
|
|
return .notAllowed
|
|
}
|
|
if case .empty = lhs {
|
|
return rhs
|
|
}
|
|
if case .empty = rhs {
|
|
return lhs
|
|
}
|
|
return .interleave(lhs, rhs)
|
|
}
|
|
|
|
private func after(_ lhs: PureXML.Schema.Pattern, _ rhs: PureXML.Schema.Pattern) -> PureXML.Schema.Pattern {
|
|
if case .notAllowed = lhs {
|
|
return .notAllowed
|
|
}
|
|
if case .notAllowed = rhs {
|
|
return .notAllowed
|
|
}
|
|
return .after(lhs, rhs)
|
|
}
|
|
|
|
func resolve(_ name: String) -> PureXML.Schema.Pattern {
|
|
defines[name] ?? .notAllowed
|
|
}
|
|
|
|
// MARK: Nullability
|
|
|
|
func nullable(_ pattern: PureXML.Schema.Pattern, visiting: Set<String> = []) -> Bool {
|
|
switch pattern {
|
|
case .empty, .text: return true
|
|
case let .choice(lhs, rhs): return nullable(lhs, visiting: visiting) || nullable(rhs, visiting: visiting)
|
|
case let .group(lhs, rhs), let .interleave(lhs, rhs):
|
|
return nullable(lhs, visiting: visiting) && nullable(rhs, visiting: visiting)
|
|
case let .oneOrMore(inner), let .list(inner): return nullable(inner, visiting: visiting)
|
|
case let .ref(name):
|
|
guard !visiting.contains(name) else { return false }
|
|
return nullable(resolve(name), visiting: visiting.union([name]))
|
|
default:
|
|
return false
|
|
}
|
|
}
|
|
|
|
// MARK: Text and attribute derivatives
|
|
|
|
func textDeriv(_ pattern: PureXML.Schema.Pattern, _ string: String, env: [String: String] = rootEnvironment) -> PureXML.Schema.Pattern {
|
|
switch pattern {
|
|
case let .choice(lhs, rhs): return choice(textDeriv(lhs, string, env: env), textDeriv(rhs, string, env: env))
|
|
case let .interleave(lhs, rhs):
|
|
return choice(interleave(textDeriv(lhs, string, env: env), rhs), interleave(lhs, textDeriv(rhs, string, env: env)))
|
|
case let .group(lhs, rhs):
|
|
let derived = group(textDeriv(lhs, string, env: env), rhs)
|
|
return nullable(lhs) ? choice(derived, textDeriv(rhs, string, env: env)) : derived
|
|
case let .after(lhs, rhs): return after(textDeriv(lhs, string, env: env), rhs)
|
|
case let .oneOrMore(inner):
|
|
return group(textDeriv(inner, string, env: env), choice(.oneOrMore(inner), .empty))
|
|
case .text: return .text
|
|
case let .ref(name): return textDeriv(resolve(name), string, env: env)
|
|
default: return valueDeriv(pattern, string, env: env)
|
|
}
|
|
}
|
|
|
|
private func valueDeriv(_ pattern: PureXML.Schema.Pattern, _ string: String, env: [String: String]) -> PureXML.Schema.Pattern {
|
|
switch pattern {
|
|
case let .value(type, literal):
|
|
type.valueMatches(string, literal: literal) ? .empty : .notAllowed
|
|
case let .data(type): type.validate(string) == nil ? .empty : .notAllowed
|
|
case let .dataExcept(type, except):
|
|
type.validate(string) == nil && !nullable(textDeriv(except, string, env: env)) ? .empty : .notAllowed
|
|
case let .valueQName(namespace, localName):
|
|
Self.resolveQNameValue(string, env: env).map { $0 == (namespace, localName) } == true ? .empty : .notAllowed
|
|
case let .list(inner): listMatches(inner, string, env: env) ? .empty : .notAllowed
|
|
default: .notAllowed
|
|
}
|
|
}
|
|
|
|
private func listMatches(_ pattern: PureXML.Schema.Pattern, _ string: String, env _: [String: String]) -> Bool {
|
|
var residual = pattern
|
|
for token in string.split(whereSeparator: \.isWhitespace) {
|
|
residual = textDeriv(residual, String(token))
|
|
}
|
|
return nullable(residual)
|
|
}
|
|
|
|
func attributeDeriv(_ pattern: PureXML.Schema.Pattern, _ attribute: PureXML.Model.Attribute, env: [String: String] = rootEnvironment) -> PureXML.Schema.Pattern {
|
|
switch pattern {
|
|
case let .choice(lhs, rhs): return choice(attributeDeriv(lhs, attribute, env: env), attributeDeriv(rhs, attribute, env: env))
|
|
case let .group(lhs, rhs):
|
|
return choice(group(attributeDeriv(lhs, attribute, env: env), rhs), group(lhs, attributeDeriv(rhs, attribute, env: env)))
|
|
case let .interleave(lhs, rhs):
|
|
return choice(interleave(attributeDeriv(lhs, attribute, env: env), rhs), interleave(lhs, attributeDeriv(rhs, attribute, env: env)))
|
|
case let .oneOrMore(inner):
|
|
return group(attributeDeriv(inner, attribute, env: env), choice(.oneOrMore(inner), .empty))
|
|
case let .after(lhs, rhs): return after(attributeDeriv(lhs, attribute, env: env), rhs)
|
|
case let .attribute(nameClass, content):
|
|
guard nameClass.contains(attribute.name), valueMatches(content, attribute.value, env: env) else { return .notAllowed }
|
|
return .empty
|
|
case let .ref(name): return attributeDeriv(resolve(name), attribute, env: env)
|
|
default: return .notAllowed
|
|
}
|
|
}
|
|
|
|
private func valueMatches(_ content: PureXML.Schema.Pattern, _ value: String, env: [String: String]) -> Bool {
|
|
if nullable(textDeriv(content, value, env: env)) {
|
|
return true
|
|
}
|
|
// A whitespace-only attribute value also matches a pattern that
|
|
// matches the empty sequence, the same leniency element content
|
|
// gets for ignorable whitespace.
|
|
return value.unicodeScalars.allSatisfy(PureXML.Parsing.XMLCharacter.isWhitespace) && nullable(content)
|
|
}
|
|
|
|
private func oneOrMoreP(_ inner: PureXML.Schema.Pattern) -> PureXML.Schema.Pattern {
|
|
if case .notAllowed = inner {
|
|
return .notAllowed
|
|
}
|
|
return .oneOrMore(inner)
|
|
}
|
|
}
|
|
}
|
|
|
|
extension PureXML.Schema.RelaxNGEngine {
|
|
// MARK: Element derivatives
|
|
|
|
func childDeriv(_ pattern: PureXML.Schema.Pattern, _ node: PureXML.Model.Node, env: [String: String] = rootEnvironment) -> PureXML.Schema.Pattern {
|
|
switch node {
|
|
case let .text(string), let .cdata(string):
|
|
textDeriv(pattern, string, env: env)
|
|
case let .element(element):
|
|
processElement(pattern, element, env: env)
|
|
default:
|
|
pattern
|
|
}
|
|
}
|
|
|
|
private func processElement(_ pattern: PureXML.Schema.Pattern, _ element: PureXML.Model.Element, env: [String: String]) -> PureXML.Schema.Pattern {
|
|
let extended = Self.extendedEnvironment(env, with: element)
|
|
let opened = startTagOpenDeriv(pattern, element.name)
|
|
let attributed = element.attributes
|
|
.filter { !Self.isNamespaceDeclaration($0) }
|
|
.reduce(opened) { attributeDeriv($0, $1, env: extended) }
|
|
let closed = startTagCloseDeriv(attributed)
|
|
let withChildren = childrenDeriv(closed, element.children, env: extended)
|
|
return endTagDeriv(withChildren)
|
|
}
|
|
|
|
func startTagOpenDeriv(_ pattern: PureXML.Schema.Pattern, _ name: PureXML.Model.QualifiedName) -> PureXML.Schema.Pattern {
|
|
switch pattern {
|
|
case let .choice(lhs, rhs):
|
|
return choice(startTagOpenDeriv(lhs, name), startTagOpenDeriv(rhs, name))
|
|
case let .element(nameClass, content):
|
|
return nameClass.contains(name) ? after(content, .empty) : .notAllowed
|
|
case let .interleave(lhs, rhs):
|
|
return choice(
|
|
applyAfter({ interleave($0, rhs) }, startTagOpenDeriv(lhs, name)),
|
|
applyAfter({ interleave(lhs, $0) }, startTagOpenDeriv(rhs, name)),
|
|
)
|
|
case let .group(lhs, rhs):
|
|
let derived = applyAfter({ group($0, rhs) }, startTagOpenDeriv(lhs, name))
|
|
return nullable(lhs) ? choice(derived, startTagOpenDeriv(rhs, name)) : derived
|
|
case let .oneOrMore(inner):
|
|
return applyAfter({ group($0, choice(oneOrMoreP(inner), .empty)) }, startTagOpenDeriv(inner, name))
|
|
case let .after(lhs, rhs):
|
|
return applyAfter({ after($0, rhs) }, startTagOpenDeriv(lhs, name))
|
|
case let .ref(reference):
|
|
return startTagOpenDeriv(resolve(reference), name)
|
|
default:
|
|
return .notAllowed
|
|
}
|
|
}
|
|
|
|
private func applyAfter(_ transform: (PureXML.Schema.Pattern) -> PureXML.Schema.Pattern, _ pattern: PureXML.Schema.Pattern) -> PureXML.Schema.Pattern {
|
|
switch pattern {
|
|
case let .after(lhs, rhs): after(lhs, transform(rhs))
|
|
case let .choice(lhs, rhs): choice(applyAfter(transform, lhs), applyAfter(transform, rhs))
|
|
default: .notAllowed
|
|
}
|
|
}
|
|
|
|
func startTagCloseDeriv(_ pattern: PureXML.Schema.Pattern) -> PureXML.Schema.Pattern {
|
|
switch pattern {
|
|
case let .choice(lhs, rhs): choice(startTagCloseDeriv(lhs), startTagCloseDeriv(rhs))
|
|
case let .group(lhs, rhs): group(startTagCloseDeriv(lhs), startTagCloseDeriv(rhs))
|
|
case let .interleave(lhs, rhs): interleave(startTagCloseDeriv(lhs), startTagCloseDeriv(rhs))
|
|
case let .oneOrMore(inner): oneOrMoreP(startTagCloseDeriv(inner))
|
|
case let .after(lhs, rhs): after(startTagCloseDeriv(lhs), rhs)
|
|
case .attribute: .notAllowed
|
|
case let .ref(reference): startTagCloseDeriv(resolve(reference))
|
|
default: pattern
|
|
}
|
|
}
|
|
|
|
private func childrenDeriv(_ pattern: PureXML.Schema.Pattern, _ children: [PureXML.Model.Node], env: [String: String]) -> PureXML.Schema.Pattern {
|
|
let coalesced = Self.coalesceText(children)
|
|
// Clark's algorithm treats an empty element as optional empty text, so
|
|
// a data/value pattern whose lexical space admits "" matches <e/>.
|
|
if coalesced.isEmpty {
|
|
return choice(pattern, textDeriv(pattern, "", env: env))
|
|
}
|
|
if coalesced.count == 1, case let .text(string) = coalesced[0] {
|
|
let derived = textDeriv(pattern, string, env: env)
|
|
return Self.isWhitespace(string) ? choice(pattern, derived) : derived
|
|
}
|
|
return coalesced.reduce(pattern) { accumulated, node in
|
|
Self.isWhitespaceText(node) ? accumulated : childDeriv(accumulated, node, env: env)
|
|
}
|
|
}
|
|
|
|
func endTagDeriv(_ pattern: PureXML.Schema.Pattern) -> PureXML.Schema.Pattern {
|
|
switch pattern {
|
|
case let .choice(lhs, rhs): choice(endTagDeriv(lhs), endTagDeriv(rhs))
|
|
case let .after(lhs, rhs): nullable(lhs) ? rhs : .notAllowed
|
|
case let .ref(reference): endTagDeriv(resolve(reference))
|
|
default: .notAllowed
|
|
}
|
|
}
|
|
|
|
// MARK: Helpers
|
|
|
|
/// Merges adjacent text and CDATA nodes into single text nodes.
|
|
static func coalesceText(_ children: [PureXML.Model.Node]) -> [PureXML.Model.Node] {
|
|
var result: [PureXML.Model.Node] = []
|
|
var run = ""
|
|
for child in children {
|
|
switch child {
|
|
case let .text(value), let .cdata(value):
|
|
run += value
|
|
case .comment, .processingInstruction:
|
|
continue
|
|
default:
|
|
if !run.isEmpty {
|
|
result.append(.text(run))
|
|
run = ""
|
|
}
|
|
result.append(child)
|
|
}
|
|
}
|
|
if !run.isEmpty {
|
|
result.append(.text(run))
|
|
}
|
|
return result
|
|
}
|
|
|
|
static func isWhitespace(_ string: String) -> Bool {
|
|
string.allSatisfy(\.isWhitespace)
|
|
}
|
|
|
|
static func isWhitespaceText(_ node: PureXML.Model.Node) -> Bool {
|
|
if case let .text(value) = node {
|
|
return isWhitespace(value)
|
|
}
|
|
return false
|
|
}
|
|
|
|
static func isNamespaceDeclaration(_ attribute: PureXML.Model.Attribute) -> Bool {
|
|
attribute.name.prefix == "xmlns" || (attribute.name.prefix == nil && attribute.name.localName == "xmlns")
|
|
}
|
|
|
|
static func elementNameCounts(_ children: [PureXML.Model.Node]) -> [String: Int] {
|
|
var counts: [String: Int] = [:]
|
|
for case let .element(element) in children {
|
|
counts[element.name.description, default: 0] += 1
|
|
}
|
|
return counts
|
|
}
|
|
}
|