stack.c File Reference

#include "./alloc.h"
#include "./language.h"
#include "./subtree.h"
#include "./array.h"
#include "./stack.h"
#include "./length.h"
#include <assert.h>
#include <stdio.h>

Go to the source code of this file.

Classes
struct	StackLink
struct	StackNode
struct	StackIterator
struct	StackHead
struct	Stack
struct	SummarizeStackSession

Macros
#define	MAX_LINK_COUNT   8
#define	MAX_NODE_POOL_SIZE   50
#define	MAX_ITERATOR_COUNT   64
#define	inline   static inline __attribute__((always_inline))

Typedefs
typedef struct StackNode	StackNode
typedef unsigned	StackAction
typedef StackAction(*	StackCallback) (void *, const StackIterator *)

Enumerations
enum	{ StackActionNone , StackActionStop = 1 , StackActionPop = 2 }

Functions
typedef	Array (StackNode *)
static void	stack_node_retain (StackNode *self)
static void	stack_node_release (StackNode *self, StackNodeArray *pool, SubtreePool *subtree_pool)
static StackNode *	stack_node_new (StackNode *previous_node, Subtree subtree, bool is_pending, TSStateId state, StackNodeArray *pool)
static bool	stack__subtree_is_equivalent (Subtree left, Subtree right)
static void	stack_node_add_link (StackNode *self, StackLink link, SubtreePool *subtree_pool)
static void	stack_head_delete (StackHead *self, StackNodeArray *pool, SubtreePool *subtree_pool)
static StackVersion	ts_stack__add_version (Stack *self, StackVersion original_version, StackNode *node)
static void	ts_stack__add_slice (Stack *self, StackVersion original_version, StackNode *node, SubtreeArray *subtrees)
StackSliceArray	stack__iter (Stack *self, StackVersion version, StackCallback callback, void *payload, int goal_subtree_count)
Stack *	ts_stack_new (SubtreePool *subtree_pool)
void	ts_stack_delete (Stack *self)
uint32_t	ts_stack_version_count (const Stack *self)
TSStateId	ts_stack_state (const Stack *self, StackVersion version)
Length	ts_stack_position (const Stack *self, StackVersion version)
Subtree	ts_stack_last_external_token (const Stack *self, StackVersion version)
void	ts_stack_set_last_external_token (Stack *self, StackVersion version, Subtree token)
unsigned	ts_stack_error_cost (const Stack *self, StackVersion version)
unsigned	ts_stack_node_count_since_error (const Stack *self, StackVersion version)
void	ts_stack_push (Stack *self, StackVersion version, Subtree subtree, bool pending, TSStateId state)
StackAction	pop_count_callback (void *payload, const StackIterator *iterator)
StackSliceArray	ts_stack_pop_count (Stack *self, StackVersion version, uint32_t count)
StackAction	pop_pending_callback (void *payload, const StackIterator *iterator)
StackSliceArray	ts_stack_pop_pending (Stack *self, StackVersion version)
StackAction	pop_error_callback (void *payload, const StackIterator *iterator)
SubtreeArray	ts_stack_pop_error (Stack *self, StackVersion version)
StackAction	pop_all_callback (void *payload, const StackIterator *iterator)
StackSliceArray	ts_stack_pop_all (Stack *self, StackVersion version)
StackAction	summarize_stack_callback (void *payload, const StackIterator *iterator)
void	ts_stack_record_summary (Stack *self, StackVersion version, unsigned max_depth)
StackSummary *	ts_stack_get_summary (Stack *self, StackVersion version)
int	ts_stack_dynamic_precedence (Stack *self, StackVersion version)
bool	ts_stack_has_advanced_since_error (const Stack *self, StackVersion version)
void	ts_stack_remove_version (Stack *self, StackVersion version)
void	ts_stack_renumber_version (Stack *self, StackVersion v1, StackVersion v2)
void	ts_stack_swap_versions (Stack *self, StackVersion v1, StackVersion v2)
StackVersion	ts_stack_copy_version (Stack *self, StackVersion version)
bool	ts_stack_merge (Stack *self, StackVersion version1, StackVersion version2)
bool	ts_stack_can_merge (Stack *self, StackVersion version1, StackVersion version2)
void	ts_stack_halt (Stack *self, StackVersion version)
void	ts_stack_pause (Stack *self, StackVersion version, Subtree lookahead)
bool	ts_stack_is_active (const Stack *self, StackVersion version)
bool	ts_stack_is_halted (const Stack *self, StackVersion version)
bool	ts_stack_is_paused (const Stack *self, StackVersion version)
Subtree	ts_stack_resume (Stack *self, StackVersion version)
void	ts_stack_clear (Stack *self)
bool	ts_stack_print_dot_graph (Stack *self, const TSLanguage *language, FILE *f)

Variables
	StackStatus

Macro Definition Documentation

inline

#define inline   static inline __attribute__((always_inline))

Definition at line 17 of file stack.c.

MAX_ITERATOR_COUNT

#define MAX_ITERATOR_COUNT   64

Definition at line 12 of file stack.c.

MAX_LINK_COUNT

#define MAX_LINK_COUNT   8

Definition at line 10 of file stack.c.

MAX_NODE_POOL_SIZE

#define MAX_NODE_POOL_SIZE   50

Definition at line 11 of file stack.c.

Typedef Documentation

StackAction

typedef unsigned StackAction

Definition at line 72 of file stack.c.

StackCallback

typedef StackAction(* StackCallback) (void *, const StackIterator *)

Definition at line 79 of file stack.c.

StackNode

typedef struct StackNode StackNode

Definition at line 1 of file stack.c.

Enumeration Type Documentation

anonymous enum

anonymous enum

Enumerator
StackActionNone
StackActionStop
StackActionPop

Definition at line 73 of file stack.c.

     {
  StackActionNone,
  StackActionStop = 1,
  StackActionPop = 2,
};

Function Documentation

Array()

typedef Array

(

StackNode *

)

Definition at line 46 of file stack.c.

             {
  StackStatusActive,
  StackStatusPaused,
  StackStatusHalted,
} StackStatus;

Referenced by ts_stack_print_dot_graph().

pop_all_callback()

StackAction pop_all_callback ( void *  payload, const StackIterator *  iterator  )

inline

Definition at line 564 of file stack.c.

                                                                                  {
  (void)payload;
  return iterator->node->link_count == 0 ? StackActionPop : StackActionNone;
}

References StackActionNone, and StackActionPop.

Referenced by ts_stack_pop_all().

pop_count_callback()

StackAction pop_count_callback ( void *  payload, const StackIterator *  iterator  )

inline

Definition at line 498 of file stack.c.

                                                                                    {
  unsigned *goal_subtree_count = payload;
  if (iterator->subtree_count == *goal_subtree_count) {
    return StackActionPop | StackActionStop;
  } else {
    return StackActionNone;
  }
}

References StackActionNone, StackActionPop, and StackActionStop.

Referenced by ts_stack_pop_count().

pop_error_callback()

StackAction pop_error_callback ( void *  payload, const StackIterator *  iterator  )

inline

Definition at line 533 of file stack.c.

                                                                                    {
  if (iterator->subtrees.size > 0) {
    bool *found_error = payload;
    if (!*found_error && ts_subtree_is_error(iterator->subtrees.contents[0])) {
      *found_error = true;
      return StackActionPop | StackActionStop;
    } else {
      return StackActionStop;
    }
  } else {
    return StackActionNone;
  }
}

References StackActionNone, StackActionPop, StackActionStop, and ts_subtree_is_error().

Referenced by ts_stack_pop_error().

pop_pending_callback()

StackAction pop_pending_callback ( void *  payload, const StackIterator *  iterator  )

inline

Definition at line 511 of file stack.c.

                                                                                      {
  (void)payload;
  if (iterator->subtree_count >= 1) {
    if (iterator->is_pending) {
      return StackActionPop | StackActionStop;
    } else {
      return StackActionStop;
    }
  } else {
    return StackActionNone;
  }
}

References StackActionNone, StackActionPop, and StackActionStop.

Referenced by ts_stack_pop_pending().

stack__iter()

StackSliceArray stack__iter ( Stack *  self, StackVersion  version, StackCallback  callback, void *  payload, int  goal_subtree_count  )

inline

Definition at line 308 of file stack.c.

  {
  array_clear(&self->slices);
  array_clear(&self->iterators);
 
  StackHead *head = array_get(&self->heads, version);
  StackIterator iterator = {
    .node = head->node,
    .subtrees = array_new(),
    .subtree_count = 0,
    .is_pending = true,
  };
 
  bool include_subtrees = false;
  if (goal_subtree_count >= 0) {
    include_subtrees = true;
    array_reserve(&iterator.subtrees, ts_subtree_alloc_size(goal_subtree_count) / sizeof(Subtree));
  }
 
  array_push(&self->iterators, iterator);
 
  while (self->iterators.size > 0) {
    for (uint32_t i = 0, size = self->iterators.size; i < size; i++) {
      StackIterator *iterator = &self->iterators.contents[i];
      StackNode *node = iterator->node;
 
      StackAction action = callback(payload, iterator);
      bool should_pop = action & StackActionPop;
      bool should_stop = action & StackActionStop || node->link_count == 0;
 
      if (should_pop) {
        SubtreeArray subtrees = iterator->subtrees;
        if (!should_stop) {
          ts_subtree_array_copy(subtrees, &subtrees);
        }
        ts_subtree_array_reverse(&subtrees);
        ts_stack__add_slice(
          self,
          version,
          node,
          &subtrees
        );
      }
 
      if (should_stop) {
        if (!should_pop) {
          ts_subtree_array_delete(self->subtree_pool, &iterator->subtrees);
        }
        array_erase(&self->iterators, i);
        i--, size--;
        continue;
      }
 
      for (uint32_t j = 1; j <= node->link_count; j++) {
        StackIterator *next_iterator;
        StackLink link;
        if (j == node->link_count) {
          link = node->links[0];
          next_iterator = &self->iterators.contents[i];
        } else {
          if (self->iterators.size >= MAX_ITERATOR_COUNT) continue;
          link = node->links[j];
          StackIterator current_iterator = self->iterators.contents[i];
          array_push(&self->iterators, current_iterator);
          next_iterator = array_back(&self->iterators);
          ts_subtree_array_copy(next_iterator->subtrees, &next_iterator->subtrees);
        }
 
        next_iterator->node = link.node;
        if (link.subtree.ptr) {
          if (include_subtrees) {
            array_push(&next_iterator->subtrees, link.subtree);
            ts_subtree_retain(link.subtree);
          }
 
          if (!ts_subtree_extra(link.subtree)) {
            next_iterator->subtree_count++;
            if (!link.is_pending) {
              next_iterator->is_pending = false;
            }
          }
        } else {
          next_iterator->subtree_count++;
          next_iterator->is_pending = false;
        }
      }
    }
  }
 
  return self->slices;
}

References test-lz4-speed::action, array_back, array_clear, array_erase, array_get, array_new, array_push, array_reserve, test-lz4-versions::head, i, StackIterator::is_pending, link, StackNode::link_count, StackNode::links, MAX_ITERATOR_COUNT, StackIterator::node, StackActionPop, StackActionStop, StackIterator::subtree_count, StackIterator::subtrees, ts_stack__add_slice(), ts_subtree_alloc_size(), ts_subtree_array_copy(), ts_subtree_array_delete(), ts_subtree_array_reverse(), ts_subtree_extra(), and ts_subtree_retain().

Referenced by ts_stack_pop_all(), ts_stack_pop_count(), ts_stack_pop_error(), ts_stack_pop_pending(), and ts_stack_record_summary().

stack__subtree_is_equivalent()

static bool stack__subtree_is_equivalent ( Subtree  left, Subtree  right  )

static

Definition at line 166 of file stack.c.

                                                                      {
  if (left.ptr == right.ptr) return true;
  if (!left.ptr || !right.ptr) return false;
 
  // Symbols must match
  if (ts_subtree_symbol(left) != ts_subtree_symbol(right)) return false;
 
  // If both have errors, don't bother keeping both.
  if (ts_subtree_error_cost(left) > 0 && ts_subtree_error_cost(right) > 0) return true;
 
  return (
    ts_subtree_padding(left).bytes == ts_subtree_padding(right).bytes &&
    ts_subtree_size(left).bytes == ts_subtree_size(right).bytes &&
    ts_subtree_child_count(left) == ts_subtree_child_count(right) &&
    ts_subtree_extra(left) == ts_subtree_extra(right) &&
    ts_subtree_external_scanner_state_eq(left, right)
  );
}

References bytes, Subtree::ptr, ts_subtree_child_count(), ts_subtree_error_cost(), ts_subtree_external_scanner_state_eq(), ts_subtree_extra(), ts_subtree_padding(), ts_subtree_size(), and ts_subtree_symbol().

Referenced by stack_node_add_link().

stack_head_delete()

static void stack_head_delete ( StackHead *  self, StackNodeArray *  pool, SubtreePool *  subtree_pool  )

static

Definition at line 250 of file stack.c.

  {
  if (self->node) {
    if (self->last_external_token.ptr) {
      ts_subtree_release(subtree_pool, self->last_external_token);
    }
    if (self->lookahead_when_paused.ptr) {
      ts_subtree_release(subtree_pool, self->lookahead_when_paused);
    }
    if (self->summary) {
      array_delete(self->summary);
      ts_free(self->summary);
    }
    stack_node_release(self->node, pool, subtree_pool);
  }
}

References array_delete, stack_node_release(), ts_free, and ts_subtree_release().

Referenced by ts_stack_clear(), ts_stack_delete(), ts_stack_remove_version(), and ts_stack_renumber_version().

stack_node_add_link()

static void stack_node_add_link ( StackNode *  self, StackLink  link, SubtreePool *  subtree_pool  )

static

Definition at line 185 of file stack.c.

  {
  if (link.node == self) return;
 
  for (int i = 0; i < self->link_count; i++) {
    StackLink *existing_link = &self->links[i];
    if (stack__subtree_is_equivalent(existing_link->subtree, link.subtree)) {
      // In general, we preserve ambiguities until they are removed from the stack
      // during a pop operation where multiple paths lead to the same node. But in
      // the special case where two links directly connect the same pair of nodes,
      // we can safely remove the ambiguity ahead of time without changing behavior.
      if (existing_link->node == link.node) {
        if (
          ts_subtree_dynamic_precedence(link.subtree) >
          ts_subtree_dynamic_precedence(existing_link->subtree)
        ) {
          ts_subtree_retain(link.subtree);
          ts_subtree_release(subtree_pool, existing_link->subtree);
          existing_link->subtree = link.subtree;
          self->dynamic_precedence =
            link.node->dynamic_precedence + ts_subtree_dynamic_precedence(link.subtree);
        }
        return;
      }
 
      // If the previous nodes are mergeable, merge them recursively.
      if (
        existing_link->node->state == link.node->state &&
        existing_link->node->position.bytes == link.node->position.bytes
      ) {
        for (int j = 0; j < link.node->link_count; j++) {
          stack_node_add_link(existing_link->node, link.node->links[j], subtree_pool);
        }
        int32_t dynamic_precedence = link.node->dynamic_precedence;
        if (link.subtree.ptr) {
          dynamic_precedence += ts_subtree_dynamic_precedence(link.subtree);
        }
        if (dynamic_precedence > self->dynamic_precedence) {
          self->dynamic_precedence = dynamic_precedence;
        }
        return;
      }
    }
  }
 
  if (self->link_count == MAX_LINK_COUNT) return;
 
  stack_node_retain(link.node);
  unsigned node_count = link.node->node_count;
  int dynamic_precedence = link.node->dynamic_precedence;
  self->links[self->link_count++] = link;
 
  if (link.subtree.ptr) {
    ts_subtree_retain(link.subtree);
    node_count += ts_subtree_node_count(link.subtree);
    dynamic_precedence += ts_subtree_dynamic_precedence(link.subtree);
  }
 
  if (node_count > self->node_count) self->node_count = node_count;
  if (dynamic_precedence > self->dynamic_precedence) self->dynamic_precedence = dynamic_precedence;
}

References Length::bytes, i, link, MAX_LINK_COUNT, StackLink::node, StackNode::position, stack__subtree_is_equivalent(), stack_node_retain(), StackNode::state, StackLink::subtree, ts_subtree_dynamic_precedence(), ts_subtree_node_count(), ts_subtree_release(), and ts_subtree_retain().

Referenced by ts_stack_merge().

stack_node_new()

static StackNode* stack_node_new ( StackNode *  previous_node, Subtree  subtree, bool  is_pending, TSStateId  state, StackNodeArray *  pool  )

static

Definition at line 123 of file stack.c.

  {
  StackNode *node = pool->size > 0
    ? array_pop(pool)
    : ts_malloc(sizeof(StackNode));
  *node = (StackNode) {
    .ref_count = 1,
    .link_count = 0,
    .state = state
  };
 
  if (previous_node) {
    node->link_count = 1;
    node->links[0] = (StackLink) {
      .node = previous_node,
      .subtree = subtree,
      .is_pending = is_pending,
    };
 
    node->position = previous_node->position;
    node->error_cost = previous_node->error_cost;
    node->dynamic_precedence = previous_node->dynamic_precedence;
    node->node_count = previous_node->node_count;
 
    if (subtree.ptr) {
      node->error_cost += ts_subtree_error_cost(subtree);
      node->position = length_add(node->position, ts_subtree_total_size(subtree));
      node->node_count += ts_subtree_node_count(subtree);
      node->dynamic_precedence += ts_subtree_dynamic_precedence(subtree);
    }
  } else {
    node->position = length_zero();
    node->error_cost = 0;
  }
 
  return node;
}

References array_pop, StackNode::dynamic_precedence, StackNode::error_cost, length_add(), length_zero(), StackNode::link_count, StackNode::links, StackLink::node, StackNode::node_count, StackNode::position, Subtree::ptr, StackNode::ref_count, ts_malloc, ts_subtree_dynamic_precedence(), ts_subtree_error_cost(), ts_subtree_node_count(), and ts_subtree_total_size().

Referenced by ts_stack_new(), and ts_stack_push().

stack_node_release()

static void stack_node_release ( StackNode *  self, StackNodeArray *  pool, SubtreePool *  subtree_pool  )

static

Definition at line 89 of file stack.c.

  {
recur:
  assert(self->ref_count != 0);
  self->ref_count--;
  if (self->ref_count > 0) return;
 
  StackNode *first_predecessor = NULL;
  if (self->link_count > 0) {
    for (unsigned i = self->link_count - 1; i > 0; i--) {
      StackLink link = self->links[i];
      if (link.subtree.ptr) ts_subtree_release(subtree_pool, link.subtree);
      stack_node_release(link.node, pool, subtree_pool);
    }
    StackLink link = self->links[0];
    if (link.subtree.ptr) ts_subtree_release(subtree_pool, link.subtree);
    first_predecessor = self->links[0].node;
  }
 
  if (pool->size < MAX_NODE_POOL_SIZE) {
    array_push(pool, self);
  } else {
    ts_free(self);
  }
 
  if (first_predecessor) {
    self = first_predecessor;
    goto recur;
  }
}

References array_push, assert(), i, link, StackNode::links, MAX_NODE_POOL_SIZE, StackLink::node, NULL, ts_free, and ts_subtree_release().

Referenced by stack_head_delete(), and ts_stack_delete().

stack_node_retain()

static void stack_node_retain ( StackNode *  self )

static

Definition at line 81 of file stack.c.

                                               {
  if (!self)
    return;
  assert(self->ref_count > 0);
  self->ref_count++;
  assert(self->ref_count != 0);
}

References assert().

Referenced by stack_node_add_link(), ts_stack__add_version(), ts_stack_clear(), and ts_stack_copy_version().

summarize_stack_callback()

StackAction summarize_stack_callback ( void *  payload, const StackIterator *  iterator  )

inline

Definition at line 578 of file stack.c.

                                                                                          {
  SummarizeStackSession *session = payload;
  TSStateId state = iterator->node->state;
  unsigned depth = iterator->subtree_count;
  if (depth > session->max_depth) return StackActionStop;
  for (unsigned i = session->summary->size - 1; i + 1 > 0; i--) {
    StackSummaryEntry entry = session->summary->contents[i];
    if (entry.depth < depth) break;
    if (entry.depth == depth && entry.state == state) return StackActionNone;
  }
  array_push(session->summary, ((StackSummaryEntry) {
    .position = iterator->node->position,
    .depth = depth,
    .state = state,
  }));
  return StackActionNone;
}

References array_push, i, SummarizeStackSession::max_depth, StackActionNone, StackActionStop, and SummarizeStackSession::summary.

Referenced by ts_stack_record_summary().

ts_stack__add_slice()

static void ts_stack__add_slice ( Stack *  self, StackVersion  original_version, StackNode *  node, SubtreeArray *  subtrees  )

static

Definition at line 288 of file stack.c.

  {
  for (uint32_t i = self->slices.size - 1; i + 1 > 0; i--) {
    StackVersion version = self->slices.contents[i].version;
    if (self->heads.contents[version].node == node) {
      StackSlice slice = {*subtrees, version};
      array_insert(&self->slices, i + 1, slice);
      return;
    }
  }
 
  StackVersion version = ts_stack__add_version(self, original_version, node);
  StackSlice slice = { *subtrees, version };
  array_push(&self->slices, slice);
}

References array_insert, array_push, i, and ts_stack__add_version().

Referenced by stack__iter().

ts_stack__add_version()

static StackVersion ts_stack__add_version ( Stack *  self, StackVersion  original_version, StackNode *  node  )

static

Definition at line 270 of file stack.c.

  {
  StackHead head = {
    .node = node,
    .node_count_at_last_error = self->heads.contents[original_version].node_count_at_last_error,
    .last_external_token = self->heads.contents[original_version].last_external_token,
    .status = StackStatusActive,
    .lookahead_when_paused = NULL_SUBTREE,
  };
  array_push(&self->heads, head);
  stack_node_retain(node);
  if (head.last_external_token.ptr) ts_subtree_retain(head.last_external_token);
  return (StackVersion)(self->heads.size - 1);
}

References array_push, test-lz4-versions::head, NULL_SUBTREE, stack_node_retain(), and ts_subtree_retain().

Referenced by ts_stack__add_slice().

ts_stack_can_merge()

bool ts_stack_can_merge	(	Stack *	self,
		StackVersion	version1,
		StackVersion	version2
	)

Definition at line 693 of file stack.c.

                                                                                   {
  StackHead *head1 = &self->heads.contents[version1];
  StackHead *head2 = &self->heads.contents[version2];
  return
    head1->status == StackStatusActive &&
    head2->status == StackStatusActive &&
    head1->node->state == head2->node->state &&
    head1->node->position.bytes == head2->node->position.bytes &&
    head1->node->error_cost == head2->node->error_cost &&
    ts_subtree_external_scanner_state_eq(head1->last_external_token, head2->last_external_token);
}

References Length::bytes, StackNode::error_cost, StackHead::last_external_token, StackHead::node, StackNode::position, StackNode::state, StackHead::status, and ts_subtree_external_scanner_state_eq().

Referenced by ts_parser__better_version_exists(), and ts_stack_merge().

ts_stack_clear()

void ts_stack_clear

(

Stack *

self

)

Definition at line 737 of file stack.c.

                                 {
  stack_node_retain(self->base_node);
  for (uint32_t i = 0; i < self->heads.size; i++) {
    stack_head_delete(&self->heads.contents[i], &self->node_pool, self->subtree_pool);
  }
  array_clear(&self->heads);
  array_push(&self->heads, ((StackHead) {
    .node = self->base_node,
    .status = StackStatusActive,
    .last_external_token = NULL_SUBTREE,
    .lookahead_when_paused = NULL_SUBTREE,
  }));
}

References array_clear, array_push, i, stack_head_delete(), and stack_node_retain().

Referenced by parser__start(), parser_parse(), ts_parser_reset(), and ts_stack_new().

ts_stack_copy_version()

StackVersion ts_stack_copy_version	(	Stack *	self,
		StackVersion	version
	)

Definition at line 669 of file stack.c.

                                                                      {
  assert(version < self->heads.size);
  array_push(&self->heads, self->heads.contents[version]);
  StackHead *head = array_back(&self->heads);
  stack_node_retain(head->node);
  if (head->last_external_token.ptr) ts_subtree_retain(head->last_external_token);
  head->summary = NULL;
  return self->heads.size - 1;
}

References array_back, array_push, assert(), test-lz4-versions::head, NULL, stack_node_retain(), and ts_subtree_retain().

Referenced by parser__recover(), parser__reduce(), and ts_parser__handle_error().

ts_stack_delete()

void ts_stack_delete

(

Stack *

self

)

Definition at line 424 of file stack.c.

                                  {
  if (self->slices.contents)
    array_delete(&self->slices);
  if (self->iterators.contents)
    array_delete(&self->iterators);
  stack_node_release(self->base_node, &self->node_pool, self->subtree_pool);
  for (uint32_t i = 0; i < self->heads.size; i++) {
    stack_head_delete(&self->heads.contents[i], &self->node_pool, self->subtree_pool);
  }
  array_clear(&self->heads);
  if (self->node_pool.contents) {
    for (uint32_t i = 0; i < self->node_pool.size; i++)
      ts_free(self->node_pool.contents[i]);
    array_delete(&self->node_pool);
  }
  array_delete(&self->heads);
  ts_free(self);
}

References array_clear, array_delete, i, stack_head_delete(), stack_node_release(), and ts_free.

Referenced by parser_destroy(), and ts_parser_delete().

ts_stack_dynamic_precedence()

int ts_stack_dynamic_precedence	(	Stack *	self,
		StackVersion	version
	)

Definition at line 615 of file stack.c.

                                                                   {
  return array_get(&self->heads, version)->node->dynamic_precedence;
}

References array_get.

Referenced by ts_parser__better_version_exists(), and ts_parser__version_status().

ts_stack_error_cost()

unsigned ts_stack_error_cost	(	const Stack *	self,
		StackVersion	version
	)

Definition at line 466 of file stack.c.

                                                                      {
  StackHead *head = array_get(&self->heads, version);
  unsigned result = head->node->error_cost;
  if (
    head->status == StackStatusPaused ||
    (head->node->state == ERROR_STATE && !head->node->links[0].subtree.ptr)) {
    result += ERROR_COST_PER_RECOVERY;
  }
  return result;
}

References array_get, ERROR_COST_PER_RECOVERY, ERROR_STATE, and test-lz4-versions::head.

Referenced by ts_parser__condense_stack(), ts_parser__recover(), ts_parser__version_status(), and ts_stack_print_dot_graph().

ts_stack_get_summary()

StackSummary* ts_stack_get_summary	(	Stack *	self,
		StackVersion	version
	)

Definition at line 611 of file stack.c.

                                                                      {
  return array_get(&self->heads, version)->summary;
}

References array_get.

Referenced by ts_parser__recover().

ts_stack_halt()

void ts_stack_halt	(	Stack *	self,
		StackVersion	version
	)

Definition at line 705 of file stack.c.

                                                      {
  array_get(&self->heads, version)->status = StackStatusHalted;
}

References array_get.

Referenced by parser__accept(), parser__better_version_exists(), parser__handle_error(), parser__repair_error(), ts_parser__accept(), ts_parser__recover(), and ts_parser__recover_to_state().

ts_stack_has_advanced_since_error()

bool ts_stack_has_advanced_since_error	(	const Stack *	self,
		StackVersion	version
	)

Definition at line 619 of file stack.c.

                                                                                {
  const StackHead *head = array_get(&self->heads, version);
  const StackNode *node = head->node;
  if (node->error_cost == 0) return true;
  while (node) {
    if (node->link_count > 0) {
      Subtree subtree = node->links[0].subtree;
      if (subtree.ptr) {
        if (ts_subtree_total_bytes(subtree) > 0) {
          return true;
        } else if (
          node->node_count > head->node_count_at_last_error &&
          ts_subtree_error_cost(subtree) == 0
        ) {
          node = node->links[0].node;
          continue;
        }
      }
    }
    break;
  }
  return false;
}

References array_get, StackNode::error_cost, test-lz4-versions::head, StackNode::link_count, StackNode::links, StackLink::node, StackNode::node_count, Subtree::ptr, StackLink::subtree, ts_subtree_error_cost(), and ts_subtree_total_bytes().

Referenced by ts_parser__lex().

ts_stack_is_active()

bool ts_stack_is_active	(	const Stack *	self,
		StackVersion	version
	)

Definition at line 716 of file stack.c.

                                                                 {
  return array_get(&self->heads, version)->status == StackStatusActive;
}

References array_get.

Referenced by ts_parser__better_version_exists(), ts_parser__recover(), and ts_parser_parse().

ts_stack_is_halted()

bool ts_stack_is_halted	(	const Stack *	self,
		StackVersion	version
	)

Definition at line 720 of file stack.c.

                                                                 {
  return array_get(&self->heads, version)->status == StackStatusHalted;
}

References array_get.

Referenced by parser__advance(), parser__better_version_exists(), parser__condense_stack(), parser_parse(), and ts_parser__condense_stack().

ts_stack_is_paused()

bool ts_stack_is_paused	(	const Stack *	self,
		StackVersion	version
	)

Definition at line 724 of file stack.c.

                                                                 {
  return array_get(&self->heads, version)->status == StackStatusPaused;
}

References array_get.

Referenced by ts_parser__condense_stack(), and ts_parser__version_status().

ts_stack_last_external_token()

Subtree ts_stack_last_external_token	(	const Stack *	self,
		StackVersion	version
	)

Definition at line 455 of file stack.c.

                                                                              {
  return array_get(&self->heads, version)->last_external_token;
}

References array_get.

Referenced by ts_parser__advance(), and ts_parser__lex().

ts_stack_merge()

bool ts_stack_merge	(	Stack *	self,
		StackVersion	version1,
		StackVersion	version2
	)

Definition at line 679 of file stack.c.

                                                                               {
  if (!ts_stack_can_merge(self, version1, version2)) return false;
  StackHead *head1 = &self->heads.contents[version1];
  StackHead *head2 = &self->heads.contents[version2];
  for (uint32_t i = 0; i < head2->node->link_count; i++) {
    stack_node_add_link(head1->node, head2->node->links[i], self->subtree_pool);
  }
  if (head1->node->state == ERROR_STATE) {
    head1->node_count_at_last_error = head1->node->node_count;
  }
  ts_stack_remove_version(self, version2);
  return true;
}

References ERROR_STATE, i, StackNode::link_count, StackNode::links, StackHead::node, StackNode::node_count, StackHead::node_count_at_last_error, stack_node_add_link(), StackNode::state, ts_stack_can_merge(), and ts_stack_remove_version().

Referenced by parser__condense_stack(), parser__handle_error(), parser__reduce(), ts_parser__condense_stack(), ts_parser__do_all_potential_reductions(), ts_parser__handle_error(), and ts_parser__reduce().

ts_stack_new()

Stack* ts_stack_new

(

SubtreePool *

subtree_pool

)

Definition at line 405 of file stack.c.

                                               {
  Stack *self = ts_calloc(1, sizeof(Stack));
 
  array_init(&self->heads);
  array_init(&self->slices);
  array_init(&self->iterators);
  array_init(&self->node_pool);
  array_reserve(&self->heads, 4);
  array_reserve(&self->slices, 4);
  array_reserve(&self->iterators, 4);
  array_reserve(&self->node_pool, MAX_NODE_POOL_SIZE);
 
  self->subtree_pool = subtree_pool;
  self->base_node = stack_node_new(NULL, NULL_SUBTREE, false, 1, &self->node_pool);
  ts_stack_clear(self);
 
  return self;
}

References array_init, array_reserve, MAX_NODE_POOL_SIZE, NULL, NULL_SUBTREE, stack_node_new(), ts_calloc, and ts_stack_clear().

Referenced by parser_init(), and ts_parser_new().

ts_stack_node_count_since_error()

unsigned ts_stack_node_count_since_error	(	const Stack *	self,
		StackVersion	version
	)

Definition at line 477 of file stack.c.

                                                                                  {
  StackHead *head = array_get(&self->heads, version);
  if (head->node->node_count < head->node_count_at_last_error) {
    head->node_count_at_last_error = head->node->node_count;
  }
  return head->node->node_count - head->node_count_at_last_error;
}

References array_get, and test-lz4-versions::head.

Referenced by ts_parser__better_version_exists(), ts_parser__recover(), ts_parser__version_status(), ts_parser_has_outstanding_parse(), and ts_stack_print_dot_graph().

ts_stack_pause()

void ts_stack_pause	(	Stack *	self,
		StackVersion	version,
		Subtree	lookahead
	)

Definition at line 709 of file stack.c.

                                                                          {
  StackHead *head = array_get(&self->heads, version);
  head->status = StackStatusPaused;
  head->lookahead_when_paused = lookahead;
  head->node_count_at_last_error = head->node->node_count;
}

References array_get, and test-lz4-versions::head.

Referenced by ts_parser__advance().

ts_stack_pop_all()

StackSliceArray ts_stack_pop_all	(	Stack *	self,
		StackVersion	version
	)

Definition at line 569 of file stack.c.

                                                                    {
  return stack__iter(self, version, pop_all_callback, NULL, 0);
}

References NULL, pop_all_callback(), and stack__iter().

Referenced by parser__accept(), and ts_parser__accept().

ts_stack_pop_count()

StackSliceArray ts_stack_pop_count	(	Stack *	self,
		StackVersion	version,
		uint32_t	count
	)

Definition at line 507 of file stack.c.

                                                                                      {
  return stack__iter(self, version, pop_count_callback, &count, count);
}

References count, pop_count_callback(), and stack__iter().

Referenced by parser__reduce(), ts_parser__recover(), ts_parser__recover_to_state(), and ts_parser__reduce().

ts_stack_pop_error()

SubtreeArray ts_stack_pop_error	(	Stack *	self,
		StackVersion	version
	)

Definition at line 547 of file stack.c.

                                                                   {
  StackNode *node = array_get(&self->heads, version)->node;
  for (unsigned i = 0; i < node->link_count; i++) {
    if (node->links[i].subtree.ptr && ts_subtree_is_error(node->links[i].subtree)) {
      bool found_error = false;
      StackSliceArray pop = stack__iter(self, version, pop_error_callback, &found_error, 1);
      if (pop.size > 0) {
        assert(pop.size == 1);
        ts_stack_renumber_version(self, pop.contents[0].version, version);
        return pop.contents[0].subtrees;
      }
      break;
    }
  }
  return (SubtreeArray) {.size = 0};
}

References array_get, assert(), i, StackNode::link_count, StackNode::links, pop_error_callback(), Subtree::ptr, stack__iter(), StackLink::subtree, ts_stack_renumber_version(), and ts_subtree_is_error().

Referenced by ts_parser__recover_to_state().

ts_stack_pop_pending()

StackSliceArray ts_stack_pop_pending	(	Stack *	self,
		StackVersion	version
	)

Definition at line 524 of file stack.c.

                                                                        {
  StackSliceArray pop = stack__iter(self, version, pop_pending_callback, NULL, 0);
  if (pop.size > 0) {
    ts_stack_renumber_version(self, pop.contents[0].version, version);
    pop.contents[0].version = version;
  }
  return pop;
}

References NULL, pop_pending_callback(), stack__iter(), ts_stack_renumber_version(), and version.

Referenced by parser__breakdown_top_of_stack(), and ts_parser__breakdown_top_of_stack().

ts_stack_position()

Length ts_stack_position	(	const Stack *	self,
		StackVersion	version
	)

Definition at line 451 of file stack.c.

                                                                  {
  return array_get(&self->heads, version)->node->position;
}

References array_get.

Referenced by ts_parser__advance(), ts_parser__better_version_exists(), ts_parser__handle_error(), ts_parser__lex(), ts_parser__recover(), and ts_parser_parse().

ts_stack_print_dot_graph()

bool ts_stack_print_dot_graph	(	Stack *	self,
		const TSLanguage *	language,
		FILE *	f
	)

Definition at line 751 of file stack.c.

                                                                                {
  array_reserve(&self->iterators, 32);
  if (!f) f = stderr;
 
  fprintf(f, "digraph stack {\n");
  fprintf(f, "rankdir=\"RL\";\n");
  fprintf(f, "edge [arrowhead=none]\n");
 
  Array(StackNode *) visited_nodes = array_new();
 
  array_clear(&self->iterators);
  for (uint32_t i = 0; i < self->heads.size; i++) {
    StackHead *head = &self->heads.contents[i];
    if (head->status == StackStatusHalted) continue;
 
    fprintf(f, "node_head_%u [shape=none, label=\"\"]\n", i);
    fprintf(f, "node_head_%u -> node_%p [", i, (void *)head->node);
 
    if (head->status == StackStatusPaused) {
      fprintf(f, "color=red ");
    }
    fprintf(f,
      "label=%u, fontcolor=blue, weight=10000, labeltooltip=\"node_count: %u\nerror_cost: %u",
      i,
      ts_stack_node_count_since_error(self, i),
      ts_stack_error_cost(self, i)
    );
 
    if (head->summary) {
      fprintf(f, "\nsummary_size: %u", head->summary->size);
    }
 
    if (head->last_external_token.ptr) {
      const ExternalScannerState *state = &head->last_external_token.ptr->external_scanner_state;
      const char *data = ts_external_scanner_state_data(state);
      fprintf(f, "\nexternal_scanner_state:");
      for (uint32_t j = 0; j < state->length; j++) fprintf(f, " %2X", data[j]);
    }
 
    fprintf(f, "\"]\n");
    array_push(&self->iterators, ((StackIterator) {
      .node = head->node
    }));
  }
 
  bool all_iterators_done = false;
  while (!all_iterators_done) {
    all_iterators_done = true;
 
    for (uint32_t i = 0; i < self->iterators.size; i++) {
      StackIterator iterator = self->iterators.contents[i];
      StackNode *node = iterator.node;
 
      for (uint32_t j = 0; j < visited_nodes.size; j++) {
        if (visited_nodes.contents[j] == node) {
          node = NULL;
          break;
        }
      }
 
      if (!node) continue;
      all_iterators_done = false;
 
      fprintf(f, "node_%p [", (void *)node);
      if (node->state == ERROR_STATE) {
        fprintf(f, "label=\"?\"");
      } else if (
        node->link_count == 1 &&
        node->links[0].subtree.ptr &&
        ts_subtree_extra(node->links[0].subtree)
      ) {
        fprintf(f, "shape=point margin=0 label=\"\"");
      } else {
        fprintf(f, "label=\"%d\"", node->state);
      }
 
      fprintf(
        f,
        " tooltip=\"position: %u,%u\nnode_count:%u\nerror_cost: %u\ndynamic_precedence: %d\"];\n",
        node->position.extent.row + 1,
        node->position.extent.column,
        node->node_count,
        node->error_cost,
        node->dynamic_precedence
      );
 
      for (int j = 0; j < node->link_count; j++) {
        StackLink link = node->links[j];
        fprintf(f, "node_%p -> node_%p [", (void *)node, (void *)link.node);
        if (link.is_pending) fprintf(f, "style=dashed ");
        if (link.subtree.ptr && ts_subtree_extra(link.subtree)) fprintf(f, "fontcolor=gray ");
 
        if (!link.subtree.ptr) {
          fprintf(f, "color=red");
        } else {
          fprintf(f, "label=\"");
          bool quoted = ts_subtree_visible(link.subtree) && !ts_subtree_named(link.subtree);
          if (quoted) fprintf(f, "'");
          const char *name = ts_language_symbol_name(language, ts_subtree_symbol(link.subtree));
          for (const char *c = name; *c; c++) {
            if (*c == '\"' || *c == '\\') fprintf(f, "\\");
            fprintf(f, "%c", *c);
          }
          if (quoted) fprintf(f, "'");
          fprintf(f, "\"");
          fprintf(
            f,
            "labeltooltip=\"error_cost: %u\ndynamic_precedence: %u\"",
            ts_subtree_error_cost(link.subtree),
            ts_subtree_dynamic_precedence(link.subtree)
          );
        }
 
        fprintf(f, "];\n");
 
        StackIterator *next_iterator;
        if (j == 0) {
          next_iterator = &self->iterators.contents[i];
        } else {
          array_push(&self->iterators, iterator);
          next_iterator = array_back(&self->iterators);
        }
        next_iterator->node = link.node;
      }
 
      array_push(&visited_nodes, node);
    }
  }
 
  fprintf(f, "}\n");
 
  array_delete(&visited_nodes);
  return true;
}

References Array(), array_back, array_clear, array_delete, array_new, array_push, array_reserve, c, TSPoint::column, StackNode::dynamic_precedence, StackNode::error_cost, ERROR_STATE, Length::extent, f, test-lz4-versions::head, i, link, StackNode::link_count, StackNode::links, StackIterator::node, StackNode::node_count, NULL, StackNode::position, Subtree::ptr, TSPoint::row, StackNode::state, StackLink::subtree, ts_external_scanner_state_data(), ts_language_symbol_name(), ts_stack_error_cost(), ts_stack_node_count_since_error(), ts_subtree_dynamic_precedence(), ts_subtree_error_cost(), ts_subtree_extra(), ts_subtree_named(), ts_subtree_symbol(), and ts_subtree_visible().

ts_stack_push()

void ts_stack_push	(	Stack *	self,
		StackVersion	version,
		Subtree	subtree,
		bool	pending,
		TSStateId	state
	)

Definition at line 485 of file stack.c.

  {
  StackHead *head = array_get(&self->heads, version);
  StackNode *new_node = stack_node_new(head->node, subtree, pending, state, &self->node_pool);
  if (!subtree.ptr) head->node_count_at_last_error = new_node->node_count;
  head->node = new_node;
}

References array_get, test-lz4-versions::head, StackNode::node_count, Subtree::ptr, and stack_node_new().

Referenced by parser__accept(), parser__breakdown_top_of_stack(), parser__handle_error(), parser__push(), parser__reduce(), parser__shift(), ts_parser__accept(), ts_parser__breakdown_top_of_stack(), ts_parser__handle_error(), ts_parser__recover(), ts_parser__recover_to_state(), ts_parser__reduce(), and ts_parser__shift().

ts_stack_record_summary()

void ts_stack_record_summary	(	Stack *	self,
		StackVersion	version,
		unsigned	max_depth
	)

Definition at line 596 of file stack.c.

                                                                                    {
  SummarizeStackSession session = {
    .summary = ts_malloc(sizeof(StackSummary)),
    .max_depth = max_depth
  };
  array_init(session.summary);
  stack__iter(self, version, summarize_stack_callback, &session, -1);
  StackHead *head = &self->heads.contents[version];
  if (head->summary) {
    array_delete(head->summary);
    ts_free(head->summary);
  }
  head->summary = session.summary;
}

References array_delete, array_init, test-lz4-versions::head, stack__iter(), summarize_stack_callback(), SummarizeStackSession::summary, ts_free, ts_malloc, and version.

Referenced by ts_parser__handle_error().

ts_stack_remove_version()

void ts_stack_remove_version	(	Stack *	self,
		StackVersion	version
	)

Definition at line 643 of file stack.c.

                                                                {
  stack_head_delete(array_get(&self->heads, version), &self->node_pool, self->subtree_pool);
  array_erase(&self->heads, version);
}

References array_erase, array_get, and stack_head_delete().

Referenced by parser__accept(), parser__condense_stack(), parser__do_potential_reductions(), parser__recover(), parser__reduce(), parser__repair_error(), ts_parser__accept(), ts_parser__condense_stack(), ts_parser__do_all_potential_reductions(), ts_parser__recover(), ts_parser__reduce(), and ts_stack_merge().

ts_stack_renumber_version()

void ts_stack_renumber_version	(	Stack *	self,
		StackVersion	v1,
		StackVersion	v2
	)

Definition at line 648 of file stack.c.

                                                                              {
  if (v1 == v2) return;
  assert(v2 < v1);
  assert((uint32_t)v1 < self->heads.size);
  StackHead *source_head = &self->heads.contents[v1];
  StackHead *target_head = &self->heads.contents[v2];
  if (target_head->summary && !source_head->summary) {
    source_head->summary = target_head->summary;
    target_head->summary = NULL;
  }
  stack_head_delete(target_head, &self->node_pool, self->subtree_pool);
  *target_head = *source_head;
  array_erase(&self->heads, v1);
}

References array_erase, assert(), NULL, stack_head_delete(), StackHead::summary, and v1.

Referenced by parser__advance(), parser__do_potential_reductions(), parser__repair_error(), ts_parser__advance(), ts_parser__do_all_potential_reductions(), ts_parser__recover(), ts_stack_pop_error(), and ts_stack_pop_pending().

ts_stack_resume()

Subtree ts_stack_resume	(	Stack *	self,
		StackVersion	version
	)

Definition at line 728 of file stack.c.

                                                           {
  StackHead *head = array_get(&self->heads, version);
  assert(head->status == StackStatusPaused);
  Subtree result = head->lookahead_when_paused;
  head->status = StackStatusActive;
  head->lookahead_when_paused = NULL_SUBTREE;
  return result;
}

References array_get, assert(), test-lz4-versions::head, and NULL_SUBTREE.

Referenced by ts_parser__condense_stack().

ts_stack_set_last_external_token()

void ts_stack_set_last_external_token	(	Stack *	self,
		StackVersion	version,
		Subtree	token
	)

Definition at line 459 of file stack.c.

                                                                                        {
  StackHead *head = array_get(&self->heads, version);
  if (token.ptr) ts_subtree_retain(token);
  if (head->last_external_token.ptr) ts_subtree_release(self->subtree_pool, head->last_external_token);
  head->last_external_token = token;
}

References array_get, test-lz4-versions::head, Subtree::ptr, ts_subtree_release(), and ts_subtree_retain().

Referenced by ts_parser__recover(), and ts_parser__shift().

ts_stack_state()

TSStateId ts_stack_state	(	const Stack *	self,
		StackVersion	version
	)

Definition at line 447 of file stack.c.

                                                                  {
  return array_get(&self->heads, version)->node->state;
}

References array_get.

Referenced by ts_parser__advance(), ts_parser__breakdown_top_of_stack(), ts_parser__do_all_potential_reductions(), ts_parser__handle_error(), ts_parser__recover(), ts_parser__recover_to_state(), ts_parser__reduce(), ts_parser__reuse_node(), ts_parser__version_status(), ts_parser_has_outstanding_parse(), and ts_parser_parse().

ts_stack_swap_versions()

void ts_stack_swap_versions	(	Stack *	self,
		StackVersion	v1,
		StackVersion	v2
	)

Definition at line 663 of file stack.c.

                                                                           {
  StackHead temporary_head = self->heads.contents[v1];
  self->heads.contents[v1] = self->heads.contents[v2];
  self->heads.contents[v2] = temporary_head;
}

References v1.

Referenced by ts_parser__condense_stack().

ts_stack_version_count()

uint32_t ts_stack_version_count

(

const Stack *

self

)

Definition at line 443 of file stack.c.

                                                   {
  return self->heads.size;
}

Referenced by parser__better_version_exists(), parser__condense_stack(), parser__do_potential_reductions(), parser__handle_error(), parser__reduce(), parser__shift(), parser_parse(), ts_parser__better_version_exists(), ts_parser__condense_stack(), ts_parser__do_all_potential_reductions(), ts_parser__handle_error(), ts_parser__recover(), ts_parser__reduce(), and ts_parser_parse().

Variable Documentation

StackStatus

StackStatus

Definition at line 52 of file stack.c.