[apple/icu.git] / icuSources / i18n / regexcmp.h

// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
//
//  regexcmp.h
//
//  Copyright (C) 2002-2016, International Business Machines Corporation and others.
//  All Rights Reserved.
//
//  This file contains declarations for the class RegexCompile
//
//  This class is internal to the regular expression implementation.
//  For the public Regular Expression API, see the file "unicode/regex.h"
//


#ifndef RBBISCAN_H
#define RBBISCAN_H

#include "unicode/utypes.h"
#if !UCONFIG_NO_REGULAR_EXPRESSIONS

#include "unicode/parseerr.h"
#include "unicode/uniset.h"
#include "unicode/uobject.h"
#include "unicode/utext.h"
#include "uhash.h"
#include "uvector.h"
#include "uvectr32.h"


U_NAMESPACE_BEGIN


//--------------------------------------------------------------------------------
//
//  class RegexCompile    Contains the regular expression compiler.
//
//--------------------------------------------------------------------------------
struct  RegexTableEl;
class   RegexPattern;


class U_I18N_API RegexCompile : public UMemory {
public:

    enum {
        kStackSize = 100            // The size of the state stack for
    };                              //   pattern parsing.  Corresponds roughly
                                    //   to the depth of parentheses nesting
                                    //   that is allowed in the rules.

    struct RegexPatternChar {
        UChar32             fChar;
        UBool               fQuoted;
    };

    RegexCompile(RegexPattern *rp, UErrorCode &e);

    void       compile(const UnicodeString &pat, UParseError &pp, UErrorCode &e);
    void       compile(UText *pat, UParseError &pp, UErrorCode &e);
    

    virtual    ~RegexCompile();

    void        nextChar(RegexPatternChar &c);      // Get the next char from the input stream.

    static void cleanup();                       // Memory cleanup


    // Categories of parentheses in pattern.
    //   The category is saved in the compile-time parentheses stack frame, and
    //   determines the code to be generated when the matching close ) is encountered.
    enum EParenClass {
        plain        = -1,               // No special handling
        capturing    = -2,
        atomic       = -3,
        lookAhead    = -4,
        negLookAhead = -5,
        flags        = -6,
        lookBehind   = -7,
        lookBehindN  = -8
    };

private:


    UBool       doParseActions(int32_t a);
    void        error(UErrorCode e);                   // error reporting convenience function.

    UChar32     nextCharLL();
    UChar32     peekCharLL();
    UnicodeSet  *scanProp();
    UnicodeSet  *scanPosixProp();
    void        handleCloseParen();
    int32_t     blockTopLoc(UBool reserve);          // Locate a position in the compiled pattern
                                                     //  at the top of the just completed block
                                                     //  or operation, and optionally ensure that
                                                     //  there is space to add an opcode there.
    void        compileSet(UnicodeSet *theSet);      // Generate the compiled pattern for
                                                     //   a reference to a UnicodeSet.
    void        compileInterval(int32_t InitOp,      // Generate the code for a {min,max} quantifier.
                               int32_t LoopOp);
    UBool       compileInlineInterval();             // Generate inline code for a {min,max} quantifier
    void        literalChar(UChar32 c);              // Compile a literal char
    void        fixLiterals(UBool split=FALSE);      // Generate code for pending literal characters.
    void        insertOp(int32_t where);             // Open up a slot for a new op in the
                                                     //   generated code at the specified location.
    void        appendOp(int32_t op);                // Append a new op to the compiled pattern.
    void        appendOp(int32_t type, int32_t val); // Build & append a new op to the compiled pattern.
    int32_t     buildOp(int32_t type, int32_t val);  // Construct a new pcode instruction.
    int32_t     allocateData(int32_t size);          // Allocate space in the matcher data area.
                                                     //   Return index of the newly allocated data.
    int32_t     allocateStackData(int32_t size);     // Allocate space in the match back-track stack frame.
                                                     //   Return offset index in the frame.
    int32_t     minMatchLength(int32_t start,
                               int32_t end);
    int32_t     maxMatchLength(int32_t start,
                               int32_t end);
    void        matchStartType();
    void        stripNOPs();

    void        setEval(int32_t op);
    void        setPushOp(int32_t op);
    UChar32     scanNamedChar();
    UnicodeSet *createSetForProperty(const UnicodeString &propName, UBool negated);

public:   // Public for testing only.
    static void U_EXPORT2 findCaseInsensitiveStarters(UChar32 c, UnicodeSet *starterChars);
private:


    UErrorCode                    *fStatus;
    RegexPattern                  *fRXPat;
    UParseError                   *fParseErr;

    //
    //  Data associated with low level character scanning
    //
    int64_t                       fScanIndex;        // Index of current character being processed
                                                     //   in the rule input string.
    UBool                         fQuoteMode;        // Scan is in a \Q...\E quoted region
    UBool                         fInBackslashQuote; // Scan is between a '\' and the following char.
    UBool                         fEOLComments;      // When scan is just after '(?',  inhibit #... to
                                                     //   end of line comments, in favor of (?#...) comments.
    int64_t                       fLineNum;          // Line number in input file.
    int64_t                       fCharNum;          // Char position within the line.
    UChar32                       fLastChar;         // Previous char, needed to count CR-LF
                                                     //   as a single line, not two.
    UChar32                       fPeekChar;         // Saved char, if we've scanned ahead.


    RegexPatternChar              fC;                // Current char for parse state machine
                                                     //   processing.

    //
    //   Data for the state machine that parses the regular expression.
    //
    RegexTableEl                  **fStateTable;     // State Transition Table for regex Rule
                                                     //   parsing.  index by p[state][char-class]

    uint16_t                      fStack[kStackSize];  // State stack, holds state pushes
    int32_t                       fStackPtr;           //  and pops as specified in the state
                                                       //  transition rules.

    //
    //  Data associated with the generation of the pcode for the match engine
    //
    int32_t                       fModeFlags;        // Match Flags.  (Case Insensitive, etc.)
                                                     //   Always has high bit (31) set so that flag values
                                                     //   on the paren stack are distinguished from relocatable
                                                     //   pcode addresses.
    int32_t                       fNewModeFlags;     // New flags, while compiling (?i, holds state
                                                     //   until last flag is scanned.
    UBool                         fSetModeFlag;      // true for (?ismx, false for (?-ismx

    UnicodeString                 fLiteralChars;     // Literal chars or strings from the pattern are accumulated here.
                                                     //   Once completed, meaning that some non-literal pattern
                                                     //   construct is encountered, the appropriate opcodes
                                                     //   to match the literal will be generated, and this
                                                     //   string will be cleared.

    int64_t                       fPatternLength;    // Length of the input pattern string.
    
    UVector32                     fParenStack;       // parentheses stack.  Each frame consists of
                                                     //   the positions of compiled pattern operations
                                                     //   needing fixup, followed by negative value.  The
                                                     //   first entry in each frame is the position of the
                                                     //   spot reserved for use when a quantifier
                                                     //   needs to add a SAVE at the start of a (block)
                                                     //   The negative value (-1, -2,...) indicates
                                                     //   the kind of paren that opened the frame.  Some
                                                     //   need special handling on close.


    int32_t                       fMatchOpenParen;   // The position in the compiled pattern
                                                     //   of the slot reserved for a state save
                                                     //   at the start of the most recently processed
                                                     //   parenthesized block. Updated when processing
                                                     //   a close to the location for the corresponding open.

    int32_t                       fMatchCloseParen;  // The position in the pattern of the first
                                                     //   location after the most recently processed
                                                     //   parenthesized block.

    int32_t                       fIntervalLow;      // {lower, upper} interval quantifier values.
    int32_t                       fIntervalUpper;    // Placed here temporarily, when pattern is
                                                     //   initially scanned.  Each new interval
                                                     //   encountered overwrites these values.
                                                     //   -1 for the upper interval value means none
                                                     //   was specified (unlimited occurences.)

    int64_t                       fNameStartPos;     // Starting position of a \N{NAME} name in a
                                                     //   pattern, valid while remainder of name is
                                                     //   scanned.

    UStack                        fSetStack;         // Stack of UnicodeSets, used while evaluating
                                                     //   (at compile time) set expressions within
                                                     //   the pattern.
    UStack                        fSetOpStack;       // Stack of pending set operators (&&, --, union)

    UChar32                       fLastSetLiteral;   // The last single code point added to a set.
                                                     //   needed when "-y" is scanned, and we need
                                                     //   to turn "x-y" into a range.

    UnicodeString                *fCaptureName;      // Named Capture, the group name is built up
                                                     //   in this string while being scanned.
};

// Constant values to be pushed onto fSetOpStack while scanning & evalueating [set expressions]
//   The high 16 bits are the operator precedence, and the low 16 are a code for the operation itself.

enum SetOperations {
    setStart         = 0 << 16 | 1,
    setEnd           = 1 << 16 | 2,
    setNegation      = 2 << 16 | 3,
    setCaseClose     = 2 << 16 | 9,
    setDifference2   = 3 << 16 | 4,    // '--' set difference operator
    setIntersection2 = 3 << 16 | 5,    // '&&' set intersection operator
    setUnion         = 4 << 16 | 6,    // implicit union of adjacent items
    setDifference1   = 4 << 16 | 7,    // '-', single dash difference op, for compatibility with old UnicodeSet.
    setIntersection1 = 4 << 16 | 8     // '&', single amp intersection op, for compatibility with old UnicodeSet.
    };

U_NAMESPACE_END
#endif   // !UCONFIG_NO_REGULAR_EXPRESSIONS
#endif   // RBBISCAN_H
Commit	Line	Data
f3c0d7a5 A	1	// © 2016 and later: Unicode, Inc. and others.
f3c0d7a5 A	2	// License & terms of use: http://www.unicode.org/copyright.html
b75a7d8f A	3	//
	4	// regexcmp.h
	5	//
2ca993e8	6	// Copyright (C) 2002-2016, International Business Machines Corporation and others.
b75a7d8f A	7	// All Rights Reserved.
	8	//
	9	// This file contains declarations for the class RegexCompile
	10	//
	11	// This class is internal to the regular expression implementation.
	12	// For the public Regular Expression API, see the file "unicode/regex.h"
	13	//
	14
	15
	16	#ifndef RBBISCAN_H
	17	#define RBBISCAN_H
	18
	19	#include "unicode/utypes.h"
	20	#if !UCONFIG_NO_REGULAR_EXPRESSIONS
	21
b75a7d8f	22	#include "unicode/parseerr.h"
2ca993e8 A	23	#include "unicode/uniset.h"
	24	#include "unicode/uobject.h"
	25	#include "unicode/utext.h"
b75a7d8f A	26	#include "uhash.h"
b75a7d8f A	27	#include "uvector.h"
b331163b	28	#include "uvectr32.h"
b75a7d8f A	29
	30
	31
	32	U_NAMESPACE_BEGIN
	33
	34
	35	//--------------------------------------------------------------------------------
	36	//
	37	// class RegexCompile Contains the regular expression compiler.
	38	//
	39	//--------------------------------------------------------------------------------
b75a7d8f A	40	struct RegexTableEl;
	41	class RegexPattern;
	42
	43
b331163b	44	class U_I18N_API RegexCompile : public UMemory {
b75a7d8f A	45	public:
b75a7d8f A	46
46f4442e A	47	enum {
	48	kStackSize = 100 // The size of the state stack for
	49	}; // pattern parsing. Corresponds roughly
	50	// to the depth of parentheses nesting
	51	// that is allowed in the rules.
	52
b75a7d8f A	53	struct RegexPatternChar {
	54	UChar32 fChar;
	55	UBool fQuoted;
	56	};
	57
	58	RegexCompile(RegexPattern *rp, UErrorCode &e);
46f4442e	59
b75a7d8f	60	void compile(const UnicodeString &pat, UParseError &pp, UErrorCode &e);
729e4ab9 A	61	void compile(UText *pat, UParseError &pp, UErrorCode &e);
729e4ab9 A	62
b75a7d8f A	63
	64	virtual ~RegexCompile();
	65
	66	void nextChar(RegexPatternChar &c); // Get the next char from the input stream.
	67
	68	static void cleanup(); // Memory cleanup
	69
	70
	71
	72	// Categories of parentheses in pattern.
	73	// The category is saved in the compile-time parentheses stack frame, and
	74	// determines the code to be generated when the matching close ) is encountered.
	75	enum EParenClass {
	76	plain = -1, // No special handling
46f4442e	77	capturing = -2,
b75a7d8f A	78	atomic = -3,
	79	lookAhead = -4,
	80	negLookAhead = -5,
	81	flags = -6,
	82	lookBehind = -7,
	83	lookBehindN = -8
	84	};
	85
	86	private:
	87
	88
46f4442e	89	UBool doParseActions(int32_t a);
b75a7d8f A	90	void error(UErrorCode e); // error reporting convenience function.
	91
	92	UChar32 nextCharLL();
	93	UChar32 peekCharLL();
b75a7d8f	94	UnicodeSet *scanProp();
46f4442e	95	UnicodeSet *scanPosixProp();
b75a7d8f A	96	void handleCloseParen();
	97	int32_t blockTopLoc(UBool reserve); // Locate a position in the compiled pattern
	98	// at the top of the just completed block
	99	// or operation, and optionally ensure that
	100	// there is space to add an opcode there.
	101	void compileSet(UnicodeSet *theSet); // Generate the compiled pattern for
	102	// a reference to a UnicodeSet.
	103	void compileInterval(int32_t InitOp, // Generate the code for a {min,max} quantifier.
	104	int32_t LoopOp);
	105	UBool compileInlineInterval(); // Generate inline code for a {min,max} quantifier
	106	void literalChar(UChar32 c); // Compile a literal char
4388f060	107	void fixLiterals(UBool split=FALSE); // Generate code for pending literal characters.
b75a7d8f A	108	void insertOp(int32_t where); // Open up a slot for a new op in the
b75a7d8f A	109	// generated code at the specified location.
b331163b A	110	void appendOp(int32_t op); // Append a new op to the compiled pattern.
	111	void appendOp(int32_t type, int32_t val); // Build & append a new op to the compiled pattern.
	112	int32_t buildOp(int32_t type, int32_t val); // Construct a new pcode instruction.
	113	int32_t allocateData(int32_t size); // Allocate space in the matcher data area.
	114	// Return index of the newly allocated data.
	115	int32_t allocateStackData(int32_t size); // Allocate space in the match back-track stack frame.
	116	// Return offset index in the frame.
b75a7d8f A	117	int32_t minMatchLength(int32_t start,
	118	int32_t end);
	119	int32_t maxMatchLength(int32_t start,
	120	int32_t end);
	121	void matchStartType();
	122	void stripNOPs();
46f4442e A	123
	124	void setEval(int32_t op);
	125	void setPushOp(int32_t op);
	126	UChar32 scanNamedChar();
	127	UnicodeSet *createSetForProperty(const UnicodeString &propName, UBool negated);
b75a7d8f	128
b331163b A	129	public: // Public for testing only.
	130	static void U_EXPORT2 findCaseInsensitiveStarters(UChar32 c, UnicodeSet *starterChars);
	131	private:
	132
b75a7d8f A	133
	134	UErrorCode *fStatus;
	135	RegexPattern *fRXPat;
	136	UParseError *fParseErr;
	137
	138	//
	139	// Data associated with low level character scanning
	140	//
729e4ab9	141	int64_t fScanIndex; // Index of current character being processed
b75a7d8f	142	// in the rule input string.
b75a7d8f A	143	UBool fQuoteMode; // Scan is in a \Q...\E quoted region
b75a7d8f A	144	UBool fInBackslashQuote; // Scan is between a '\' and the following char.
46f4442e	145	UBool fEOLComments; // When scan is just after '(?', inhibit #... to
b75a7d8f	146	// end of line comments, in favor of (?#...) comments.
729e4ab9 A	147	int64_t fLineNum; // Line number in input file.
729e4ab9 A	148	int64_t fCharNum; // Char position within the line.
b75a7d8f A	149	UChar32 fLastChar; // Previous char, needed to count CR-LF
	150	// as a single line, not two.
	151	UChar32 fPeekChar; // Saved char, if we've scanned ahead.
	152
	153
	154	RegexPatternChar fC; // Current char for parse state machine
	155	// processing.
	156
	157	//
	158	// Data for the state machine that parses the regular expression.
	159	//
	160	RegexTableEl **fStateTable; // State Transition Table for regex Rule
	161	// parsing. index by p[state][char-class]
	162
	163	uint16_t fStack[kStackSize]; // State stack, holds state pushes
73c04bcf	164	int32_t fStackPtr; // and pops as specified in the state
b75a7d8f A	165	// transition rules.
	166
	167	//
	168	// Data associated with the generation of the pcode for the match engine
	169	//
	170	int32_t fModeFlags; // Match Flags. (Case Insensitive, etc.)
73c04bcf A	171	// Always has high bit (31) set so that flag values
	172	// on the paren stack are distinguished from relocatable
	173	// pcode addresses.
b75a7d8f A	174	int32_t fNewModeFlags; // New flags, while compiling (?i, holds state
	175	// until last flag is scanned.
	176	UBool fSetModeFlag; // true for (?ismx, false for (?-ismx
	177
4388f060 A	178	UnicodeString fLiteralChars; // Literal chars or strings from the pattern are accumulated here.
	179	// Once completed, meaning that some non-literal pattern
	180	// construct is encountered, the appropriate opcodes
	181	// to match the literal will be generated, and this
	182	// string will be cleared.
b75a7d8f	183
729e4ab9 A	184	int64_t fPatternLength; // Length of the input pattern string.
729e4ab9 A	185
b75a7d8f A	186	UVector32 fParenStack; // parentheses stack. Each frame consists of
b75a7d8f A	187	// the positions of compiled pattern operations
46f4442e	188	// needing fixup, followed by negative value. The
b75a7d8f A	189	// first entry in each frame is the position of the
	190	// spot reserved for use when a quantifier
	191	// needs to add a SAVE at the start of a (block)
	192	// The negative value (-1, -2,...) indicates
	193	// the kind of paren that opened the frame. Some
	194	// need special handling on close.
	195
	196
	197	int32_t fMatchOpenParen; // The position in the compiled pattern
	198	// of the slot reserved for a state save
	199	// at the start of the most recently processed
b331163b A	200	// parenthesized block. Updated when processing
	201	// a close to the location for the corresponding open.
	202
b75a7d8f A	203	int32_t fMatchCloseParen; // The position in the pattern of the first
	204	// location after the most recently processed
	205	// parenthesized block.
	206
	207	int32_t fIntervalLow; // {lower, upper} interval quantifier values.
	208	int32_t fIntervalUpper; // Placed here temporarily, when pattern is
	209	// initially scanned. Each new interval
	210	// encountered overwrites these values.
	211	// -1 for the upper interval value means none
	212	// was specified (unlimited occurences.)
	213
729e4ab9	214	int64_t fNameStartPos; // Starting position of a \N{NAME} name in a
b75a7d8f A	215	// pattern, valid while remainder of name is
b75a7d8f A	216	// scanned.
46f4442e A	217
	218	UStack fSetStack; // Stack of UnicodeSets, used while evaluating
	219	// (at compile time) set expressions within
	220	// the pattern.
	221	UStack fSetOpStack; // Stack of pending set operators (&&, --, union)
	222
	223	UChar32 fLastSetLiteral; // The last single code point added to a set.
	224	// needed when "-y" is scanned, and we need
	225	// to turn "x-y" into a range.
b331163b A	226
	227	UnicodeString *fCaptureName; // Named Capture, the group name is built up
	228	// in this string while being scanned.
b75a7d8f A	229	};
b75a7d8f A	230
46f4442e A	231	// Constant values to be pushed onto fSetOpStack while scanning & evalueating [set expressions]
	232	// The high 16 bits are the operator precedence, and the low 16 are a code for the operation itself.
	233
	234	enum SetOperations {
	235	setStart = 0 << 16 \| 1,
	236	setEnd = 1 << 16 \| 2,
	237	setNegation = 2 << 16 \| 3,
	238	setCaseClose = 2 << 16 \| 9,
	239	setDifference2 = 3 << 16 \| 4, // '--' set difference operator
	240	setIntersection2 = 3 << 16 \| 5, // '&&' set intersection operator
	241	setUnion = 4 << 16 \| 6, // implicit union of adjacent items
	242	setDifference1 = 4 << 16 \| 7, // '-', single dash difference op, for compatibility with old UnicodeSet.
	243	setIntersection1 = 4 << 16 \| 8 // '&', single amp intersection op, for compatibility with old UnicodeSet.
	244	};
	245
b75a7d8f A	246	U_NAMESPACE_END
	247	#endif // !UCONFIG_NO_REGULAR_EXPRESSIONS
	248	#endif // RBBISCAN_H