+static void
+lex_token_destroy (struct lex_token *t)
+{
+ token_uninit (&t->token);
+ if (t->ref_cnt)
+ {
+ assert (*t->ref_cnt > 0);
+ if (!--*t->ref_cnt)
+ {
+ free (t->macro_rep);
+ free (t->ref_cnt);
+ }
+ }
+ free (t);
+}
+\f
+/* A deque of lex_tokens that comprises one stage in the token pipeline in a
+ lex_source. */
+struct lex_stage
+ {
+ struct deque deque;
+ struct lex_token **tokens;
+ };
+
+static void lex_stage_clear (struct lex_stage *);
+static void lex_stage_uninit (struct lex_stage *);
+
+static size_t lex_stage_count (const struct lex_stage *);
+static bool lex_stage_is_empty (const struct lex_stage *);
+
+static struct lex_token *lex_stage_first (struct lex_stage *);
+static struct lex_token *lex_stage_nth (struct lex_stage *, size_t ofs);
+
+static void lex_stage_push_last (struct lex_stage *, struct lex_token *);
+static void lex_stage_pop_first (struct lex_stage *);
+
+static void lex_stage_shift (struct lex_stage *dst, struct lex_stage *src,
+ size_t n);
+
+/* Deletes all the tokens from STAGE. */
+static void
+lex_stage_clear (struct lex_stage *stage)
+{
+ while (!deque_is_empty (&stage->deque))
+ lex_stage_pop_first (stage);
+}
+
+/* Deletes all the tokens from STAGE and frees storage for the deque. */
+static void
+lex_stage_uninit (struct lex_stage *stage)
+{
+ lex_stage_clear (stage);
+ free (stage->tokens);
+}
+
+/* Returns true if STAGE contains no tokens, otherwise false. */
+static bool
+lex_stage_is_empty (const struct lex_stage *stage)
+{
+ return deque_is_empty (&stage->deque);
+}
+
+/* Returns the number of tokens in STAGE. */
+static size_t
+lex_stage_count (const struct lex_stage *stage)
+{
+ return deque_count (&stage->deque);
+}
+
+/* Returns the first token in STAGE, which must be nonempty.
+ The first token is the one accessed with the least lookahead. */
+static struct lex_token *
+lex_stage_first (struct lex_stage *stage)
+{
+ return lex_stage_nth (stage, 0);
+}
+
+/* Returns the token the given INDEX in STAGE. The first token (with the least
+ lookahead) is 0, the second token is 1, and so on. There must be at least
+ INDEX + 1 tokens in STAGE. */
+static struct lex_token *
+lex_stage_nth (struct lex_stage *stage, size_t index)
+{
+ return stage->tokens[deque_back (&stage->deque, index)];
+}
+
+/* Adds TOKEN so that it becomes the last token in STAGE. */
+static void
+lex_stage_push_last (struct lex_stage *stage, struct lex_token *token)
+{
+ if (deque_is_full (&stage->deque))
+ stage->tokens = deque_expand (&stage->deque, stage->tokens,
+ sizeof *stage->tokens);
+ stage->tokens[deque_push_front (&stage->deque)] = token;
+}
+
+/* Removes and returns the first token from STAGE. */
+static struct lex_token *
+lex_stage_take_first (struct lex_stage *stage)
+{
+ return stage->tokens[deque_pop_back (&stage->deque)];
+}
+
+/* Removes the first token from STAGE and uninitializes it. */
+static void
+lex_stage_pop_first (struct lex_stage *stage)
+{
+ lex_token_destroy (lex_stage_take_first (stage));
+}
+
+/* Removes the first N tokens from SRC, appending them to DST as the last
+ tokens. */
+static void
+lex_stage_shift (struct lex_stage *dst, struct lex_stage *src, size_t n)
+{
+ for (size_t i = 0; i < n; i++)
+ lex_stage_push_last (dst, lex_stage_take_first (src));
+}
+