X3D Regular Expressions (regexes)

Overview | Design Considerations and Whitespace | X3D Patterns | XML Patterns | References | Tools | X3D Resources | Contact

X3D Regular Expressions (regexes) are used to validate the correctness of string and numeric array values in an X3D scene.

XML | DOCTYPE | Bool | Color | ColorRGBA | Double | Float | Image | Int32 | Rotation | String | Time | Vec2 | Vec3 | Vec4 | Matrix3 | Matrix4 | bboxSize

🔖 Overview

Regular expressions (regexes) define string grammars that efficiently and rigorously define allowable character patterns making up a data value.

Regexes themselves are carefully defined sequences of characters that form a search pattern, mainly used for string pattern matching. For example, this technique allows detection of well-formed (or incorrect) MFVec3f arrays of three-tuple floats in an X3D scene.

X3D regexes are utilized judiciously when the base types of XML Schema are insufficient to capture the necessary richness of X3D content validation. Like all aspects of X3D Schema validation, regex validation is typically high performance and optional for end-user content display.

Note that not all regex languages are completely consistent, thus small (but fundamentally important) variations can occur. This work strictly follows regex syntax for XML Schema, which in turn permits consistent application using other variations of regex languages.

Interestingly, various data validation tools provide expressive power that is able to validate values to different degrees of fidelity.

1. DOCTYPE (DTD). DOCTYPE validation can only check that attribute values are strings. In some cases, a strict set of allowed enumeration values is defined (such as legal names for profiles and components).
2. XML Schema. Schema validation can check a large set of built-in data types. However, XML Schema validation is typically not able to fully check the correctness of array values. For example, an SFVec3f triplet (3-tuple) or an MFVec3f array can be checked to only contain floating-point values, but cannot be checked to have a multiple of three floats.
3. Regular expressions (regexes). Regular expressions can define any regular grammar, and thus have arbitrary expressive power. Although definitions may be tricky to define, character patterns of arbitrary complexity are theoretically achievable.
4. Regexes found on this page are included in the data-type definitions of each X3D XML Schema and X3D Unified Object Model (X3DUOM).

X3D Regular Expressions are an important part of X3D Quality Assurance (QA) to maximize the correctness of X3D scene content.

🔖 Design Considerations

General regex design considerations for X3D XML Schema include the following.

1. Regex constructs that are inconsistently implemented across major programming languages are avoided.
2. Careful design allows use of regexes that can be adapted for usage in XML, ClassicVRML, JavaScript/JSON, Java and other language environments.
3. For numeric types, leading sign characters (+ or -) are optionally present.
4. For numeric types, leading zeroes are not allowed, except for an optional leading zero preceding the decimal point when the significand is only fractional.
5. A required mantissa (integer or floating point) is represented as 0|[1-9][0-9]* (meaning either a solitary 0 or else a single non-zero digit followed by an optional number of additional digits).
6. The fractional part (to the right of the decimal point) can be represented as [0-9]*
7. The decimal separator is the symbol used to separate the integer part from the fractional part of a decimal number. The period character . is used for all such X3D values, and is escaped as \. when written in a regex.
8. Scientific notation starts with upper or lower-case E, is optionally positive or negative ([Ee][+-]?[0-9]+)? and can be appended to float expressions. For integer expressions, nonnegative scientific notation ([Ee][+]?[0-9]+)? can be appended.
9. Regex anchors are implicit and not included in XML Schema and X3DUOM regexes. Note that strict consumption of all value characters gets performed by these regexes. The anchor characters are necessary for regex101 engine unit testing so that otherwise-illegal values are not rejected (in MF tests).

Pattern components are used repeatedly in this design:

• Regex anchor matching:  ^ (line start) and $ (line end)
• Whitespace matching:
  • \s* (optional whitespace outside all values)
  • \s+ (required whitespace within tuple values)
  • \s*,?\s* (required whitespace with optional single comma, following each n-tuple value)
• Group repetition:             {n} repeats the preceding group n number of times.
• Boolean-value matching: true|false
• Hexadecimal matching:   0x[0-9a-fA-F]{1,16}
• Scientific notation:           ([Ee][+-]?[0-9]+)?
• Integer-value matching:   [+-]?(0|[1-9][0-9]*)([Ee][+-]?[0-9]+)?
• Float-value matching:      ([+-]?((0|[1-9][0-9]*)(\.[0-9]*)?|\.[0-9]+)([Ee][+-]?[0-9]+)?)
• Nonnegative float [0..1] matching:      ([+]?((0(\.[0-9]*)?|\.[0-9]+)|1(\.0*)?)([Ee][+-]?[0-9]+)?)

🔖 Disallowed values and Negative Lookahead

Some values may be numerically correct but not permitted.

• For example, numbers using scientific notation in the range [0..1] such as 3.0E-6 which nevertheless have a leading digit in range [2..9].

Negative Lookahead filters have potential to disqualify attributes that contain illegal values.

• W3C Recommendation for XML Schema (XSD): Regular Expressions does not support this construct, perhaps to avoid the possibility of computational denial-of-service (DoS) attacks.
• (?!((0|0\.0*|\.0+)\s+){3}) prohibits 0 0 0 and 0.0 0.0 0.0 (for example).
• (?!\s*,\s*,) prohibits multiple adjacent commas in intermediate whitespace, for example 0 0 0, ,0 0 0 is an illegal set of MFColor values.

This can be a useful construct since some specific values are disallowed in X3D. One such instance is that any zero vector is illegal as initial axis triplet of an SFRotation.

Alternate (stricter and more complex) regexes might someday get included in X3DUOM, but current regular expressions are powerful and satisfactory.

🔖 Whitespace Considerations

Intermediate commas are treated as whitespace, but are only allowed between each singleton value. For example, SFVec3f 3-tuple values within an MFVec3f array do not contain comma characters (but may be separated by commas and whitespace). Experience has shown that misplaced commas are a crucial indicator of malformed tuple values in large float arrays.

• Reference: X3D Extensible Markup Language (XML) encoding, Clause 5 Encoding of fields, 5.1.2 Description

For XML Schema to enable any inclusion of intermediate commas as whitespace characters in MultiField (MF) array types, native XML Schema datatypes typically cannot be used directly. In order to ensure strict validation, regex patterns must be used instead.

• Patterns to consume outer whitespace are prepended/appended for each type. Type regexes also allow multiple inner whitespace characters, optionally including a single comma between individual MF array values.
• Of note is that regex patterns only apply to base type xs:string, and so further application of strong XML Schema typing (i.e. base="xs:double" etc.) is not simultaneously possible when allowing commas as whitespace.
• Implementation of the \s regex pattern can vary in Perl Compatible Regular Expressions PCRE library (C, PHP, R, etc.) and some other implementations to accept a number of characters such as vertical whitespace \v including vertical tab cK, form feed \f, line feed, paragraph or line separator, and special Unicode characters. Thus an even stricter pattern ( \n\r\t)* might conceivably be used instead of pattern \s in order to strictly honor whitespace characters defined in ClassicVRML grammar.
• Similar to some programming languages, MFVec patterns typically allow a single trailing comma at the end of an array.

Potential whitespace variations in scene content are not an issue if X3D Canonicalization (C14N) has been applied to an X3D scene.

🔖 X3D Patterns

The following regex patterns are used in X3D XML Schema, X3D Unified Object Model (X3DUOM) and other validation tools.

TODO. Several pattern possibilities for urls/URNs are conceivable. Adding an MFString url regex pattern is likely useful.

X3D Java Scene Access Interface Library (X3DJSAIL) provides a set of unit tests in org.web3d.x3d.tests.FieldObjectTests to check these regexes against default and alternative values.

A scratch pad of various experimental regexes is found in X3dRegularExpressionTests.txt.

🔖 XML Patterns

The Extensible Markup Language (XML) provides several useful definitions and restrictions on string types.

• CDATA is Character Data, or unrestricted text. (XML Recommendation) (XML Schema)
• NMTOKEN is Name Token to match naming requirements for legal characters with no spaces. (XML Recommendation) (XML Schema)
• xs:token is similar to NMTOKEN but allows single-occurrence whitespace characters within the string. No leading or trailing spaces can occur. (XML Schema)

X3D Scene Authoring Hints: Validation describe all initial XML headers for X3D.

Note that regex checking of expressions within the X3D XML Schemas are needed, since literal validation of those attribute values gets performed by various authoring tools (such as Altova XMLSpy).

Regex testing for XML-related constructs by X3dDoctypeChecker.java include the following.

🔖 Error-detection regexes are applied as part of X3D Examples Archives build.xml checking, see target processScenes.regularExpressionChecks for invocation details.

🔖 Error-correction regexes are also possible using XPath replace(source,pattern,replacement) function. For repeatability the pattern being matched must be a strict regular expression rather than a literal.

🔖 References

The following references provide useful additional information about X3D, regular expressions and data validation.

1. Apache Ant Manual: replaceregexp, regexp type, regexp type mapper. Also Ant-contrib propertyregex.
2. Davis, Mark. Unicode Regular Expression Guidelines, 2016.
3. Friedl, Jeffrey E.F., Mastering Regular Expressions: Understand Your Data and Be More Productive Third Edition, O'Reilly and Associates, Sebastopol California, 2009.
4. Goyvaertz, Jan and Levithan, Steven, Regular Expressions Cookbook: Detailed Solutions in Eight Programming Languages, second edition, O'Reilly Media, Sebastopol California, 2012.
5. Python regular expression (regex) library re is built into Python (Python regex howto)
6. RegExLib.com regular expression library
7. Regular-expressions.Info website, including XML Schema Regular Expressions and Runaway Regular Expressions: Catastrophic Backtracking.
8. E-mail post: Regular expression checking for malformed floating-point numbers and excess leading zeros
9. Wikipedia: Regular expression article.
10. Wikipedia: Ken Thompson's construction algorithm article.
11. X3D field data types are defined in Annex 5. Field type reference X3D Abstract Specification.
12. World Wide Web Consortium (W3C) Recommendation: XML Schema Definition Language (XSD) 1.1 Part 2 Datatypes with sections on Regular expressions, float checking, etc.
13. X3D Specifications: XML Schema and DOCTYPE Validation include the latest versions of recommended XML Schemas and DOCTYPEs (DTDs) for X3D.
14. X3D Resources provides links to numerous resources supporting X3D and VRML.
    • X3D Quality Assurance (QA) identifies errors and warnings in order to make X3D scene content more portable and reliable. This section provides links to each of the different QA tests that are available.
15. X3D Scene Authoring Hints provide a collection of style guidelines, authoring tips and best practices to improve the quality, consistency and maintainability of X3D Graphics scenes.
    • Validation of X3D Scenes using DTD and XML Schema shows example declarations of DTD and Schema in X3D scenes.
16. X3D Unified Object Model (X3DUOM)
17. X3D Java Scene Access Interface Library (X3DJSAIL)
18. X3D Validator is a Web application that checks X3D scene validity.
19. XML Schema 1.1 Part 2: Datatypes Second Edition, World Wide Web Consortium (W3C) Recommendation. Includes sections on Datatype System, Built-in datatypes and Regular Expressions.

🔖 Tools

Links to tools of interest follow. Additional recommendations are welcome.

• Online Regex Tester allows live color-coded testing of regex expressions and corresponding string matches in a browser. (n.b. alternative regex vocabularies offered)
• XML Schema - Regular Expressions offers detailed guidance.

🔖 Contact

Questions, suggestions and comments about these resources are welcome. Please send them to Don Brutzman.

The contributions of Roy Walmsley are gratefully acknowledged.

Available online at https://www.web3d.org/specifications/X3dRegularExpressions.html

Version control of this document is maintained at
https://sourceforge.net/p/x3d/code/HEAD/tree/www.web3d.org/specifications/X3dRegularExpressions.html

Updated: 3 September 2023