------------------------------------------------------------------------------ -- -- -- GNAT LIBRARY COMPONENTS -- -- -- -- G N A T . R E G P A T -- -- -- -- S p e c -- -- -- -- Copyright (C) 1986 by University of Toronto. -- -- Copyright (C) 1996-2004 Ada Core Technologies, Inc. -- -- -- -- GNAT is free software; you can redistribute it and/or modify it under -- -- terms of the GNU General Public License as published by the Free Soft- -- -- ware Foundation; either version 2, or (at your option) any later ver- -- -- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- -- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -- -- for more details. You should have received a copy of the GNU General -- -- Public License distributed with GNAT; see file COPYING. If not, write -- -- to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, -- -- MA 02111-1307, USA. -- -- -- -- As a special exception, if other files instantiate generics from this -- -- unit, or you link this unit with other files to produce an executable, -- -- this unit does not by itself cause the resulting executable to be -- -- covered by the GNU General Public License. This exception does not -- -- however invalidate any other reasons why the executable file might be -- -- covered by the GNU Public License. -- -- -- -- GNAT was originally developed by the GNAT team at New York University. -- -- Extensive contributions were provided by Ada Core Technologies Inc. -- -- -- ------------------------------------------------------------------------------ -- This package implements roughly the same set of regular expressions as -- are available in the Perl or Python programming languages. -- This is an extension of the original V7 style regular expression library -- written in C by Henry Spencer. Apart from the translation to Ada, the -- interface has been considerably changed to use the Ada String type -- instead of C-style nul-terminated strings. ------------------------------------------------------------ -- Summary of Pattern Matching Packages in GNAT Hierarchy -- ------------------------------------------------------------ -- There are three related packages that perform pattern maching functions. -- the following is an outline of these packages, to help you determine -- which is best for your needs. -- GNAT.Regexp (files g-regexp.ads/g-regexp.adb) -- This is a simple package providing Unix-style regular expression -- matching with the restriction that it matches entire strings. It -- is particularly useful for file name matching, and in particular -- it provides "globbing patterns" that are useful in implementing -- unix or DOS style wild card matching for file names. -- GNAT.Regpat (files g-regpat.ads/g-regpat.adb) -- This is a more complete implementation of Unix-style regular -- expressions, copied from the Perl regular expression engine, -- written originally in C by Henry Spencer. It is functionally the -- same as that library. -- GNAT.Spitbol.Patterns (files g-spipat.ads/g-spipat.adb) -- This is a completely general pattern matching package based on the -- pattern language of SNOBOL4, as implemented in SPITBOL. The pattern -- language is modeled on context free grammars, with context sensitive -- extensions that provide full (type 0) computational capabilities. package GNAT.Regpat is pragma Preelaborate (Regpat); -- The grammar is the following: -- regexp ::= expr -- ::= ^ expr -- anchor at the beginning of string -- ::= expr $ -- anchor at the end of string -- expr ::= term -- ::= term | term -- alternation (term or term ...) -- term ::= item -- ::= item item ... -- concatenation (item then item) -- item ::= elmt -- match elmt -- ::= elmt * -- zero or more elmt's -- ::= elmt + -- one or more elmt's -- ::= elmt ? -- matches elmt or nothing -- ::= elmt *? -- zero or more times, minimum number -- ::= elmt +? -- one or more times, minimum number -- ::= elmt ?? -- zero or one time, minimum number -- ::= elmt { num } -- matches elmt exactly num times -- ::= elmt { num , } -- matches elmt at least num times -- ::= elmt { num , num2 } -- matches between num and num2 times -- ::= elmt { num }? -- matches elmt exactly num times -- ::= elmt { num , }? -- matches elmt at least num times -- non-greedy version -- ::= elmt { num , num2 }? -- matches between num and num2 times -- non-greedy version -- elmt ::= nchr -- matches given character -- ::= [range range ...] -- matches any character listed -- ::= [^ range range ...] -- matches any character not listed -- ::= . -- matches any single character -- -- except newlines -- ::= ( expr ) -- parens used for grouping -- ::= \ num -- reference to num-th parenthesis -- range ::= char - char -- matches chars in given range -- ::= nchr -- ::= [: posix :] -- any character in the POSIX range -- ::= [:^ posix :] -- not in the POSIX range -- posix ::= alnum -- alphanumeric characters -- ::= alpha -- alphabetic characters -- ::= ascii -- ascii characters (0 .. 127) -- ::= cntrl -- control chars (0..31, 127..159) -- ::= digit -- digits ('0' .. '9') -- ::= graph -- graphic chars (32..126, 160..255) -- ::= lower -- lower case characters -- ::= print -- printable characters (32..127) -- ::= punct -- printable, except alphanumeric -- ::= space -- space characters -- ::= upper -- upper case characters -- ::= word -- alphanumeric characters -- ::= xdigit -- hexadecimal chars (0..9, a..f) -- char ::= any character, including special characters -- ASCII.NUL is not supported. -- nchr ::= any character except \()[].*+?^ or \char to match char -- \n means a newline (ASCII.LF) -- \t means a tab (ASCII.HT) -- \r means a return (ASCII.CR) -- \b matches the empty string at the beginning or end of a -- word. A word is defined as a set of alphanumerical -- characters (see \w below). -- \B matches the empty string only when *not* at the -- beginning or end of a word. -- \d matches any digit character ([0-9]) -- \D matches any non digit character ([^0-9]) -- \s matches any white space character. This is equivalent -- to [ \t\n\r\f\v] (tab, form-feed, vertical-tab,... -- \S matches any non-white space character. -- \w matches any alphanumeric character or underscore. -- This include accented letters, as defined in the -- package Ada.Characters.Handling. -- \W matches any non-alphanumeric character. -- \A match the empty string only at the beginning of the -- string, whatever flags are used for Compile (the -- behavior of ^ can change, see Regexp_Flags below). -- \G match the empty string only at the end of the -- string, whatever flags are used for Compile (the -- behavior of $ can change, see Regexp_Flags below). -- ... ::= is used to indication repetition (one or more terms) -- Embedded newlines are not matched by the ^ operator. -- It is possible to retrieve the substring matched a parenthesis -- expression. Although the depth of parenthesis is not limited in the -- regexp, only the first 9 substrings can be retrieved. -- The highest value possible for the arguments to the curly operator ({}) -- are given by the constant Max_Curly_Repeat below. -- The operators '*', '+', '?' and '{}' always match the longest possible -- substring. They all have a non-greedy version (with an extra ? after the -- operator), which matches the shortest possible substring. -- For instance: -- regexp="<.*>" string="<h1>title</h1>" matches="<h1>title</h1>" -- regexp="<.*?>" string="<h1>title</h1>" matches="<h1>" -- -- '{' and '}' are only considered as special characters if they appear -- in a substring that looks exactly like '{n}', '{n,m}' or '{n,}', where -- n and m are digits. No space is allowed. In other contexts, the curly -- braces will simply be treated as normal characters. -- Compiling Regular Expressions -- ============================= -- To use this package, you first need to compile the regular expression -- (a string) into a byte-code program, in a Pattern_Matcher structure. -- This first step checks that the regexp is valid, and optimizes the -- matching algorithms of the second step. -- Two versions of the Compile subprogram are given: one in which this -- package will compute itself the best possible size to allocate for the -- byte code; the other where you must allocate enough memory yourself. An -- exception is raised if there is not enough memory. -- declare -- Regexp : String := "a|b"; -- Matcher : Pattern_Matcher := Compile (Regexp); -- -- The size for matcher is automatically allocated -- Matcher2 : Pattern_Matcher (1000); -- -- Some space is allocated directly. -- begin -- Compile (Matcher2, Regexp); -- ... -- end; -- Note that the second version is significantly faster, since with the -- first version the regular expression has in fact to be compiled twice -- (first to compute the size, then to generate the byte code). -- Note also that you can not use the function version of Compile if you -- specify the size of the Pattern_Matcher, since the discriminants will -- most probably be different and you will get a Constraint_Error -- Matching Strings -- ================ -- Once the regular expression has been compiled, you can use it as often -- as needed to match strings. -- Several versions of the Match subprogram are provided, with different -- parameters and return results. -- See the description under each of these subprograms. -- Here is a short example showing how to get the substring matched by -- the first parenthesis pair. -- declare -- Matches : Match_Array (0 .. 1); -- Regexp : String := "a(b|c)d"; -- Str : String := "gacdg"; -- begin -- Match (Compile (Regexp), Str, Matches); -- return Str (Matches (1).First .. Matches (1).Last); -- -- returns 'c' -- end; -- Finding all occurrences -- ======================= -- Finding all the occurrences of a regular expression in a string cannot -- be done by simply passing a slice of the string. This wouldn't work for -- anchored regular expressions (the ones starting with "^" or ending with -- "$"). -- Instead, you need to use the last parameter to Match (Data_First), as in -- the following loop: -- declare -- Str : String := -- "-- first line" & ASCII.LF & "-- second line"; -- Matches : Match_array (0 .. 0); -- Regexp : Pattern_Matcher := Compile ("^--", Multiple_Lines); -- Current : Natural := Str'First; -- begin -- loop -- Match (Regexp, Str, Matches, Current); -- exit when Matches (0) = No_Match; -- -- -- Process the match at position Matches (0).First -- -- Current := Matches (0).Last + 1; -- end loop; -- end; -- String Substitution -- =================== -- No subprogram is currently provided for string substitution. -- However, this is easy to simulate with the parenthesis groups, as -- shown below. -- This example swaps the first two words of the string: -- declare -- Regexp : String := "([a-z]+) +([a-z]+)"; -- Str : String := " first second third "; -- Matches : Match_Array (0 .. 2); -- begin -- Match (Compile (Regexp), Str, Matches); -- return Str (Str'First .. Matches (1).First - 1) -- & Str (Matches (2).First .. Matches (2).Last) -- & " " -- & Str (Matches (1).First .. Matches (1).Last) -- & Str (Matches (2).Last + 1 .. Str'Last); -- -- returns " second first third " -- end; --------------- -- Constants -- --------------- Expression_Error : exception; -- This exception is raised when trying to compile an invalid -- regular expression. All subprograms taking an expression -- as parameter may raise Expression_Error. Max_Paren_Count : constant := 255; -- Maximum number of parenthesis in a regular expression. -- This is limited by the size of a Character, as found in the -- byte-compiled version of regular expressions. Max_Curly_Repeat : constant := 32767; -- Maximum number of repetition for the curly operator. -- The digits in the {n}, {n,} and {n,m } operators can not be higher -- than this constant, since they have to fit on two characters in the -- byte-compiled version of regular expressions. Max_Program_Size : constant := 2**15 - 1; -- Maximum size that can be allocated for a program type Program_Size is range 0 .. Max_Program_Size; for Program_Size'Size use 16; -- Number of bytes allocated for the byte-compiled version of a regular -- expression. The size required depends on the complexity of the regular -- expression in a complex manner that is undocumented (other than in the -- body of the Compile procedure). Normally the size is automatically set -- and the programmer need not be concerned about it. There are two -- exceptions to this. First in the calls to Match, it is possible to -- specify a non-zero size that is known to be large enough. This can -- slightly increase the efficiency by avoiding a copy. Second, in the -- case of calling compile, it is possible using the procedural form -- of Compile to use a single Pattern_Matcher variable for several -- different expressions by setting its size sufficiently large. Auto_Size : constant := 0; -- Used in calls to Match to indicate that the Size should be set to -- a value appropriate to the expression being used automatically. type Regexp_Flags is mod 256; for Regexp_Flags'Size use 8; -- Flags that can be given at compile time to specify default -- properties for the regular expression. No_Flags : constant Regexp_Flags; Case_Insensitive : constant Regexp_Flags; -- The automaton is optimized so that the matching is done in a case -- insensitive manner (upper case characters and lower case characters -- are all treated the same way). Single_Line : constant Regexp_Flags; -- Treat the Data we are matching as a single line. This means that -- ^ and $ will ignore \n (unless Multiple_Lines is also specified), -- and that '.' will match \n. Multiple_Lines : constant Regexp_Flags; -- Treat the Data as multiple lines. This means that ^ and $ will also -- match on internal newlines (ASCII.LF), in addition to the beginning -- and end of the string. -- -- This can be combined with Single_Line. ----------------- -- Match_Array -- ----------------- subtype Match_Count is Natural range 0 .. Max_Paren_Count; type Match_Location is record First : Natural := 0; Last : Natural := 0; end record; type Match_Array is array (Match_Count range <>) of Match_Location; -- The substring matching a given pair of parenthesis. -- Index 0 is the whole substring that matched the full regular -- expression. -- -- For instance, if your regular expression is something like: -- "a(b*)(c+)", then Match_Array(1) will be the indexes of the -- substring that matched "b*" and Match_Array(2) will be the substring -- that matched "c+". -- -- The number of parenthesis groups that can be retrieved is unlimited, -- and all the Match subprograms below can use a Match_Array of any size. -- Indexes that do not have any matching parenthesis are set to -- No_Match. No_Match : constant Match_Location := (First => 0, Last => 0); -- The No_Match constant is (0, 0) to differentiate between -- matching a null string at position 1, which uses (1, 0) -- and no match at all. --------------------------------- -- Pattern_Matcher Compilation -- --------------------------------- -- The subprograms here are used to precompile regular expressions -- for use in subsequent Match calls. Precompilation improves -- efficiency if the same regular expression is to be used in -- more than one Match call. type Pattern_Matcher (Size : Program_Size) is private; -- Type used to represent a regular expression compiled into byte code Never_Match : constant Pattern_Matcher; -- A regular expression that never matches anything function Compile (Expression : String; Flags : Regexp_Flags := No_Flags) return Pattern_Matcher; -- Compile a regular expression into internal code -- -- Raises Expression_Error if Expression is not a legal regular expression -- -- The appropriate size is calculated automatically to correspond to the -- provided expression. This is the normal default method of compilation. -- Note that it is generally not possible to assign the result of two -- different calls to this Compile function to the same Pattern_Matcher -- variable, since the sizes will differ. -- -- Flags is the default value to use to set properties for Expression -- (e.g. case sensitivity,...). procedure Compile (Matcher : out Pattern_Matcher; Expression : String; Final_Code_Size : out Program_Size; Flags : Regexp_Flags := No_Flags); -- Compile a regular expression into into internal code -- This procedure is significantly faster than the Compile function -- since it avoids the extra step of precomputing the required size. -- -- However, it requires the user to provide a Pattern_Matcher variable -- whose size is preset to a large enough value. One advantage of this -- approach, in addition to the improved efficiency, is that the same -- Pattern_Matcher variable can be used to hold the compiled code for -- several different regular expressions by setting a size that is -- large enough to accomodate all possibilities. -- -- In this version of the procedure call, the actual required code -- size is returned. Also if Matcher.Size is zero on entry, then the -- resulting code is not stored. A call with Matcher.Size set to Auto_Size -- can thus be used to determine the space required for compiling the -- given regular expression. -- -- This function raises Storage_Error if Matcher is too small to hold -- the resulting code (i.e. Matcher.Size has too small a value). -- -- Expression_Error is raised if the string Expression does not contain -- a valid regular expression. -- -- Flags is the default value to use to set properties for Expression (case -- sensitivity,...). procedure Compile (Matcher : out Pattern_Matcher; Expression : String; Flags : Regexp_Flags := No_Flags); -- Same procedure as above, expect it does not return the final -- program size, and Matcher.Size cannot be Auto_Size. function Paren_Count (Regexp : Pattern_Matcher) return Match_Count; pragma Inline (Paren_Count); -- Return the number of parenthesis pairs in Regexp. -- -- This is the maximum index that will be filled if a Match_Array is -- used as an argument to Match. -- -- Thus, if you want to be sure to get all the parenthesis, you should -- do something like: -- -- declare -- Regexp : Pattern_Matcher := Compile ("a(b*)(c+)"); -- Matched : Match_Array (0 .. Paren_Count (Regexp)); -- begin -- Match (Regexp, "a string", Matched); -- end; ------------- -- Quoting -- ------------- function Quote (Str : String) return String; -- Return a version of Str so that every special character is quoted. -- The resulting string can be used in a regular expression to match -- exactly Str, whatever character was present in Str. -------------- -- Matching -- -------------- -- The Match subprograms are given a regular expression in string -- form, and perform the corresponding match. The following parameters -- are present in all forms of the Match call. -- Expression contains the regular expression to be matched as a string -- Data contains the string to be matched -- Data_First is the lower bound for the match, i.e. Data (Data_First) -- will be the first character to be examined. If Data_First is set to -- the special value of -1 (the default), then the first character to -- be examined is Data (Data_First). However, the regular expression -- character ^ (start of string) still refers to the first character -- of the full string (Data (Data'First)), which is why there is a -- separate mechanism for specifying Data_First. -- Data_Last is the upper bound for the match, i.e. Data (Data_Last) -- will be the last character to be examined. If Data_Last is set to -- the special value of Positive'Last (the default), then the last -- character to be examined is Data (Data_Last). However, the regular -- expression character $ (end of string) still refers to the last -- character of the full string (Data (Data'Last)), which is why there -- is a separate mechanism for specifying Data_Last. -- Note: the use of Data_First and Data_Last is not equivalent to -- simply passing a slice as Expression because of the handling of -- regular expression characters ^ and $. -- Size is the size allocated for the compiled byte code. Normally -- this is defaulted to Auto_Size which means that the appropriate -- size is allocated automatically. It is possible to specify an -- explicit size, which must be sufficiently large. This slightly -- increases the efficiency by avoiding the extra step of computing -- the appropriate size. -- The following exceptions can be raised in calls to Match -- -- Storage_Error is raised if a non-zero value is given for Size -- and it is too small to hold the compiled byte code. -- -- Expression_Error is raised if the given expression is not a legal -- regular expression. procedure Match (Expression : String; Data : String; Matches : out Match_Array; Size : Program_Size := Auto_Size; Data_First : Integer := -1; Data_Last : Positive := Positive'Last); -- This version returns the result of the match stored in Match_Array. -- At most Matches'Length parenthesis are returned. function Match (Expression : String; Data : String; Size : Program_Size := Auto_Size; Data_First : Integer := -1; Data_Last : Positive := Positive'Last) return Natural; -- This version returns the position where Data matches, or if there is -- no match, then the value Data'First - 1. function Match (Expression : String; Data : String; Size : Program_Size := Auto_Size; Data_First : Integer := -1; Data_Last : Positive := Positive'Last) return Boolean; -- This version returns True if the match succeeds, False otherwise ------------------------------------------------ -- Matching a Pre-Compiled Regular Expression -- ------------------------------------------------ -- The following functions are significantly faster if you need to reuse -- the same regular expression multiple times, since you only have to -- compile it once. For these functions you must first compile the -- expression with a call to Compile as previously described. -- The parameters Data, Data_First and Data_Last are as described -- in the previous section. function Match (Self : Pattern_Matcher; Data : String; Data_First : Integer := -1; Data_Last : Positive := Positive'Last) return Natural; -- Match Data using the given pattern matcher. Returns the position -- where Data matches, or (Data'First - 1) if there is no match. function Match (Self : Pattern_Matcher; Data : String; Data_First : Integer := -1; Data_Last : Positive := Positive'Last) return Boolean; -- Return True if Data matches using the given pattern matcher. pragma Inline (Match); -- All except the last one below procedure Match (Self : Pattern_Matcher; Data : String; Matches : out Match_Array; Data_First : Integer := -1; Data_Last : Positive := Positive'Last); -- Match Data using the given pattern matcher and store result in Matches. -- The expression matches if Matches (0) /= No_Match. -- -- At most Matches'Length parenthesis are returned. ----------- -- Debug -- ----------- procedure Dump (Self : Pattern_Matcher); -- Dump the compiled version of the regular expression matched by Self -------------------------- -- Private Declarations -- -------------------------- private subtype Pointer is Program_Size; -- The Pointer type is used to point into Program_Data -- Note that the pointer type is not necessarily 2 bytes -- although it is stored in the program using 2 bytes type Program_Data is array (Pointer range <>) of Character; Program_First : constant := 1; -- The "internal use only" fields in regexp are present to pass -- info from compile to execute that permits the execute phase -- to run lots faster on simple cases. They are: -- First character that must begin a match or ASCII.Nul -- Anchored true iff match must start at beginning of line -- Must_Have pointer to string that match must include or null -- Must_Have_Length length of Must_Have string -- First and Anchored permit very fast decisions on suitable -- starting points for a match, cutting down the work a lot. -- Must_Have permits fast rejection of lines that cannot possibly -- match. -- The Must_Have tests are costly enough that Optimize -- supplies a Must_Have only if the r.e. contains something potentially -- expensive (at present, the only such thing detected is * or + -- at the start of the r.e., which can involve a lot of backup). -- The length is supplied because the test in Execute needs it -- and Optimize is computing it anyway. -- The initialization is meant to fail-safe in case the user of this -- package tries to use an uninitialized matcher. This takes advantage -- of the knowledge that ASCII.Nul translates to the end-of-program (EOP) -- instruction code of the state machine. No_Flags : constant Regexp_Flags := 0; Case_Insensitive : constant Regexp_Flags := 1; Single_Line : constant Regexp_Flags := 2; Multiple_Lines : constant Regexp_Flags := 4; type Pattern_Matcher (Size : Pointer) is record First : Character := ASCII.NUL; -- internal use only Anchored : Boolean := False; -- internal use only Must_Have : Pointer := 0; -- internal use only Must_Have_Length : Natural := 0; -- internal use only Paren_Count : Natural := 0; -- # paren groups Flags : Regexp_Flags := No_Flags; Program : Program_Data (Program_First .. Size) := (others => ASCII.NUL); end record; Never_Match : constant Pattern_Matcher := (0, ASCII.NUL, False, 0, 0, 0, No_Flags, (others => ASCII.NUL)); end GNAT.Regpat;