/* testgenerator1.pl: Test generator for regexes */

/* Copyright (c) 2008 World Wide Web Consortium, 
 * (Massachusetts Institute of Technology, European Research 
 * Consortium for Informatics and Mathematics, Keio University). 
 * All Rights Reserved. This work is distributed under the 
 * W3C(TM) Software License [1] in the hope that it will be 
 * useful, but WITHOUT ANY WARRANTY; without even the implied 
 * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *
 * [1] http://www.w3.org/Consortium/Legal/2002/copyright-software-20021231
 */

/* This file is part of Xerophily, a parser for XSD regular expressions. */

:- module(testgenerator1,
          [
            teststring/2,
            teststring/3
          ]).

/* experiment:  try suppressing this call.  
:- ensure_loaded('regex.dcg.pl').
*/
:- use_module(g_opts).

/* s(n,NT,s):  n is a number; will be used for random test generation.
 * NT is a non-terminal (used for making sure these are actually legal
 * strings against the non-terminals I think they are legal against).
 * s is a string; should be legal against the non-terminal.
 */

teststring(N,S) :- teststring(N,_,S).
teststring(N,A,S) :-
	/* generate n random numbers */
	random_numbers(N,Ns),
	/* concatenate the strings they select */
	numbers_strings(Ns,Ss),
	concat_atom(Ss,A),
	atom_chars(A,S).

random_numbers(0,[]).
random_numbers(N0,[R|Rs]) :-
	N0 > 0,
	N1 is N0 - 1,
	R is random(128),
	random_numbers(N1,Rs).

numbers_strings(Ns,Ss) :- maplist(n_s,Ns,Ss).
n_s(N,S) :- s(N,_,S).

/* verify:  check that the strings really are what I think they are.
 * Unfortunately, this doesn't work as written:  not all of the
 * nonterminals in the grammar take exactly two arguments.
 * So I'm skipping this verification step for now; it's not really
 * crucial. -MSS, 2008-05-27
 */
verify_once_failable(AST) :-
	default_grammar(G),
	get_grammar_options(G,Opts),
	s(_,NT,A),
	NT \= terminal,
	verify(NT,Opts,A,AST).

verify(NT,Opts,A,AST) :-
	Head =.. [NT, Opts, AST],
	atom_chars(A,S),
	phrase(Head,S).	
	

/* Do expressions for each non-terminal in the grammar, at least
 * the ones that appear on right-hand sides (here, all of them do).
 *
 * Imagine the approriate set of ATNs as a single large regex 
 * consisting of a choice over all the ATNs, and with an alphabet
 * containing (a) all the real terminal symbols (or at least
 * one representative of each equivalence class) and (b) pseudo-atoms
 * (here represented as strings) matching each non-terminal.
 * It's then clear (a) how many states there are and (b) what
 * the largest minimum path length is.
 */



/* DCG for XML Schema 1.0 regular expressions.
 * Parse the expression and return a structure.
 * 
 * Revisions:
 * 2008-05-24 : CMSMcQ : build a set of substrings for random string generation,
 *                       starting from regex.dcg.pl
 */


/* "A regular expression is composed from zero or more branches,
 * separated by | characters."
 *
 * [1] regExp ::= branch ( '|' branch )* 
 */
/* (Actually, the grammar requires at least one branch; the prose is wrong,
 * misguided perhaps by the fact that the branch can be empty. 
 */
s(0,regExp,'0').
s(1,regExp,'a').
s(2,regExp,'').
s(3,regExp,'[abc]').
s(4,regExp,'a|b|cde').
s(5,terminal,'|').

s(6,altbranches,'|xyz').
s(7,altbranches,'|[a-z]|[0-9]*').

/* [Definition:] A branch consists of zero or more pieces,
 * concatenated together.
 */
/* [2] branch ::= piece* */

s(8,branch,'x').
s(9,branch,'x*y+z{2,5}').

 

/* [Definition:] A piece is an atom, possibly followed by a
 * quantifier.
 *
 * [3] piece ::= atom quantifier?  
 */




/* [Definition:] A quantifier is one of ?, *, +, {n,m} or {n,}, which
 * have the meanings defined in the table above.
 *
 * [4] quantifier ::= [?*+] | ( '{' quantity '}' ) 
 */
/* [5] quantity ::= quantRange | quantMin | QuantExact */
/* [6] quantRange ::= QuantExact ',' QuantExact */
/* [7] quantMin ::= QuantExact ',' */
/* [8] QuantExact ::= [0-9]+ */

s(10,quantifier,'?').
s(11,quantifier,'+').
s(12,quantifier,'*').
s(13,terminal,'{').
s(14,terminal,'}').
s(15,terminal,',').
s(16,quantifier,'{1,9}').
s(17,quantifier,'{3,}').
s(18,quantifier,'{3}').
s(19,maxspec,',2').
s(20,maxspec,',').
s(21,quantexact,'2').
s(22,quantexact,'999').
s(23,digit,'3').



/* [Definition:] An atom is either a normal character, a character
 * class, or a parenthesized regular expression.
 * 
 * [9] atom ::= Char | charClass | ( '(' regExp ')' ) 
 */

s(24,re_atom,'3').
s(25,re_atom,'x').
s(26,re_atom,'[xyz]').
s(27,re_atom,'([xyz])').
s(28,re_atom,'(([xyz]))').
s(29,re_atom,'((([xyz])))').
s(30,terminal,'(').
s(31,terminal,')').

/* [Definition:] A metacharacter is either ., \, ?, *, +, {, } (, ), |, 
 * [, or ]. These characters have special meanings in regular
 * expressions, but can be escaped to form atoms that denote the sets
 * of strings containing only themselves, i.e., an escaped
 * metacharacter behaves like a normal character.
 */

s(32,terminal,'.').
s(33,terminal,'\\').
s(34,terminal,'?').
s(35,terminal,'*').
s(36,terminal,'+').
s(37,terminal,'{').
s(38,terminal,'}').
s(39,terminal,'(').
s(40,terminal,')').
s(41,terminal,'|').

/* N.B. XSD 1.0 omitted | from this list, as did drafts D4 and D5 
 * of XSD 1.1.  D6 and later include it.  The grammar rules have 
 * always had it, so it's unlikely that any parsers treat | as a 
 * normal character, but there's a grammar option for it, just in
 * case.
 */

/* [Definition:] A normal character is any XML character that is not a
 * metacharacter. In regular expressions, a normal character is an
 * atom that denotes the singleton set of strings containing only
 * itself.
 *
 * 1.0 1E, PER, 2E, D4, and D5 have:
 *
 *     [10] Char ::= [^.\?*+()|#x5B#x5D] 
 *
 * Later versions (D6, LC, D8, W) have:
 *
 *     [10] Char ::= [^.\?*+{}()|#x5B#x5D] 
 */

s(42,char,'.').
s(43,char,'\\').
s(44,char,'?').
s(45,char,'*').
s(46,char,'+').
s(47,char,'(').
s(48,char,')').
s(49,char,'[').
s(50,char,']').
s(51,char,'|').
s(52,char,'{').
s(53,char,'}').



/* Note that a normal character can be represented either as itself,
 * or with a character reference.
 */

/* F.1 Character Classes */

/* [Definition:] A character class is an atom R that identifies a set
 * of characters C(R). The set of strings L(R) denoted by a character
 * class R contains one single-character string "c" for each character
 * c in C(R).
 *
 * 1.0 1E has:
 * 
 *     [11] charClass ::= charClassEsc | charClassExpr
 * 
 * All other forms of the grammar have:
 *
 * [11] charClass ::= charClassEsc | charClassExpr | WildcardEsc
 *
 */

s(54,charClass,'\n').
s(55,charClass,'\\{').
s(56,charClass,'\\}').
s(57,charClass,'\\s').
s(58,charClass,'\\d').
s(59,charClass,'\\W').
s(60,charClass,'.').
s(61,charClass,'[aeiou]').
s(62,charClass,'[a-zA-Z]').
s(63,charClass,'[^a-zA-Z]').
s(64,charClass,'\\p{L}').
s(65,charClass,'\\p{IsBasicLatin}').
s(66,charClass,'\\p{IsBasicallyLatin}').

 
/* A character class is either a character class escape or a character
 * class expression or a wildcard escape.
 */
/* [Definition:] A character class expression is a character group
 * surrounded by [ and ] characters. For all character groups G, [G]
 * is a valid character class expression, identifying the set of
 * characters C([G]) = C(G).
 *
 * [12] charClassExpr ::= '[' charGroup ']' 
 */

s(67,charClassExpr,'[abc]').
s(68,charClassExpr,'[^abc]').
s(69,charClassExpr,'[\\p{IsBasicLatin}-[aeiou]]').
s(70,charClassExpr,'[^abc-[aeiou]]').

/* [Definition:] A character group is either a positive character
 * group, a negative character group, or a character class
 * subtraction.
 *
 * Grammars 1E through D8 have:
 *
 *     [13] charGroup ::= posCharGroup | negCharGroup | charClassSub 
 * 
 * W has:
 * 
 *     [76] charGroup ::= (posCharGroup | negCharGroup) ('-' charClassExpr)?
 *
 */
s(71,charGroup,'abc').
s(72,charGroup,'a-z').
s(73,charGroup,'a-zA-Z0-9').
s(74,charGroup,'^a-zA-Z0-9').
s(75,charGroup,'^a-zA-Z0-9[abc]').
s(76,charGroup,'^a-zA-Z0-9-[abc]').

/* [Definition:] A positive character group consists of one or more
 * character ranges or character class escapes, concatenated
 * together. A positive character group identifies the set of
 * characters containing all of the characters in all of the sets
 * identified by its constituent ranges or escapes.
 *
 * Most forms of the grammar have:
 *
 *     [14] posCharGroup ::= ( charRange | charClassEsc )+ 
 * 
 * W has:
 * 
 *     [77] posCharGroup ::= (charGroupPart)+
 *
 */

/* N.B. "The ^ character is only valid at the beginning of a positive 
 * character group if it is part of a negative character group".
 *
 * So we pass a parameter on the call to posCharGroup, to act as a flag: 
 *   - 'nolc' means no leading caret is allowed.
 *   - 'oklc' means leading caret is allowed.
 * We could check this in the AST, instead of here.  But for most
 * purposes, it's more convenient to impose that rule here instead
 * of generating multiple parse trees and then winnowing them.
 *
 */
s(77,posCharGroup,'xyz').
s(78,posCharGroup,'q-v').
s(79,posCharGroup,'\\+').
s(80,posCharGroup,'\\-').
s(81,posCharGroup,'\\[').
s(82,posCharGroup,'\\]').
s(83,posCharGroup,'\\^').

/* [Definition:] A negative character group is a positive character
 * group preceded by the ^ character. For all positive character
 * groups P, ^P is a valid negative character group, and C(^P)
 * contains all XML characters that are not in C(P).
 *
 * [15] negCharGroup ::= '^' posCharGroup 
 */
s(84,posCharGroup,'^xyz').
s(85,posCharGroup,'^q-v').
s(86,posCharGroup,'^\\+').
s(87,posCharGroup,'^\\-').
s(88,posCharGroup,'^\\^').
s(89,posCharGroup,'^^').


 
/* [Definition:] A character class subtraction is a character class
 * expression subtracted from a positive character group or negative
 * character group, using the - character.
 *
 * [16] charClassSub ::= ( posCharGroup | negCharGroup ) '-'
 *                       charClassExpr 
 */

s(90,charClassSub,'a-z-[aeiou]').
s(91,charClassSub,'abcABC-[aeiou]').

/* [Definition:] A character group part (charGroupPart) is either a
 * single unescaped character (SingleCharNoEsc), a single escaped
 * character (SingleCharEsc), or a character range (charRange).
 *
 * 
 * [79] charGroupPart ::= singleChar | charRange
 * [80] singleChar ::= SingleCharEsc | SingleCharNoEsc 
 *
 * If a charGroupPart starts with a singleChar and this is immediately
 * followed by a hyphen, and if the hyphen is part of the character
 * group (that is, it is not being treated as a substraction operator
 * because it is followed by '['), then the hyphen must be followed by
 * another singleChar, and the sequence (singleChar, hyphen,
 * singleChar) is treated as a charRange. It is an error if either of
 * the two singleChars in a charRange is a SingleCharNoEsc comprising
 * an unescaped hyphen.
 *
 * (This seems to rule out groups like [a-], perhaps intentionally.)
 *
 * More formally, I read that paragraph as saying
 * if (lookahead('-') and not lookahead('-]'), then fail.
 * Reversed to be a condition of success, this becomes the guard
 * ( not lookahead('-') or lookahead('-[') ), or in Prolog as below.
 */

s(92,charGroupPart,'a').
s(93,charGroupPart,'x').
s(94,charGroupPart,'x-z').
s(95,charGroupPart,'\\t').

/* [Definition:] A character range R identifies a set of characters
 * C(R) containing all XML characters with UCS code points in a
 * specified range.
 *
 * Several variants.  charrange('1E') (1.0 1E) has:
 *
 *     [17] charRange ::= seRange | XmlCharRef | XmlCharIncDash  
 *
 * charrange('PER') (1.0 2E PER) has:
 * 
 *     [17] charRange ::= seRange | XmlChar  
 *
 * charrange('2E') (2E, D4-D8) has:
 *
 *     [17] charRange ::= seRange | XmlCharIncDash
 *
 * charRange('W') (draft proposal for bug 1889) has:
 * 
 *     [82] charRange ::= singleChar '-' singleChar
 */  

s(96,charRange,'a-z').
s(97,charRange,'\\n-z').
s(98,charRange,'-').


/* [18] seRange ::= charOrEsc '-' charOrEsc */
/* not reachable if we have grammar option charrange('W'). */


/* [19] XmlCharRef ::= ( '&#' [0-9]+ ';' ) 
 *                   | (' &#x' [0-9a-fA-F]+ ';' ) 
 */
/* Only reachable in 1E */




/* [20] charOrEsc ::= XmlChar | SingleCharEsc */
/* not reachable if we have grammar option charrange('W'). */


/* [21] XmlChar ::= [^\#x2D#x5B#x5D] 
 * i.e. any character but "\", "-",  "[", or "]".
 * If the carethack is on and the CaretFlag argument is 'nolc',
 * then also exclude '^'.
 */
s(99,terminal,'^').
s(100,terminal,'-').

/* XmlCharIncDash is present in 1E, 2E, D4-D8, but not in PER or W. */
/* [22] XmlCharIncDash ::= [^\#x5B#x5D] 
 * i.e. any but \ [ ]
 */


/* 1E through D8 impose some form or other of the following constraints
 * in prose; W omits all of them.
 *
 * "A single XML character is a character range that identifies the set
 * of characters containing only itself. All XML characters are valid
 * character ranges, except as follows:"
 *
 *   "The [, ], - and \ characters are not valid character ranges;"
 *
 * Imposed in this program by a guard on charRange (not checked for 
 * grammar version W).
 *
 *   "The ^ character is only valid at the beginning of a positive
 *   character group if it is part of a negative character group"
 *
 * Imposed here by the caret hack (CaretFlag argument).
 * W has a similar rule elsewhere, so this is checked pretty much
 * always.
 *
 *   "The - character is a valid character range only at the
 *   beginning or end of a positive character group."
 *
 * Not in PER or W.  Constraint imposed here by call to hyphen_ok
 * with the content of any positive character group.
 *
 *   A character range may also be written in the form s-e,
 *   identifying the set that contains all XML characters with UCS
 *   code points greater than or equal to the code point of s, but not
 *   greater than the code point of e.
 */
/* All versions up to W say:
 * "s-e is a valid character range iff:
 *
 *   "s is a single character escape, or an XML character; 
 *   "s is not \ 
 *   "If s is the first character in a character class expression, 
 *      [??? surely you mean in a positive character group?!]
 *      then s is not ^ 
 *   "e is a single character escape, or an XML character; 
 *   "e is not \ or [; and 
 *   "The code point of e is greater than or equal to the code point of
 *      s."
 */
/* Of these, 1 and 4 are enforced by the grammar,
 * 3 by the carethack flag, and 2, 5, and 6 are enforced 
 * by a guard in the rule for serange.
 */

/* W adds:
 * 
 * [87] SingleCharNoEsc ::= [^\#x5B#x5D] 
 * 
 * A single unescaped character (SingleCharNoEsc) is any character
 * except '[' or ']'. There are special rules, described earlier, that
 * constraint the use of the characters '-' and '^' in order to
 * disambiguate the syntax.
 */


/* N.B. The prose of proposal W does not mention \, so the correct
 * rule may be 	not(member(Atom, [ '[',']' ])) }.
 * Not something to make a grammar option for, though.
 */


/* F.1.1 Character Class Escapes
 *
 * [Definition:] A character class escape is a short sequence of
 * characters that identifies predefined character class. The valid
 * character class escapes are the single character escapes, the
 * multi-character escapes, and the category escapes (including the
 * block escapes).
 *
 * [23] charClassEsc ::= ( SingleCharEsc | MultiCharEsc | catEsc |
 *                         complEsc ) 
 */


/* [Definition:] A single character escape identifies a set containing
 * a only one character -- usually because that character is difficult
 * or impossible to write directly into a regular expression.
 */
/* [24] SingleCharEsc ::= '\' [nrt\|.?*+(){}#x2D#x5B#x5D#x5E] */
/*                             nrt\|.?*+(){} -   [   ]   ^    */


/* The valid single character escapes are: Identifying the set of
 * characters C(R) containing:
 *
 *   \n the newline character (#xA) 
 *   \r the return character (#xD) 
 *   \t the tab character (#x9) 
 *   \\ \ 
 *   \| | 
 *   \. . 
 *   \- - 
 *   \^ ^ 
 *   \? ? 
 *   \* * 
 *   \+ + 
 *   \{ { 
 *   \} } 
 *   \( ( 
 *   \) ) 
 *   \[ [ 
 *   \] ] 
 */

s(101,terminal,'\\n').
s(102,terminal,'\\r').
s(103,terminal,'\\t').
s(104,terminal,'\\\\').
s(105,terminal,'\\|').
s(106,terminal,'\\.').
s(107,terminal,'\\-').
s(108,terminal,'\\^').
s(109,terminal,'\\?').
s(110,terminal,'\\*').
s(111,terminal,'\\+').
s(112,terminal,'\\{').
s(113,terminal,'\\}').
s(114,terminal,'\\(').
s(115,terminal,'\\)').
s(116,terminal,'\\[').
s(117,terminal,'\\]').

/* [Definition:] [Unicode Database] specifies a number of possible
 * values for the "General Category" property and provides mappings
 * from code points to specific character properties. The set
 * containing all characters that have property X, can be identified
 * with a category escape \p{X}. The complement of this set is
 * specified with the category escape \P{X}. ([\P{X}] = [^\p{X}]).
 */
/* [25] catEsc ::= '\p{' charProp '}' */

s(118,terminal,'\\p{').
s(119,terminal,'\\P{').
s(120,terminal,'}').
s(121,terminal,'}').

/* [26] complEsc ::= '\P{' charProp '}' */


/* [27] charProp ::= IsCategory | IsBlock */


/* Note: [Unicode Database] is subject to future revision. For
 * example, the mapping from code points to character properties might
 * be updated. All minimally conforming processors must support the
 * character properties defined in the version of [Unicode Database]
 * that is current at the time this specification became a W3C
 * Recommendation. However, implementors are encouraged to support the
 * character properties defined in any future version.
 */
/* The following table specifies the recognized values of the "General
 * Category" property.
 *
 *   Category Property Meaning 
 *   Letters     L  All Letters 
 *               Lu uppercase 
 *               Ll lowercase 
 *               Lt titlecase 
 *               Lm modifier 
 *               Lo other 
 *
 *   Marks       M  All Marks 
 *               Mn nonspacing 
 *               Mc spacing combining 
 *               Me enclosing 
 *
 *   Numbers     N  All Numbers 
 *               Nd decimal digit 
 *               Nl letter 
 *               No other 
 *
 *   Punctuation P  All Punctuation 
 *               Pc connector 
 *               Pd dash 
 *               Ps open 
 *               Pe close 
 *               Pi initial quote (may behave like Ps or Pe 
 *                  depending on usage) 
 *               Pf final quote (may behave like Ps or Pe 
 *                  depending on usage) 
 *               Po other 
 *
 *   Separators  Z  All Separators 
 *               Zs space 
 *               Zl line 
 *               Zp paragraph 
 *
 *   Symbols     S All Symbols 
 *               Sm math 
 *               Sc currency 
 *               Sk modifier 
 *               So other 
 *
 *   Other       C  All Others 
 *               Cc control 
 *               Cf format 
 *               Co private use 
 *               Cn not assigned 
 */

/* [28] IsCategory ::= Letters | Marks | Numbers | Punctuation |
 *                     Separators | Symbols | Others */


/* [29] Letters ::= 'L' [ultmo]?  */
/* [30] Marks ::= 'M' [nce]?  */
/* [31] Numbers ::= 'N' [dlo]?  */
/* [32] Punctuation ::= 'P' [cdseifo]?  */
/* [33] Separators ::= 'Z' [slp]?  */
/* [34] Symbols ::= 'S' [mcko]?  */
/* [35] Others ::= 'C' [cfon]?  */

s(122,terminal,'Lu').
s(123,terminal,'Sk').
s(124,terminal,'Cn').

/* Note: The properties mentioned above exclude the Cs property. The
 * Cs property identifies "surrogate" characters, which do not occur
 * at the level of the "character abstraction" that XML instance
 * documents operate on.
 */
/* [Definition:] [Unicode Database] groups code points into a number
 * of blocks such as Basic Latin (i.e., ASCII), Latin-1 Supplement,
 * Hangul Jamo, CJK Compatibility, etc. The set containing all
 * characters that have block name X (with all white space stripped
 * out), can be identified with a block escape \p{IsX}. The complement
 * of this set is specified with the block escape \P{IsX}. ([\P{IsX}]
 * = [^\p{IsX}]).
 */
/* [36] IsBlock ::= 'Is' [a-zA-Z0-9#x2D]+ */
s(125,'IsBlock','abracadabra').
s(126,'IsBlock','IsGreek').
s(126,'IsBlock','IsGreek').
s(127,'IsBlock','IsCJKCompatibilityIdeographsSupplement').

/* [Definition:] A multi-character escape provides a simple way to
 * identify a commonly used set of characters:
 *
 * 1E has:
 *
 * [37] MultiCharEsc ::= '.' | ('\' [sSiIcCdDwW])  
 *
 * All later versions have:
 *
 * [37] MultiCharEsc ::= '\' [sSiIcCdDwW]  
 */



/* ? [37a] WildcardEsc ::= '.' ?  */


/*   Character sequence Equivalent character class 
 *
 *   .  [^\n\r] 
 *   \s [#x20\t\n\r] 
 *   \S [^\s] 
 *   \i the set of initial name characters, 
 *      those matched by Letter | '_' | ':' 
 *   \I [^\i] 
 *   \c the set of name characters, those matched by NameChar 
 *   \C [^\c] 
 *   \d \p{Nd} 
 *   \D [^\d] 
 *   \w [#x0000-#x10FFFF]-[\p{P}\p{Z}\p{C}] 
 *      (all characters except the set of "punctuation", 
 *      "separator" and "other" characters)  
 *   \W [^\w] 
 */
/* Note: The regular expression language defined here does not attempt
 * to provide a general solution to "regular expressions" over UCS
 * character sequences. In particular, it does not easily provide for
 * matching sequences of base characters and combining marks. The
 * language is targeted at support of "Level 1" features as defined in
 * [Unicode Regular Expression Guidelines]. It is hoped that future
 * versions of this specification will provide support for "Level 2"
 * features.
 */

