W3C home > Mailing lists > Public > public-script-coord@w3.org > October to December 2012

Generating random WebIDL fragments from grammar

From: Dominique Hazael-Massieux <dom@w3.org>
Date: Fri, 21 Dec 2012 18:38:30 +0100
Message-ID: <1356111510.3064.8.camel@cumulustier>
To: public-script-coord@w3.org
Cc: public-webapps-testsuite@w3.org
Hi,

As a way to test both my WebIDL parser [1] and the WebIDL grammar, I've
been looking at generating random but valid fragments from the WebIDL
grammar.

To that end, I've been using abnfgen:
http://www.quut.com/abnfgen/

Since abnfgen only takes ABNF as input, I've written a quick and dirty
script (attached) that converts the grammar as defined in the WebIDL
spec (when copied and pasted in a text file) into an ABNF grammar.

It does mostly syntax conversion from one grammar to the other, although
it also does a few tweaks in order to generate more useful test cases. 

The grammar that it currently generates is buggy, because the grammar in
the WebIDL spec is buggy; attached is a ABNF grammar that more closely
matches what I think WebIDL intends.

Using that grammar, I can generate a bunch of random WebIDL fragments,
e.g. with:
        for i in `seq 1 150` ; do abnfgen webidl.bnf > test$i.idl ; done
which I then run against my parser:
        for i in *.idl ;do widlproc $i 1>/dev/null ; done

This has proved pretty useful in finding bugs in my implementation, as
well as bugs in the grammar, so I thought I would share it.

(I've already modified a number of test cases in the widlproc repository
as a result of this work)

Dom

1. https://github.com/dontcallmedom/widlproc

Definitions=1*(ExtendedAttributeList Definition) [Definitions]
Definition=CallbackOrInterface
 / Partial / Dictionary / Exception / Enum / Typedef / ImplementsStatement
CallbackOrInterface=whitespace 'callback' whitespace CallbackRestOrInterface / Interface
CallbackRestOrInterface=CallbackRest / Interface
Interface=whitespace 'interface' whitespace identifier Inheritance whitespace '{' whitespace InterfaceMembers whitespace '}' whitespace ';' whitespace
Partial=whitespace 'partial' whitespace PartialDefinition
PartialDefinition=PartialInterface / PartialDictionary
PartialInterface=whitespace 'interface' whitespace identifier whitespace '{' whitespace InterfaceMembers whitespace '}' whitespace ';' whitespace
InterfaceMembers=[ExtendedAttributeList InterfaceMember InterfaceMembers]
InterfaceMember=Const / AttributeOrOperationOrIterator
Dictionary=whitespace 'dictionary' whitespace identifier Inheritance whitespace '{' whitespace DictionaryMembers whitespace '}' whitespace ';' whitespace
DictionaryMembers=[ExtendedAttributeList DictionaryMember DictionaryMembers]
DictionaryMember=Type identifier Default whitespace ';' whitespace
PartialDictionary=whitespace 'dictionary' whitespace identifier whitespace '{' whitespace DictionaryMembers whitespace '}' whitespace ';' whitespace
Default=['=' whitespace DefaultValue]
DefaultValue=ConstValue / string
Exception=whitespace 'exception' whitespace identifier Inheritance whitespace '{' whitespace ExceptionMembers whitespace '}' whitespace ';' whitespace
ExceptionMembers=[ExtendedAttributeList ExceptionMember ExceptionMembers]
Inheritance=[':' whitespace identifier]
Enum=whitespace 'enum' whitespace identifier whitespace '{' whitespace EnumValueList whitespace '}' whitespace ';' whitespace
EnumValueList=string EnumValues
EnumValues=[',' whitespace string EnumValues]
CallbackRest=identifier whitespace '=' whitespace ReturnType whitespace '(' whitespace ArgumentList whitespace ')' whitespace ';' whitespace
Typedef=whitespace 'typedef' whitespace ExtendedAttributeList Type identifier whitespace ';' whitespace
ImplementsStatement=identifier whitespace 'implements' whitespace identifier whitespace ';' whitespace
Const=whitespace 'const' whitespace ConstType identifier whitespace '=' whitespace ConstValue whitespace ';' whitespace
ConstValue=BooleanLiteral / FloatLiteral / integer /whitespace 'null' whitespace
BooleanLiteral=whitespace 'true' whitespace /whitespace 'false' whitespace
FloatLiteral=float /whitespace '-' 'Infinity' whitespace /whitespace 'Infinity' whitespace /whitespace 'NaN' whitespace
AttributeOrOperationOrIterator=Serializer / Stringifier / Static / Attribute / OperationOrIterator
Serializer=whitespace 'serializer' whitespace SerializerRest
SerializerRest= ReturnType OperationRest /whitespace '=' whitespace SerializationPattern whitespace ';' / whitespace ';' whitespace
SerializationPattern=whitespace '{' whitespace SerializationPatternMap whitespace '}' whitespace /whitespace '[' whitespace SerializationPatternList whitespace ']' whitespace / identifier
SerializationPatternMap=['getter' whitespace /whitespace 'inherit' whitespace Identifiers / identifier Identifiers]
SerializationPatternList=['getter' whitespace / identifier Identifiers]
Identifiers=[',' whitespace identifier Identifiers]
Stringifier = whitespace 'stringifier' whitespace (AttributeOrOperationRest / whitespace ';' whitespace)
Static=whitespace 'static' whitespace AttributeOrOperationRest
AttributeOrOperationRest=AttributeRest / ReturnType OperationRest
Attribute=Inherit AttributeRest
AttributeRest=ReadOnly whitespace 'attribute' whitespace Type identifier whitespace ';' whitespace
Inherit=[whitespace 'inherit' whitespace]
ReadOnly=[whitespace 'readonly' whitespace]
OperationOrIterator=ReturnType OperationOrIteratorRest / SpecialOperation
SpecialOperation=Special Specials ReturnType OperationRest
Specials=[Special Specials]
Special=whitespace 'getter' whitespace /whitespace 'setter' whitespace /whitespace 'creator' whitespace /whitespace 'deleter' whitespace /whitespace 'legacycaller' whitespace
OperationOrIteratorRest=IteratorRest / OperationRest
IteratorRest=whitespace 'iterator' whitespace OptionalIteratorInterfaceOrObject whitespace ';' whitespace
OptionalIteratorInterfaceOrObject=OptionalIteratorInterface /whitespace 'object' whitespace
OptionalIteratorInterface=['=' whitespace identifier]
OperationRest=OptionalIdentifier Whitespace '(' whitespace ArgumentList whitespace ')' whitespace ';' whitespace
OptionalIdentifier=[identifier]
ArgumentList=[Argument Arguments]
Arguments=[',' whitespace Argument Arguments]
Argument=ExtendedAttributeList OptionalOrRequiredArgument
OptionalOrRequiredArgument=whitespace 'optional' whitespace Type ArgumentName Default / Type Ellipsis ArgumentName
ArgumentName=ArgumentNameKeyword / identifier
Ellipsis=['...']
ExceptionMember=Const / ExceptionField
ExceptionField=Type identifier whitespace ';' whitespace
ExtendedAttributeList=['[' whitespace ExtendedAttribute ExtendedAttributes whitespace ']']
ExtendedAttributes=[',' whitespace ExtendedAttribute ExtendedAttributes]
;ExtendedAttribute=whitespace '(' whitespace ExtendedAttributeInner whitespace ')' whitespace ExtendedAttributeRest /whitespace '[' whitespace ExtendedAttributeInner whitespace ']' whitespace ExtendedAttributeRest /whitespace '{' whitespace ExtendedAttributeInner whitespace '}' whitespace ExtendedAttributeRest / OtherO ExtendedAttributeRest
ExtendedAttribute = ExtendedAttributeNoArgs / ExtendedAttributeArgList / ExtendedAttributeIdent / ExtendedAttributeNamedArgList
ExtendedAttributeRest=[ExtendedAttribute]
ExtendedAttributeInner=['(' whitespace ExtendedAttributeInner whitespace ')' whitespace ExtendedAttributeInner /whitespace '[' whitespace ExtendedAttributeInner whitespace ']' whitespace ExtendedAttributeInner /whitespace '{' whitespace ExtendedAttributeInner whitespace '}' whitespace ExtendedAttributeInner / OtherOrComma ExtendedAttributeInner]
OtherO=integer / float / identifier / string / other /whitespace '-' whitespace /whitespace '.' whitespace /whitespace '...' whitespace /whitespace ':' whitespace /whitespace ';' whitespace /whitespace '<' whitespace /whitespace '=' whitespace /whitespace '>' whitespace /whitespace '?' whitespace /whitespace 'ByteString' whitespace /whitespace 'Date' whitespace /whitespace 'DOMString' whitespace /whitespace 'Infinity' whitespace /whitespace 'NaN' whitespace /whitespace 'RegExp' whitespace /whitespace 'any' whitespace /whitespace 'boolean' whitespace /whitespace 'byte' whitespace /whitespace 'double' whitespace /whitespace 'false' whitespace /whitespace 'float' whitespace /whitespace 'long' whitespace /whitespace 'null' whitespace /whitespace 'object' whitespace /whitespace 'octet' whitespace /whitespace 'or' whitespace /whitespace 'optional' whitespace /whitespace 'sequence' whitespace /whitespace 'short' whitespace /whitespace 'true' whitespace /whitespace 'unsigned' whitespace /whitespace 'void' whitespace / ArgumentNameKeyword
ArgumentNameKeyword=whitespace 'attribute' whitespace /whitespace 'callback' whitespace /whitespace 'const' whitespace /whitespace 'creator' whitespace /whitespace 'deleter' whitespace /whitespace 'dictionary' whitespace /whitespace 'enum' whitespace /whitespace 'exception' whitespace /whitespace 'getter' whitespace /whitespace 'implements' whitespace /whitespace 'inherit' whitespace /whitespace 'interface' whitespace /whitespace 'legacycaller' whitespace /whitespace 'partial' whitespace /whitespace 'serializer' whitespace /whitespace 'setter' whitespace /whitespace 'static' whitespace /whitespace 'stringifier' whitespace /whitespace 'typedef' whitespace /whitespace 'unrestricted' whitespace
OtherOrComma=OtherO /whitespace ',' whitespace
Type=SingleType / UnionType TypeSuffix
SingleType=NonAnyType /whitespace 'any' whitespace TypeSuffixStartingWithArray
UnionType=whitespace '(' whitespace UnionMemberType whitespace 'or' whitespace UnionMemberType UnionMemberTypes whitespace ')' whitespace
UnionMemberType=NonAnyType / UnionType TypeSuffix /whitespace 'any' whitespace '[' whitespace ']' whitespace TypeSuffix
UnionMemberTypes=['or' whitespace UnionMemberType UnionMemberTypes]
NonAnyType=PrimitiveType TypeSuffix /whitespace 'ByteString' whitespace TypeSuffix /whitespace 'DOMString' whitespace TypeSuffix / identifier TypeSuffix /whitespace 'sequence' whitespace '<' whitespace Type whitespace '>' whitespace Null /whitespace 'object' whitespace TypeSuffix /whitespace 'Date' whitespace TypeSuffix /whitespace 'RegExp' whitespace TypeSuffix
ConstType=PrimitiveType Null / identifier Null
PrimitiveType=UnsignedIntegerType / UnrestrictedFloatType /whitespace 'boolean' whitespace /whitespace 'byte' whitespace /whitespace 'octet' whitespace
UnrestrictedFloatType=whitespace 'unrestricted' whitespace FloatType / FloatType
FloatType=whitespace 'float' whitespace /whitespace 'double' whitespace
UnsignedIntegerType=whitespace 'unsigned' whitespace IntegerType / IntegerType
IntegerType=whitespace 'short' whitespace /whitespace 'long' whitespace OptionalLong
OptionalLong=[whitespace 'long' whitespace]
TypeSuffix=['[' whitespace ']' whitespace TypeSuffix /whitespace '?' whitespace TypeSuffixStartingWithArray]
TypeSuffixStartingWithArray=['[' whitespace ']' whitespace TypeSuffix]
Null=['?']
ReturnType=Type /whitespace 'void' whitespace
ExtendedAttributeNoArgs=identifier
ExtendedAttributeArgList=identifier whitespace '(' whitespace ArgumentList whitespace ')' whitespace
ExtendedAttributeIdent=identifier whitespace '=' whitespace identifier
ExtendedAttributeNamedArgList=identifier whitespace '=' whitespace identifier whitespace '(' whitespace ArgumentList whitespace ')' whitespace


integer 	= ['-'] 1*DIGIT whitespace ;	-?(0([Xx][0-9A-Fa-f]+|[0-7]*)|[1-9][0-9]*)
float 	=  ['-'] (1*DIGIT '.' *DIGIT / *DIGIT '.' 1*DIGIT) [ 'e' / 'E'  [ '+'  / '-'  ] 1*DIGIT ] whitespace ;	-?(([0-9]+\.[0-9]*|[0-9]*\.[0-9]+)([Ee][+-]?[0-9]+)?|[0-9]+[Ee][+-]?[0-9]+)
nonquote 	= (%x20-21 / %x23-7E) whitespace
identifier 	= 	ALPHA *(ALPHA / DIGIT) whitespace
string 	= 	DQUOTE *nonquote DQUOTE whitespace
whitespace 	= (LF / WSP)
other 	= 	%x20-29 / %x40 / %x5B-60 / %x7B-7E



Received on Friday, 21 December 2012 17:38:53 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 8 May 2013 19:30:08 UTC