-- S p e c --
-- --
-- Copyright (C) 1986 by University of Toronto. --
--- Copyright (C) 1996-2006, AdaCore --
+-- Copyright (C) 1996-2008, AdaCore --
-- --
-- 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- --
-- interface has been considerably changed to use the Ada String type
-- instead of C-style nul-terminated strings.
+-- See file s-regpat.ads for full documentation of the interface
+
------------------------------------------------------------
-- Summary of Pattern Matching Packages in GNAT Hierarchy --
------------------------------------------------------------
--- There are three related packages that perform pattern maching functions.
+-- There are three related packages that perform pattern matching 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)
+-- GNAT.Regexp (files g-regexp.ads/s-regexp.ads/s-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)
+-- GNAT.Regpat (files g-regpat.ads/s-regpat.ads/s-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
-- language is modeled on context free grammars, with context sensitive
-- extensions that provide full (type 0) computational capabilities.
-package GNAT.Regpat is
- pragma Preelaborate;
-
- -- 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 cannot 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 cannot 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. The lower bound of
- -- Matches is required to be zero.
- --
- -- 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));
+with System.Regpat;
-end GNAT.Regpat;
+package GNAT.Regpat renames System.Regpat;
OSDN Git Service
