Add iterator for inversion lists

4 files changed, 78 insertions, 1 deletions

diff --git a/embed.fnc b/embed.fnc
index e24ad275db..4e9106a31d 100644
--- a/embed.fnc
+++ b/embed.fnc
@@ -1315,6 +1315,9 @@ EiMR	|UV	|invlist_max	|NN SV* const invlist
 EiM	|void	|invlist_set_len	|NN SV* const invlist|const UV len
 EiM	|void	|invlist_trim	|NN SV* const invlist
 EsM	|void	|invlist_union	|NN SV* const a|NN SV* const b|NN SV** output
+EiMR	|UV*	|get_invlist_iter_addr	|NN SV* invlist
+EiM	|void	|invlist_iterinit|NN SV* invlist
+EsMR	|bool	|invlist_iternext|NN SV* invlist|NN UV* start|NN UV* end
 #endif
 Ap	|void	|taint_env
 Ap	|void	|taint_proper	|NULLOK const char* f|NN const char *const s
diff --git a/embed.h b/embed.h
index fd2fb1a33b..711a4bc454 100644
--- a/embed.h
+++ b/embed.h
@@ -875,9 +875,12 @@
 #define cl_init			S_cl_init
 #define cl_is_anything		S_cl_is_anything
 #define cl_or			S_cl_or
+#define get_invlist_iter_addr(a)	S_get_invlist_iter_addr(aTHX_ a)
 #define invlist_array(a)	S_invlist_array(aTHX_ a)
 #define invlist_extend(a,b)	S_invlist_extend(aTHX_ a,b)
 #define invlist_intersection(a,b,c)	S_invlist_intersection(aTHX_ a,b,c)
+#define invlist_iterinit(a)	S_invlist_iterinit(aTHX_ a)
+#define invlist_iternext(a,b,c)	S_invlist_iternext(aTHX_ a,b,c)
 #define invlist_len(a)		S_invlist_len(aTHX_ a)
 #define invlist_max(a)		S_invlist_max(aTHX_ a)
 #define invlist_set_len(a,b)	S_invlist_set_len(aTHX_ a,b)
diff --git a/proto.h b/proto.h
index fdfc82b0c8..320edfd0b7 100644
--- a/proto.h
+++ b/proto.h
@@ -6041,6 +6041,12 @@ 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_get_invlist_iter_addr(pTHX_ SV* invlist)
+			__attribute__warn_unused_result__
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT_GET_INVLIST_ITER_ADDR	\
+	assert(invlist)
+
 PERL_STATIC_INLINE UV*	S_invlist_array(pTHX_ SV* const invlist)
 			__attribute__warn_unused_result__
 			__attribute__nonnull__(pTHX_1);
@@ -6059,6 +6065,19 @@ STATIC void	S_invlist_intersection(pTHX_ SV* const a, SV* const b, SV** i)
 #define PERL_ARGS_ASSERT_INVLIST_INTERSECTION	\
 	assert(a); assert(b); assert(i)
 
+PERL_STATIC_INLINE void	S_invlist_iterinit(pTHX_ SV* invlist)
+			__attribute__nonnull__(pTHX_1);
+#define PERL_ARGS_ASSERT_INVLIST_ITERINIT	\
+	assert(invlist)
+
+STATIC bool	S_invlist_iternext(pTHX_ SV* invlist, UV* start, UV* end)
+			__attribute__warn_unused_result__
+			__attribute__nonnull__(pTHX_1)
+			__attribute__nonnull__(pTHX_2)
+			__attribute__nonnull__(pTHX_3);
+#define PERL_ARGS_ASSERT_INVLIST_ITERNEXT	\
+	assert(invlist); assert(start); assert(end)
+
 PERL_STATIC_INLINE UV	S_invlist_len(pTHX_ SV* const invlist)
 			__attribute__warn_unused_result__
 			__attribute__nonnull__(pTHX_1);
diff --git a/regcomp.c b/regcomp.c
index 02062a6fbb..1f9c33d1c0 100644
--- a/regcomp.c
+++ b/regcomp.c
@@ -5835,7 +5835,8 @@ S_reg_scan_name(pTHX_ RExC_state_t *pRExC_state, U32 flags)
  * Some of the methods should always be private to the implementation, and some
  * should eventually be made public */
 
-#define HEADER_LENGTH 0
+#define INVLIST_ITER_OFFSET 0
+#define HEADER_LENGTH (INVLIST_ITER_OFFSET + 1)
 
 /* Internally things are UVs */
 #define TO_INTERNAL_SIZE(x) ((x + HEADER_LENGTH) * sizeof(UV))
@@ -5905,6 +5906,9 @@ Perl__new_invlist(pTHX_ IV initial_size)
     new_list = newSV(TO_INTERNAL_SIZE(initial_size));
     invlist_set_len(new_list, 0);
 
+    /* Force iterinit() to be used to get iteration to work */
+    *get_invlist_iter_addr(new_list) = UV_MAX;
+
     return new_list;
 }
 #endif
@@ -6362,10 +6366,58 @@ S_add_cp_to_invlist(pTHX_ SV* invlist, const UV cp) {
     return add_range_to_invlist(invlist, cp, cp);
 }
 
+PERL_STATIC_INLINE UV*
+S_get_invlist_iter_addr(pTHX_ SV* invlist)
+{
+    /* Return the address of the UV that contains the current iteration
+     * position */
+
+    PERL_ARGS_ASSERT_GET_INVLIST_ITER_ADDR;
+
+    return (UV *) (SvPVX(invlist) + (INVLIST_ITER_OFFSET * sizeof (UV)));
+}
+
+PERL_STATIC_INLINE void
+S_invlist_iterinit(pTHX_ SV* invlist)	/* Initialize iterator for invlist */
+{
+    PERL_ARGS_ASSERT_INVLIST_ITERINIT;
+
+    *get_invlist_iter_addr(invlist) = 0;
+}
+
+STATIC bool
+S_invlist_iternext(pTHX_ SV* invlist, UV* start, UV* end)
+{
+    UV* pos = get_invlist_iter_addr(invlist);
+    UV len = invlist_len(invlist);
+    UV *array;
+
+    PERL_ARGS_ASSERT_INVLIST_ITERNEXT;
+
+    if (*pos >= len) {
+	*pos = UV_MAX;	/* Force iternit() to be required next time */
+	return FALSE;
+    }
+
+    array = invlist_array(invlist);
+
+    *start = array[(*pos)++];
+
+    if (*pos >= len) {
+	*end = UV_MAX;
+    }
+    else {
+	*end = array[(*pos)++] - 1;
+    }
+
+    return TRUE;
+}
+
 #undef HEADER_LENGTH
 #undef INVLIST_INITIAL_LENGTH
 #undef TO_INTERNAL_SIZE
 #undef FROM_INTERNAL_SIZE
+#undef INVLIST_ITER_OFFSET
 
 /* End of inversion list object */