Add initial inversion list object

Going forward the intent is to convert from swashes to the better-suited
inversion list data structure.  This adds rudimentary inversion lists that have
only the functionality needed for 5.14.  As a result, they are as much as
possible static to one file.

What's necessary for 5.14 is enough to allow folding of ANYOF nodes to be moved
from regexec to regcomp.  Why they are needed for that is to generate as
compact as possible class definitions; otherwise, very long linear lists might
be generated.  (They still may be, but that's inherent in the problem domain;
this generates as compact as possible, combining overlapping ranges, etc.)

The only two non-trivial methods in this object are from published algorithms.

1 files changed, 84 insertions, 1 deletions

diff --git a/proto.h b/proto.h
index 829e451529..8441ee810e 100644
--- a/proto.h
+++ b/proto.h
@@ -23,12 +23,26 @@ PERL_CALLCONV int	Perl_Gv_AMupdate(pTHX_ HV* stash, bool destructing)
 	assert(stash)
 
 PERL_CALLCONV const char *	Perl_PerlIO_context_layers(pTHX_ const char *mode);
-PERL_CALLCONV HV*	Perl__swash_inversion_hash(pTHX_ SV *swash)
+PERL_CALLCONV void	Perl__append_range_to_invlist(pTHX_ HV* const invlist, const UV start, const UV end)
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT__APPEND_RANGE_TO_INVLIST	\
+	assert(invlist)
+
+PERL_CALLCONV HV*	Perl__new_invlist(pTHX_ const IV initial_size)
+			__attribute__warn_unused_result__;
+
+PERL_CALLCONV HV*	Perl__swash_inversion_hash(pTHX_ SV* const swash)
 			__attribute__warn_unused_result__
 			__attribute__nonnull__(pTHX_1);
 #define PERL_ARGS_ASSERT__SWASH_INVERSION_HASH	\
 	assert(swash)
 
+PERL_CALLCONV HV*	Perl__swash_to_invlist(pTHX_ SV* const swash)
+			__attribute__warn_unused_result__
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT__SWASH_TO_INVLIST	\
+	assert(swash)
+
 PERL_CALLCONV PADOFFSET	Perl_allocmy(pTHX_ const char *const name, const STRLEN len, const U32 flags)
 			__attribute__nonnull__(pTHX_1);
 #define PERL_ARGS_ASSERT_ALLOCMY	\
@@ -5931,6 +5945,12 @@ STATIC U32	S_add_data(struct RExC_state_t *pRExC_state, U32 n, const char *s)
 #define PERL_ARGS_ASSERT_ADD_DATA	\
 	assert(pRExC_state); assert(s)
 
+STATIC HV*	S_add_range_to_invlist(pTHX_ HV* const invlist, const UV start, const UV end)
+			__attribute__warn_unused_result__
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT_ADD_RANGE_TO_INVLIST	\
+	assert(invlist)
+
 STATIC void	S_checkposixcc(pTHX_ struct RExC_state_t *pRExC_state)
 			__attribute__nonnull__(pTHX_1);
 #define PERL_ARGS_ASSERT_CHECKPOSIXCC	\
@@ -5973,6 +5993,69 @@ STATIC void	S_cl_or(const struct RExC_state_t *pRExC_state, struct regnode_charc
 #define PERL_ARGS_ASSERT_CL_OR	\
 	assert(pRExC_state); assert(cl); assert(or_with)
 
+PERL_STATIC_INLINE UV*	S_invlist_array(pTHX_ HV* const invlist)
+			__attribute__warn_unused_result__
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT_INVLIST_ARRAY	\
+	assert(invlist)
+
+PERL_STATIC_INLINE void	S_invlist_destroy(pTHX_ HV* const invlist)
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT_INVLIST_DESTROY	\
+	assert(invlist)
+
+STATIC void	S_invlist_extend(pTHX_ HV* const invlist, const UV len)
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT_INVLIST_EXTEND	\
+	assert(invlist)
+
+STATIC HV*	S_invlist_intersection(pTHX_ HV* const a, HV* const b)
+			__attribute__warn_unused_result__
+			__attribute__nonnull__(pTHX_1)
+			__attribute__nonnull__(pTHX_2);
+#define PERL_ARGS_ASSERT_INVLIST_INTERSECTION	\
+	assert(a); assert(b)
+
+PERL_STATIC_INLINE UV	S_invlist_len(pTHX_ HV* const invlist)
+			__attribute__warn_unused_result__
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT_INVLIST_LEN	\
+	assert(invlist)
+
+PERL_STATIC_INLINE UV	S_invlist_max(pTHX_ HV* const invlist)
+			__attribute__warn_unused_result__
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT_INVLIST_MAX	\
+	assert(invlist)
+
+PERL_STATIC_INLINE void	S_invlist_set_array(pTHX_ HV* const invlist, const UV* const array)
+			__attribute__nonnull__(pTHX_1)
+			__attribute__nonnull__(pTHX_2);
+#define PERL_ARGS_ASSERT_INVLIST_SET_ARRAY	\
+	assert(invlist); assert(array)
+
+PERL_STATIC_INLINE void	S_invlist_set_len(pTHX_ HV* const invlist, const UV len)
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT_INVLIST_SET_LEN	\
+	assert(invlist)
+
+PERL_STATIC_INLINE void	S_invlist_set_max(pTHX_ HV* const invlist, const UV max)
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT_INVLIST_SET_MAX	\
+	assert(invlist)
+
+PERL_STATIC_INLINE void	S_invlist_trim(pTHX_ HV* const invlist)
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT_INVLIST_TRIM	\
+	assert(invlist)
+
+STATIC HV*	S_invlist_union(pTHX_ HV* const a, HV* const b)
+			__attribute__warn_unused_result__
+			__attribute__nonnull__(pTHX_1)
+			__attribute__nonnull__(pTHX_2);
+#define PERL_ARGS_ASSERT_INVLIST_UNION	\
+	assert(a); assert(b)
+
 STATIC U32	S_join_exact(pTHX_ struct RExC_state_t *pRExC_state, regnode *scan, I32 *min, U32 flags, regnode *val, U32 depth)
 			__attribute__nonnull__(pTHX_1)
 			__attribute__nonnull__(pTHX_2)