blob: 157c6f3ed6d61905491135ce309c363d5125d289 [file] [log] [blame]
------------------------------------------------------------------------------
-- --
-- GNAT RUN-TIME COMPONENTS --
-- --
-- A D A . S T R I N G S . S E A R C H --
-- --
-- S p e c --
-- --
-- Copyright (C) 1992-2022, Free Software Foundation, 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 3, 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. --
-- --
-- As a special exception under Section 7 of GPL version 3, you are granted --
-- additional permissions described in the GCC Runtime Library Exception, --
-- version 3.1, as published by the Free Software Foundation. --
-- --
-- You should have received a copy of the GNU General Public License and --
-- a copy of the GCC Runtime Library Exception along with this program; --
-- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
-- <http://www.gnu.org/licenses/>. --
-- --
-- GNAT was originally developed by the GNAT team at New York University. --
-- Extensive contributions were provided by Ada Core Technologies Inc. --
-- --
------------------------------------------------------------------------------
-- This package contains the search functions from Ada.Strings.Fixed. They
-- are separated out because they are shared by Ada.Strings.Bounded and
-- Ada.Strings.Unbounded, and we don't want to drag in other irrelevant stuff
-- from Ada.Strings.Fixed when using the other two packages. Although user
-- programs should access these subprograms via one of the standard string
-- packages, we do not make this a private package, since ghost function
-- Match is used in the contracts of the standard string packages.
-- Preconditions in this unit are meant for analysis only, not for run-time
-- checking, so that the expected exceptions are raised. This is enforced
-- by setting the corresponding assertion policy to Ignore. Postconditions,
-- contract cases and ghost code should not be executed at runtime as well,
-- in order not to slow down the execution of these functions.
pragma Assertion_Policy (Pre => Ignore,
Post => Ignore,
Contract_Cases => Ignore,
Ghost => Ignore);
with Ada.Strings.Maps; use type Ada.Strings.Maps.Character_Mapping_Function;
package Ada.Strings.Search with SPARK_Mode is
pragma Preelaborate;
-- The ghost function Match tells whether the slice of Source starting at
-- From and of length Pattern'Length matches with Pattern with respect to
-- Mapping. Pattern should be non-empty and the considered slice should be
-- fully included in Source'Range.
function Match
(Source : String;
Pattern : String;
Mapping : Maps.Character_Mapping_Function;
From : Integer) return Boolean
is
(for all K in Pattern'Range =>
Pattern (K) = Mapping (Source (From + (K - Pattern'First))))
with
Ghost,
Pre => Mapping /= null
and then Pattern'Length > 0
and then Source'Length > 0
and then From in Source'First .. Source'Last - (Pattern'Length - 1),
Global => null;
function Match
(Source : String;
Pattern : String;
Mapping : Maps.Character_Mapping;
From : Integer) return Boolean
is
(for all K in Pattern'Range =>
Pattern (K) =
Ada.Strings.Maps.Value
(Mapping, Source (From + (K - Pattern'First))))
with
Ghost,
Pre => Pattern'Length > 0
and then Source'Length > 0
and then From in Source'First .. Source'Last - (Pattern'Length - 1),
Global => null;
function Is_Identity
(Mapping : Maps.Character_Mapping) return Boolean
with
Post => (if Is_Identity'Result then
(for all K in Character =>
Ada.Strings.Maps.Value (Mapping, K) = K)),
Global => null;
function Index
(Source : String;
Pattern : String;
Going : Direction := Forward;
Mapping : Maps.Character_Mapping := Maps.Identity) return Natural
with
Pre => Pattern'Length > 0,
Post => Index'Result in 0 | Source'Range,
Contract_Cases =>
-- If Source is the empty string, then 0 is returned
(Source'Length = 0 => Index'Result = 0,
-- If some slice of Source matches Pattern, then a valid index is
-- returned.
Source'Length > 0
and then
(for some J in
Source'First .. Source'Last - (Pattern'Length - 1) =>
Match (Source, Pattern, Mapping, J))
=>
-- The result is in the considered range of Source
Index'Result in Source'First .. Source'Last - (Pattern'Length - 1)
-- The slice beginning at the returned index matches Pattern
and then Match (Source, Pattern, Mapping, Index'Result)
-- The result is the smallest or largest index which satisfies
-- the matching, respectively when Going = Forward and Going =
-- Backward.
and then
(for all J in Source'Range =>
(if (if Going = Forward
then J <= Index'Result - 1
else J - 1 in Index'Result
.. Source'Last - Pattern'Length)
then not (Match (Source, Pattern, Mapping, J)))),
-- Otherwise, 0 is returned
others => Index'Result = 0),
Global => null;
function Index
(Source : String;
Pattern : String;
Going : Direction := Forward;
Mapping : Maps.Character_Mapping_Function) return Natural
with
Pre => Pattern'Length > 0 and then Mapping /= null,
Post => Index'Result in 0 | Source'Range,
Contract_Cases =>
-- If Source is the null string, then 0 is returned
(Source'Length = 0 => Index'Result = 0,
-- If some slice of Source matches Pattern, then a valid index is
-- returned.
Source'Length > 0 and then
(for some J in Source'First .. Source'Last - (Pattern'Length - 1) =>
Match (Source, Pattern, Mapping, J))
=>
-- The result is in the considered range of Source
Index'Result in Source'First .. Source'Last - (Pattern'Length - 1)
-- The slice beginning at the returned index matches Pattern
and then Match (Source, Pattern, Mapping, Index'Result)
-- The result is the smallest or largest index which satisfies
-- the matching, respectively when Going = Forward and Going =
-- Backward.
and then
(for all J in Source'Range =>
(if (if Going = Forward
then J <= Index'Result - 1
else J - 1 in Index'Result
.. Source'Last - Pattern'Length)
then not (Match (Source, Pattern, Mapping, J)))),
-- Otherwise, 0 is returned
others => Index'Result = 0),
Global => null;
function Index
(Source : String;
Set : Maps.Character_Set;
Test : Membership := Inside;
Going : Direction := Forward) return Natural
with
Post => Index'Result in 0 | Source'Range,
Contract_Cases =>
-- If no character of Source satisfies the property Test on Set, then
-- 0 is returned.
((for all C of Source =>
(Test = Inside) /= Ada.Strings.Maps.Is_In (C, Set))
=>
Index'Result = 0,
-- Otherwise, an index in the range of Source is returned
others =>
-- The result is in the range of Source
Index'Result in Source'Range
-- The character at the returned index satisfies the property
-- Test on Set.
and then (Test = Inside)
= Ada.Strings.Maps.Is_In (Source (Index'Result), Set)
-- The result is the smallest or largest index which satisfies
-- the property, respectively when Going = Forward and Going =
-- Backward.
and then
(for all J in Source'Range =>
(if J /= Index'Result
and then (J < Index'Result) = (Going = Forward)
then (Test = Inside)
/= Ada.Strings.Maps.Is_In (Source (J), Set)))),
Global => null;
function Index
(Source : String;
Pattern : String;
From : Positive;
Going : Direction := Forward;
Mapping : Maps.Character_Mapping := Maps.Identity) return Natural
with
Pre => Pattern'Length > 0
and then (if Source'Length > 0 then From in Source'Range),
Post => Index'Result in 0 | Source'Range,
Contract_Cases =>
-- If Source is the empty string, then 0 is returned
(Source'Length = 0 => Index'Result = 0,
-- If some slice of Source matches Pattern, then a valid index is
-- returned.
Source'Length > 0
and then
(for some J in
(if Going = Forward then From else Source'First)
.. (if Going = Forward then Source'Last else From)
- (Pattern'Length - 1) =>
Match (Source, Pattern, Mapping, J))
=>
-- The result is in the considered range of Source
Index'Result in
(if Going = Forward then From else Source'First)
.. (if Going = Forward then Source'Last else From)
- (Pattern'Length - 1)
-- The slice beginning at the returned index matches Pattern
and then Match (Source, Pattern, Mapping, Index'Result)
-- The result is the smallest or largest index which satisfies
-- the matching, respectively when Going = Forward and Going =
-- Backward.
and then
(for all J in Source'Range =>
(if (if Going = Forward
then J in From .. Index'Result - 1
else J - 1 in Index'Result
.. From - Pattern'Length)
then not (Match (Source, Pattern, Mapping, J)))),
-- Otherwise, 0 is returned
others => Index'Result = 0),
Global => null;
function Index
(Source : String;
Pattern : String;
From : Positive;
Going : Direction := Forward;
Mapping : Maps.Character_Mapping_Function) return Natural
with
Pre => Pattern'Length > 0
and then Mapping /= null
and then (if Source'Length > 0 then From in Source'Range),
Post => Index'Result in 0 | Source'Range,
Contract_Cases =>
-- If Source is the empty string, then 0 is returned
(Source'Length = 0 => Index'Result = 0,
-- If some slice of Source matches Pattern, then a valid index is
-- returned.
Source'Length > 0
and then
(for some J in
(if Going = Forward then From else Source'First)
.. (if Going = Forward then Source'Last else From)
- (Pattern'Length - 1) =>
Match (Source, Pattern, Mapping, J))
=>
-- The result is in the considered range of Source
Index'Result in
(if Going = Forward then From else Source'First)
.. (if Going = Forward then Source'Last else From)
- (Pattern'Length - 1)
-- The slice beginning at the returned index matches Pattern
and then Match (Source, Pattern, Mapping, Index'Result)
-- The result is the smallest or largest index which satisfies
-- the matching, respectively when Going = Forward and Going =
-- Backwards.
and then
(for all J in Source'Range =>
(if (if Going = Forward
then J in From .. Index'Result - 1
else J - 1 in Index'Result
.. From - Pattern'Length)
then not (Match (Source, Pattern, Mapping, J)))),
-- Otherwise, 0 is returned
others => Index'Result = 0),
Global => null;
function Index
(Source : String;
Set : Maps.Character_Set;
From : Positive;
Test : Membership := Inside;
Going : Direction := Forward) return Natural
with
Pre => (if Source'Length > 0 then From in Source'Range),
Post => Index'Result in 0 | Source'Range,
Contract_Cases =>
-- If Source is the empty string, or no character of the considered
-- slice of Source satisfies the property Test on Set, then 0 is
-- returned.
(Source'Length = 0
or else
(for all J in Source'Range =>
(if J = From or else (J > From) = (Going = Forward) then
(Test = Inside) /= Ada.Strings.Maps.Is_In (Source (J), Set)))
=>
Index'Result = 0,
-- Otherwise, an index in the considered range of Source is returned
others =>
-- The result is in the considered range of Source
Index'Result in Source'Range
and then (Index'Result = From
or else
(Index'Result > From) = (Going = Forward))
-- The character at the returned index satisfies the property
-- Test on Set
and then
(Test = Inside)
= Ada.Strings.Maps.Is_In (Source (Index'Result), Set)
-- The result is the smallest or largest index which satisfies
-- the property, respectively when Going = Forward and Going =
-- Backward.
and then
(for all J in Source'Range =>
(if J /= Index'Result
and then (J < Index'Result) = (Going = Forward)
and then (J = From
or else (J > From) = (Going = Forward))
then (Test = Inside)
/= Ada.Strings.Maps.Is_In (Source (J), Set)))),
Global => null;
function Index_Non_Blank
(Source : String;
Going : Direction := Forward) return Natural
with
Post => Index_Non_Blank'Result in 0 | Source'Range,
Contract_Cases =>
-- If all characters of Source are Space characters, then 0 is
-- returned.
((for all C of Source => C = ' ') => Index_Non_Blank'Result = 0,
-- Otherwise, a valid index is returned
others =>
-- The result is in the range of Source
Index_Non_Blank'Result in Source'Range
-- The character at the returned index is not a Space character
and then Source (Index_Non_Blank'Result) /= ' '
-- The result is the smallest or largest index which is not a
-- Space character, respectively when Going = Forward and
-- Going = Backward.
and then
(for all J in Source'Range =>
(if J /= Index_Non_Blank'Result
and then (J < Index_Non_Blank'Result)
= (Going = Forward)
then Source (J) = ' '))),
Global => null;
function Index_Non_Blank
(Source : String;
From : Positive;
Going : Direction := Forward) return Natural
with
Pre => (if Source'Length /= 0 then From in Source'Range),
Post => Index_Non_Blank'Result in 0 | Source'Range,
Contract_Cases =>
-- If Source is the null string, or all characters in the considered
-- slice of Source are Space characters, then 0 is returned.
(Source'Length = 0
or else
(for all J in Source'Range =>
(if J = From or else (J > From) = (Going = Forward) then
Source (J) = ' '))
=>
Index_Non_Blank'Result = 0,
-- Otherwise, a valid index is returned
others =>
-- The result is in the considered range of Source
Index_Non_Blank'Result in Source'Range
and then (Index_Non_Blank'Result = From
or else (Index_Non_Blank'Result > From)
= (Going = Forward))
-- The character at the returned index is not a Space character
and then Source (Index_Non_Blank'Result) /= ' '
-- The result is the smallest or largest index which is not a
-- Space character, respectively when Going = Forward and
-- Going = Backward.
and then
(for all J in Source'Range =>
(if J /= Index_Non_Blank'Result
and then (J < Index_Non_Blank'Result)
= (Going = Forward)
and then (J = From or else (J > From)
= (Going = Forward))
then Source (J) = ' '))),
Global => null;
function Count
(Source : String;
Pattern : String;
Mapping : Maps.Character_Mapping := Maps.Identity) return Natural
with
Pre => Pattern'Length > 0,
Global => null;
function Count
(Source : String;
Pattern : String;
Mapping : Maps.Character_Mapping_Function) return Natural
with
Pre => Pattern'Length > 0 and then Mapping /= null,
Global => null;
function Count
(Source : String;
Set : Maps.Character_Set) return Natural
with
Global => null;
procedure Find_Token
(Source : String;
Set : Maps.Character_Set;
From : Positive;
Test : Membership;
First : out Positive;
Last : out Natural)
with
Pre => (if Source'Length /= 0 then From in Source'Range),
Contract_Cases =>
-- If Source is the empty string, or if no character of the considered
-- slice of Source satisfies the property Test on Set, then First is
-- set to From and Last is set to 0.
(Source'Length = 0
or else
(for all C of Source (From .. Source'Last) =>
(Test = Inside) /= Ada.Strings.Maps.Is_In (C, Set))
=>
First = From and then Last = 0,
-- Otherwise, First and Last are set to valid indexes
others =>
-- First and Last are in the considered range of Source
First in From .. Source'Last
and then Last in First .. Source'Last
-- No character between From and First satisfies the property Test
-- on Set.
and then
(for all C of Source (From .. First - 1) =>
(Test = Inside) /= Ada.Strings.Maps.Is_In (C, Set))
-- All characters between First and Last satisfy the property Test
-- on Set.
and then
(for all C of Source (First .. Last) =>
(Test = Inside) = Ada.Strings.Maps.Is_In (C, Set))
-- If Last is not Source'Last, then the character at position
-- Last + 1 does not satify the property Test on Set.
and then
(if Last < Source'Last
then (Test = Inside)
/= Ada.Strings.Maps.Is_In (Source (Last + 1), Set))),
Global => null;
procedure Find_Token
(Source : String;
Set : Maps.Character_Set;
Test : Membership;
First : out Positive;
Last : out Natural)
with
Pre => Source'First > 0,
Contract_Cases =>
-- If Source is the empty string, or if no character of Source
-- satisfies the property Test on Set, then First is set to From
-- and Last is set to 0.
(Source'Length = 0
or else
(for all C of Source =>
(Test = Inside) /= Ada.Strings.Maps.Is_In (C, Set))
=>
First = Source'First and then Last = 0,
-- Otherwise, First and Last are set to valid indexes
others =>
-- First and Last are in the considered range of Source
First in Source'Range
and then Last in First .. Source'Last
-- No character before First satisfies the property Test on Set
and then
(for all C of Source (Source'First .. First - 1) =>
(Test = Inside) /= Ada.Strings.Maps.Is_In (C, Set))
-- All characters between First and Last satisfy the property Test
-- on Set.
and then
(for all C of Source (First .. Last) =>
(Test = Inside) = Ada.Strings.Maps.Is_In (C, Set))
-- If Last is not Source'Last, then the character at position
-- Last + 1 does not satify the property Test on Set.
and then
(if Last < Source'Last
then (Test = Inside)
/= Ada.Strings.Maps.Is_In (Source (Last + 1), Set))),
Global => null;
end Ada.Strings.Search;