Format: https://www.debian.org/doc/packaging-manuals/copyright-format/1.0/
Upstream-Name: libre-engine-re2-perl
Source: <url://example.com>
#
# Please double check copyright with the licensecheck(1) command.

Files:     Changes
           MANIFEST
           MANIFEST.SKIP
           META.json
           META.yml
           Makefile.PL
           RE2.xs
           TODO
           compat-cophh.h
           compat-rx.h
           re2/.hgignore
           re2/AUTHORS
           re2/CONTRIBUTORS
           re2/README
           re2/libre2.symbols
           re2/libre2.symbols.darwin
           re2/re2/Makefile
           re2/re2/perl_groups.cc
           re2/re2/unicode_casefold.cc
           re2/re2/unicode_groups.cc
           re2/runtests
           re2/testinstall.cc
           re2/util/hash.cc
           re2_xs.cc
           re2_xs.h
           t/00.compile.t
           t/00.re2-tests.t
           t/01.basic.t
           t/02.chars.t
           t/03.modifiers.t
           t/04.multiline.t
           t/05.url.t
           t/06.matchrange.t
           t/07.utf8.t
           t/08.pos.t
           t/09.mem.t
           t/10.options.t
           t/ree-pcre/capture.t
           t/ree-pcre/import.t
           t/ree-pcre/match.t
           t/ree-pcre/qr.t
           t/ree-pcre/s.t
           t/ree-pcre/split-null.t
           t/ree-pcre/split.t
           t/ree-pcre/subexp.t
           t/ree-pcre/unimport.t
Copyright: __NO_COPYRIGHT_NOR_LICENSE__
License:   __NO_COPYRIGHT_NOR_LICENSE__

Files:     re2/Makefile
           re2/re2/bitstate.cc
           re2/re2/filtered_re2.cc
           re2/re2/make_unicode_casefold.py
           re2/re2/make_unicode_groups.py
           re2/re2/nfa.cc
           re2/re2/onepass.cc
           re2/re2/prefilter.cc
           re2/re2/prefilter_tree.cc
           re2/re2/re2.h
           re2/re2/regexp.h
           re2/re2/set.cc
           re2/re2/set.h
           re2/re2/testing/backtrack.cc
           re2/re2/testing/dfa_test.cc
           re2/re2/testing/exhaustive_tester.h
           re2/re2/testing/filtered_re2_test.cc
           re2/re2/testing/mimics_pcre_test.cc
           re2/re2/testing/null_walker.cc
           re2/re2/testing/possible_match_test.cc
           re2/re2/testing/required_prefix_test.cc
           re2/re2/testing/search_test.cc
           re2/re2/testing/set_test.cc
           re2/re2/testing/unicode_test.py
           re2/re2/unicode.py
           re2/re2/variadic_function.h
           re2/util/arena.cc
           re2/util/atomicops.h
           re2/util/benchmark.cc
           re2/util/benchmark.h
           re2/util/random.cc
           re2/util/random.h
           re2/util/stringpiece.cc
           re2/util/stringprintf.cc
           re2/util/strutil.cc
           re2/util/test.cc
           re2/util/test.h
           re2/util/thread.cc
           re2/util/thread.h
           re2/util/util.h
           re2/util/valgrind.cc
Copyright: 1999-2010 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.

Files:     re2/re2/testing/exhaustive1_test.cc
           re2/re2/testing/exhaustive2_test.cc
           re2/re2/testing/exhaustive3_test.cc
           re2/re2/testing/exhaustive_test.cc
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Exhaustive testing of regular expression matching.

Files:     re2/re2/testing/string_generator.cc
           re2/re2/testing/string_generator.h
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 String generator: generates all possible strings of up to
 maxlen letters using the set of letters in alpha.
 Fetch strings using a Java-like Next()/HasNext() interface.

Files:     re2/re2/testing/parse_test.cc
           re2/re2/testing/regexp_test.cc
Copyright: 2006 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Test parse.cc, dump.cc, and tostring.cc.

Files:     lib/re/engine/RE2.pm
Copyright: 2007 E<AElig>var ArnfjE<ouml>rE<eth> Bjarmason.
           2010 David Leadbeater.
License:   Perl
 Based on L<re::engine::PCRE>:
 .
 The original version was copyright 2006 Audrey Tang
 E<lt>cpan@audreyt.orgE<gt> and Yves Orton.
 .
 This program is free software; you can redistribute it and/or modify it
 under the same terms as Perl itself.
 .
 (However the bundled copy of RE2 has a different copyright owner and is under a
 BSD-like license, see F<re2/LICENSE>.)

Files:     README
Copyright: 2007 Ævar Arnfjörð Bjarmason.
           2010 David Leadbeater.
License:   Perl
 Based on re::engine::PCRE:
 .
 The original version was copyright 2006 Audrey Tang <cpan@audreyt.org>
 and Yves Orton.
 .
 This program is free software; you can redistribute it and/or modify it
 under the same terms as Perl itself.
 .
 (However the bundled copy of RE2 has a different copyright owner and is
 under a BSD-like license, see re2/LICENSE.)

Files:     ppport.h
Copyright: __NO_COPYRIGHT__ in: ppport.h
License:   Perl
 This program is free software; you can redistribute it and/or
 modify it under the same terms as Perl itself.

Files:     re2/re2/unicode_casefold.h
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Unicode case folding tables.
 .
 The Unicode case folding tables encode the mapping from one Unicode point
 to the next largest Unicode point with equivalent folding.  The largest
 point wraps back to the first.  For example, the tables map:
 .
 'A' -> 'a'
 'a' -> 'A'
 .
 'K' -> 'k'
 'k' -> 'K'  (Kelvin symbol)
 'K' -> 'K'
 .
 Like everything Unicode, these tables are big.  If we represent the table
 as a sorted list of uint32 pairs, it has 2049 entries and is 16 kB.
 Most table entries look like the ones around them:
 'A' maps to 'A'+32, 'B' maps to 'B'+32, etc.
 Instead of listing all the pairs explicitly, we make a list of ranges
 and deltas, so that the table entries for 'A' through 'Z' can be represented
 as a single entry { 'A', 'Z', +32 }.
 .
 In addition to blocks that map to each other (A-Z mapping to a-z)
 there are blocks of pairs that individually map to each other
 (for example, 0100<->0101, 0102<->0103, 0104<->0105, ...).
 For those, the special delta value EvenOdd marks even/odd pairs
 (if even, add 1; if odd, subtract 1), and OddEven marks odd/even pairs.
 .
 In this form, the table has 274 entries, about 3kB.  If we were to split
 the table into one for 16-bit codes and an overflow table for larger ones,
 we could get it down to about 1.5kB, but that's not worth the complexity.
 .
 The grouped form also allows for efficient fold range calculations
 rather than looping one character at a time.

Files:     re2/util/sparse_set.h
Copyright: 2006 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 DESCRIPTION
 .
 SparseSet<T>(m) is a set of integers in [0, m).
 It requires sizeof(int)*m memory, but it provides
 fast iteration through the elements in the set and fast clearing
 of the set.
 .
 Insertion and deletion are constant time operations.
 .
 Allocating the set is a constant time operation
 when memory allocation is a constant time operation.
 .
 Clearing the set is a constant time operation (unusual!).
 .
 Iterating through the set is an O(n) operation, where n
 is the number of items in the set (not O(m)).
 .
 The set iterator visits entries in the order they were first
 inserted into the array.  It is safe to add items to the set while
 using an iterator: the iterator will visit indices added to the set
 during the iteration, but will not re-visit indices whose values
 change after visiting.  Thus SparseSet can be a convenient
 implementation of a work queue.
 .
 The SparseSet implementation is NOT thread-safe.  It is up to the
 caller to make sure only one thread is accessing the set.  (Typically
 these sets are temporary values and used in situations where speed is
 important.)
 .
 The SparseSet interface does not present all the usual STL bells and
 whistles.
 .
 Implemented with reference to Briggs & Torczon, An Efficient
 Representation for Sparse Sets, ACM Letters on Programming Languages
 and Systems, Volume 2, Issue 1-4 (March-Dec.  1993), pp.  59-69.

Files:     re2/util/flags.h
Copyright: 2009 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Simplified version of Google's command line flags.
 Does not support parsing the command line.
 If you want to do that, see
 http://code.google.com/p/google-gflags

Files:     re2/util/utf.h
Copyright: 2002 Lucent Technologies.
License:   __UNKNOWN__
 Permission to use, copy, modify, and distribute this software for any
 purpose without fee is hereby granted, provided that this entire notice
 is included in all copies of any software which is or includes a copy
 or modification of this software and in all copies of the supporting
 documentation for such software.
 THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR LUCENT TECHNOLOGIES MAKE ANY
 REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
 .
 This file and rune.cc have been converted to compile as C++ code
 in name space re2.

Files:     re2/util/rune.cc
Copyright: 2002 Lucent Technologies.
License:   __UNKNOWN__
 Permission to use, copy, modify, and distribute this software for any
 purpose without fee is hereby granted, provided that this entire notice
 is included in all copies of any software which is or includes a copy
 or modification of this software and in all copies of the supporting
 documentation for such software.
 THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR LUCENT TECHNOLOGIES MAKE ANY
 REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.

Files:     re2/re2/testing/dump.cc
Copyright: 2006 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Dump the regexp into a string showing structure.

Files:     re2/re2/regexp.cc
Copyright: 2006 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Regular expression representation.

Files:     re2/re2/testing/re2_test.cc
Copyright: 2002-2009 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 TODO: Test extractions for PartialMatch/Consume

Files:     re2/re2/testing/regexp_generator.cc
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Regular expression generator: generates all possible

Files:     re2/re2/walker-inl.h
Copyright: 2006 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Helper class for traversing Regexps without recursion.
 Clients should declare their own subclasses that override
 the PreVisit and PostVisit methods, which are called before
 and after visiting the subexpressions.
 .
 Not quite the Visitor pattern, because (among other things)
 the Visitor pattern is recursive.

Files:     re2/re2/testing/regexp_generator.h
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Regular expression generator: generates all possible
 regular expressions within given parameters (see below for details).

Files:     re2/re2/stringpiece.h
Copyright: 2001-2010 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 A string-like object that points to a sized piece of memory.
 .
 Functions or methods may use const StringPiece& parameters to accept either
 a "const char*" or a "string" value that will be implicitly converted to
 a StringPiece.  The implicit conversion means that it is often appropriate
 to include this .h file in other files rather than forward-declaring
 StringPiece as would be appropriate for most other Google classes.
 .
 Systematic usage of StringPiece is encouraged as it will reduce unnecessary
 conversions from "const char*" to "string" and back again.
 .
 Arghh!  I wish C++ literals were "string".

Files:     re2/re2/mimics_pcre.cc
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Determine whether this library should match PCRE exactly
 for a particular Regexp.  (If so, the testing framework can
 check that it does.)
 .
 This library matches PCRE except in these cases:
 * the regexp contains a repetition of an empty string,
 like (a*)* or (a*)+.  In this case, PCRE will treat
 the repetition sequence as ending with an empty string,
 while this library does not.
 * Perl and PCRE differ on whether \v matches \n.
 For historical reasons, this library implements the Perl behavior.
 * Perl and PCRE allow $ in one-line mode to match either the very
 end of the text or just before a \n at the end of the text.
 This library requires it to match only the end of the text.
 * Similarly, Perl and PCRE do not allow ^ in multi-line mode to
 match the end of the text if the last character is a \n.
 This library does allow it.
 .
 Regexp::MimicsPCRE checks for any of these conditions.

Files:     re2/re2/simplify.cc
Copyright: 2006 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Rewrite POSIX and other features in re
 to use simple extended regular expression features.
 Also sort and simplify character classes.

Files:     re2/re2/testing/random_test.cc
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Random testing of regular expression matching.

Files:     re2/re2/unicode_groups.h
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Unicode character groups.
 .
 The codes get split into ranges of 16-bit codes
 and ranges of 32-bit codes.  It would be simpler
 to use only 32-bit ranges, but these tables are large
 enough to warrant extra care.
 .
 Using just 32-bit ranges gives 27 kB of data.
 Adding 16-bit ranges gives 18 kB of data.
 Adding an extra table of 16-bit singletons would reduce
 to 16.5 kB of data but make the data harder to use;
 we don't bother.

Files:     re2/re2/make_perl_groups.pl
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Generate table entries giving character ranges
 for POSIX/Perl character classes.  Rather than
 figure out what the definition is, it is easier to ask
 Perl about each letter from 0-128 and write down
 its answer.

Files:     re2/re2/filtered_re2.h
Copyright: 2009 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 The class FilteredRE2 is used as a wrapper to multiple RE2 regexps.
 It provides a prefilter mechanism that helps in cutting down the
 number of regexps that need to be actually searched.
 .
 By design, it does not include a string matching engine. This is to
 allow the user of the class to use their favorite string match
 engine. The overall flow is: Add all the regexps using Add, then
 Compile the FilteredRE2. The compile returns strings that need to
 be matched. Note that all returned strings are lowercase. For
 applying regexps to a search text, the caller does the string
 matching using the strings returned. When doing the string match,
 note that the caller has to do that on lower cased version of the
 search text. Then call FirstMatch or AllMatches with a vector of
 indices of strings that were found in the text to get the actual
 regexp matches.

Files:     re2/re2/prefilter_tree.h
Copyright: 2009 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 The PrefilterTree class is used to form an AND-OR tree of strings
 that would trigger each regexp. The 'prefilter' of each regexp is
 added tp PrefilterTree, and then PrefilterTree is used to find all
 the unique strings across the prefilters. During search, by using
 matches from a string matching engine, PrefilterTree deduces the
 set of regexps that are to be triggered. The 'string matching
 engine' itself is outside of this class, and the caller can use any
 favorite engine. PrefilterTree provides a set of strings (called
 atoms) that the user of this class should use to do the string
 matching.

Files:     re2/util/logging.h
Copyright: 2009 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Simplified version of Google's logging.

Files:     re2/re2/parse.cc
Copyright: 2006 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Regular expression parser.
 .
 The parser is a simple precedence-based parser with a
 manual stack.  The parsing work is done by the methods
 of the ParseState class.  The Regexp::Parse function is
 essentially just a lexer that calls the ParseState method
 for each token.
 .
 The parser recognizes POSIX extended regular expressions
 excluding backreferences, collating elements, and collating
 classes.  It also allows the empty string as a regular expression
 and recognizes the Perl escape sequences \d, \s, \w, \D, \S, and \W.
 See regexp.h for rationale.

Files:     re2/re2/testing/compile_test.cc
Copyright: 2007 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Test prog.cc, compile.cc

Files:     re2/util/pcre.cc
Copyright: 2003-2009 Google Inc.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 This is a variant of PCRE's pcrecpp.cc, originally written at Google.
 The main changes are the addition of the HitLimit method and
 compilation as PCRE in namespace re2.

Files:     re2/re2/testing/re2_arg_test.cc
Copyright: 2005 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 This tests to make sure numbers are parsed from strings
 correctly.
 Todo: Expand the test to validate strings parsed to the other types
 supported by RE2::Arg class

Files:     re2/re2/prog.cc
Copyright: 2007 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Compiled regular expression representation.

Files:     re2/util/valgrind.h
Copyright: 2000-2009 Julian Seward.
License:   __UNKNOWN__
 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions
 are met:
 .
 1. Redistributions of source code must retain the above copyright
 notice, this list of conditions and the following disclaimer.
 .
 2. The origin of this software must not be misrepresented; you must
 not claim that you wrote the original software.  If you use this
 software in a product, an acknowledgment in the product
 documentation would be appreciated but is not required.
 .
 3. Altered source versions must be plainly marked as such, and must
 not be misrepresented as being the original software.
 .
 4. The name of the author may not be used to endorse or promote
 products derived from this software without specific prior written
 permission.
 .
 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
 OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Files:     re2/re2/testing/regexp_benchmark.cc
Copyright: 2006-2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Benchmarks for regular expression implementations.

Files:     re2/util/arena.h
Copyright: 2000 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Sometimes it is necessary to allocate a large number of small
 objects.  Doing this the usual way (malloc, new) is slow,
 especially for multithreaded programs.  An UnsafeArena provides a
 mark/release method of memory management: it asks for a large chunk
 from the operating system and doles it out bit by bit as required.
 Then you free all the memory at once by calling UnsafeArena::Reset().
 The "Unsafe" refers to the fact that UnsafeArena is not safe to
 call from multiple threads.
 .
 The global operator new that can be used as follows:
 .
 #include "lib/arena-inl.h"
 .
 UnsafeArena arena(1000);

Files:     re2/re2/re2.cc
Copyright: 2003-2009 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Regular expression interface RE2.
 .
 Originally the PCRE C++ wrapper, but adapted to use
 the new automata-based regular expression engines.

Files:     re2/re2/testing/simplify_test.cc
Copyright: 2006 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Test simplify.cc.

Files:     re2/util/mutex.h
Copyright: 2007 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 A simple mutex wrapper, supporting locks and read-write locks.
 You should assume the locks are *not* re-entrant.

Files:     re2/util/sparse_array_test.cc
Copyright: 2006 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Simple tests that SparseArray behaves.

Files:     re2/util/pcre.h
Copyright: 2003-2010 Google Inc.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 This is a variant of PCRE's pcrecpp.h, originally written at Google.
 The main changes are the addition of the HitLimit method and
 compilation as PCRE in namespace re2.
 .
 C++ interface to the pcre regular-expression library.  PCRE supports
 Perl-style regular expressions (with extensions like \d, \w, \s,
 ...).

Files:     re2/re2/testing/exhaustive_tester.cc
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Exhaustive testing of regular expression matching.
 .
 Each test picks an alphabet (e.g., "abc"), a maximum string length,
 a maximum regular expression length, and a maximum number of letters
 that can appear in the regular expression.  Given these parameters,
 it tries every possible regular expression and string, verifying that
 the NFA, DFA, and a trivial backtracking implementation agree about
 the location of the match.

Files:     re2/util/sparse_array.h
Copyright: 2006 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 DESCRIPTION
 .
 SparseArray<T>(m) is a map from integers in [0, m) to T values.
 It requires (sizeof(T)+sizeof(int))*m memory, but it provides
 fast iteration through the elements in the array and fast clearing
 of the array.  The array has a concept of certain elements being
 uninitialized (having no value).
 .
 Insertion and deletion are constant time operations.
 .
 Allocating the array is a constant time operation
 when memory allocation is a constant time operation.
 .
 Clearing the array is a constant time operation (unusual!).
 .
 Iterating through the array is an O(n) operation, where n
 is the number of items in the array (not O(m)).
 .
 The array iterator visits entries in the order they were first
 inserted into the array.  It is safe to add items to the array while
 using an iterator: the iterator will visit indices added to the array
 during the iteration, but will not re-visit indices whose values
 change after visiting.  Thus SparseArray can be a convenient
 implementation of a work queue.
 .
 The SparseArray implementation is NOT thread-safe.  It is up to the
 caller to make sure only one thread is accessing the array.  (Typically
 these arrays are temporary values and used in situations where speed is
 important.)
 .
 The SparseArray interface does not present all the usual STL bells and
 whistles.
 .
 Implemented with reference to Briggs & Torczon, An Efficient
 Representation for Sparse Sets, ACM Letters on Programming Languages
 and Systems, Volume 2, Issue 1-4 (March-Dec.  1993), pp.  59-69.
 .
 Briggs & Torczon popularized this technique, but it had been known
 long before their paper.  They point out that Aho, Hopcroft, and
 Ullman's 1974 Design and Analysis of Computer Algorithms and Bentley's
 1986 Programming Pearls both hint at the technique in exercises to the
 reader (in Aho & Hopcroft, exercise 2.12; in Bentley, column 1
 exercise 8).
 .
 Briggs & Torczon describe a sparse set implementation.  I have
 trivially generalized it to create a sparse array (actually the original
 target of the AHU and Bentley exercises).
 .
 IMPLEMENTATION

Files:     re2/re2/prefilter.h
Copyright: 2009 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Prefilter is the class used to extract string guards from regexps.
 Rather than using Prefilter class directly, use FilteredRE2.

Files:     re2/re2/testing/charclass_test.cc
Copyright: 2006 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Test character class manipulations.

Files:     re2/re2/compile.cc
Copyright: 2007 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Compile regular expression to Prog.
 .
 Prog and Inst are defined in prog.h.
 This file's external interface is just Regexp::CompileToProg.
 The Compiler class defined in this file is private.

Files:     re2/re2/tostring.cc
Copyright: 2006 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Format a regular expression structure as a string.

Files:     re2/re2/dfa.cc
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 A DFA (deterministic finite automaton)-based regular expression search.
 .
 The DFA search has two main parts: the construction of the automaton,
 which is represented by a graph of State structures, and the execution
 of the automaton over a given input string.
 .
 The basic idea is that the State graph is constructed so that the
 execution can simply start with a state s, and then for each byte c in

Files:     re2/re2/testing/string_generator_test.cc
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Test StringGenerator.

Files:     re2/re2/testing/tester.h
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Comparative tester for regular expression matching.
 Checks all implementations against each other.

Files:     re2/re2/testing/tester.cc
Copyright: 2008 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Regular expression engine tester -- test all the implementations against each other.

Files:     re2/re2/prog.h
Copyright: 2007 The RE2 Authors.
License:   __UNKNOWN__
 Use of this source code is governed by a BSD-style
 license that can be found in the LICENSE file.
 .
 Compiled representation of regular expressions.
 See regexp.h for the Regexp class, which represents a regular
 expression symbolically.

#----------------------------------------------------------------------------
# Files marked as NO_LICENSE_TEXT_FOUND may be covered by the following
# license/copyright files.
