xref: /external/srec/srec/crec/astar.c

/*---------------------------------------------------------------------------*
 *  astar.c  *
 *                                                                           *
 *  Copyright 2007, 2008 Nuance Communciations, Inc.                               *
 *                                                                           *
 *  Licensed under the Apache License, Version 2.0 (the 'License');          *
 *  you may not use this file except in compliance with the License.         *
 *                                                                           *
 *  You may obtain a copy of the License at                                  *
 *      http://www.apache.org/licenses/LICENSE-2.0                           *
 *                                                                           *
 *  Unless required by applicable law or agreed to in writing, software      *
 *  distributed under the License is distributed on an 'AS IS' BASIS,        *
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. *
 *  See the License for the specific language governing permissions and      *
 *  limitations under the License.                                           *
 *                                                                           *
 *---------------------------------------------------------------------------*/

#include "pstdio.h"
#include "passert.h"

#include"srec_sizes.h"
#include"search_network.h"
#include"srec.h"
#include"srec_context.h"
#include"word_lattice.h"
#include "portable.h"
#include "srec_stats.h"
#include "astar.h"
#include "astar_pphash.h"

#ifdef SET_RCSID
static const char *rcsid = 0 ? (const char *) &rcsid :
                           "$Id: astar.c,v 1.19.4.9 2008/04/30 15:12:15 dahan Exp $";
#endif

#define PRINT_ASTAR_SOMEWHAT  0
#define PRINT_ASTAR_DETAILS   0
#define PRINT_ASTAR_QBT_DETAILS   0 /* Quick Back Trace */
#define MAX_NBEST_LEN        32
#define NBEST_LEN_MARGIN     10
#define MAX_NUM_PARPS       400 /* 3*MAX_NBEST_LEN*MAX_WORDS_PER_COMPLETE_PATH need better dup
													         check on complete paths */
#define ASTAR_PRUNE_DELTA 20000
#define DEBUG_PARP_MANAGEMENT 0

#if PRINT_ASTAR_DETAILS
static int do_draw_as_dotty = 0;
static int do_draw_file_idx = 0;

int astar_draw_tree_as_dotty(const char* file, srec* rec, AstarStack* stack);
#endif

/*
  The word graph is represented as an arc_token_list,
  arc_token's are chained together 2 linked lists,
  arc_token->first_next_arc ... like a "TO" node
  arc_token->next_arc_index ... a linked list of arcs leaving the same node

  get_arc_for_word() finds the arc_token for a particular extension
  backward though the word graph (ie. forward through the reverse word graph)

*/

#define ARC_TOKEN_ONE (arc_token*)1
arc_token* get_arc_for_word(arc_token* atoken, wordID word,
                            void* context_void,
                            wordID terminal_word)
{
  srec_context* context = (srec_context*)context_void;
  arc_token* arc_token_list = context->arc_token_list;
  arc_token* tmp;
  wordmap* wmap = context->olabels;

  if (atoken == ARC_TOKEN_ONE)
  {
    /* log_report("Warning:  bad thing is happening word=%d\n", word); */
    return 0;
  }
  else if (atoken == 0)
  {
    arc_token root_arc;
    root_arc.first_next_arc = ARC_TOKEN_LNK(arc_token_list, 0);
    root_arc.next_token_index = ARC_TOKEN_NULL;
    root_arc.ilabel = root_arc.olabel = 0;
    return get_arc_for_word(&root_arc, word, context_void, terminal_word);

    /* the arc token is NULL for partial paths just starting; but
       the word graph has nasty epsilons at the beginning, we'll remove
       them later, but must handle them in the mean time. */
    atoken = &arc_token_list[0];
    for (; atoken; atoken = ARC_TOKEN_PTR(arc_token_list, atoken->next_token_index))
    {
      if (atoken->ilabel == word)
        return atoken;
      else if (atoken->ilabel == WORD_EPSILON_LABEL)
      {
        for (tmp = ARC_TOKEN_PTR(arc_token_list, atoken->first_next_arc); tmp;
             tmp = ARC_TOKEN_PTR(arc_token_list, tmp->next_token_index))
          if (tmp->ilabel == word)
            return tmp;
      }
      else if (atoken->ilabel < wmap->num_slots)
      {
        if (wordmap_whether_in_rule(wmap, word, atoken->ilabel))
          return atoken;
      }
    }
    return 0;
  }
  else if (word == terminal_word)
  {
    /* -pau- LABEL, the word graph does not seem to have them! */
    tmp = ARC_TOKEN_PTR(arc_token_list, atoken->first_next_arc);
    if (!tmp)
      return ARC_TOKEN_ONE;
    else if (tmp->first_next_arc == ARC_TOKEN_NULL && (tmp->ilabel == MAXwordID || tmp->ilabel == terminal_word))
      return ARC_TOKEN_ONE;
    else
    {
      /* again more weirdness in the output graph format1
      might be due to multiple endnodes? */
      for (tmp = ARC_TOKEN_PTR(arc_token_list, atoken->first_next_arc); tmp;
           tmp = ARC_TOKEN_PTR(arc_token_list, tmp->next_token_index))
        if (tmp->ilabel == MAXwordID && tmp->first_next_arc == ARC_TOKEN_NULL)
          return ARC_TOKEN_ONE;
      return 0;
    }
  }
  else
  {
#if PRINT_ASTAR_DETAILS
    printf("word %d allowed? ", word);
#endif
    if (atoken->first_next_arc == ARC_TOKEN_NULL)
      return 0;
    else
      tmp = ARC_TOKEN_PTR(arc_token_list, atoken->first_next_arc);
    /* handle single epsilons */
    if (tmp->ilabel == WORD_EPSILON_LABEL && tmp->next_token_index == ARC_TOKEN_NULL)
      tmp = ARC_TOKEN_PTR(arc_token_list, tmp->first_next_arc);
    for (; tmp; tmp = ARC_TOKEN_PTR(arc_token_list, tmp->next_token_index))
    {
#if PRINT_ASTAR_DETAILS
      printf(" W%d(%s)", tmp->ilabel, tmp->ilabel != MAXwordID ? wmap->words[tmp->ilabel] : "");
#endif
      if (tmp->ilabel == word)
      {
#if PRINT_ASTAR_DETAILS
        printf("\n");
#endif
        return tmp;
      }
      else if (tmp->ilabel < wmap->num_slots)
      {
        if (wordmap_whether_in_rule(wmap, word, tmp->ilabel))
          return tmp;
      }
    }
#if PRINT_ASTAR_DETAILS
    printf("\n");
#endif
    return 0;
  }
}

arc_token* get_arc_for_word_without_slot_annotation(arc_token* atoken, const char* word,
    void* context_void,
    wordID terminal_word)
{
  srec_context* context = (srec_context*)context_void;
  arc_token* arc_token_list = context->arc_token_list;
  arc_token* tmp;
  wordmap* wmap = context->olabels;
  wordID wdid = wordmap_find_index(wmap, word);

  if (atoken == ARC_TOKEN_ONE)
  {
    /* log_report("Warning:  bad thing is happening word=%d\n", word); */
    return 0;
  }
  else if (atoken == NULL)
  {
    arc_token root_arc;
    root_arc.first_next_arc = ARC_TOKEN_LNK(arc_token_list, 0);
    root_arc.next_token_index = ARC_TOKEN_NULL;
    root_arc.ilabel = root_arc.olabel = 0;
    return get_arc_for_word_without_slot_annotation(&root_arc, word, context_void, terminal_word);
  }
  else if (word == NULL)
  {
    /* -pau- LABEL, the word graph does not seem to have them! */
    tmp = ARC_TOKEN_PTR(arc_token_list, atoken->first_next_arc);
    if (!tmp)
      return ARC_TOKEN_ONE;
    else if (!tmp->first_next_arc && (tmp->ilabel == MAXwordID || tmp->ilabel == terminal_word))
      return ARC_TOKEN_ONE;
    else
    {
      /* again more weirdness in the output graph format1
      might be due to multiple endnodes? */
      for (tmp = ARC_TOKEN_PTR(arc_token_list, atoken->first_next_arc); tmp;
           tmp = ARC_TOKEN_PTR(arc_token_list, tmp->next_token_index))
        if (tmp->ilabel == MAXwordID && tmp->first_next_arc == ARC_TOKEN_NULL)
          return ARC_TOKEN_ONE;
      return 0;
    }
  }
  else
  {
    for (tmp = ARC_TOKEN_PTR(arc_token_list, atoken->first_next_arc); tmp;
         tmp = ARC_TOKEN_PTR(arc_token_list, tmp->next_token_index))
    {
      if (tmp->ilabel == wdid)
      {
        return tmp;
      }
      else if (tmp->ilabel < wmap->num_slots)
      {
        wdid = wordmap_find_index_in_rule(wmap, word, tmp->ilabel);
        if (wdid != MAXwordID)
          return tmp;
      }
      else if (tmp->ilabel == WORD_EPSILON_LABEL)
      {
        tmp = ARC_TOKEN_PTR(arc_token_list, tmp->first_next_arc);
        tmp = get_arc_for_word_without_slot_annotation(tmp, word, context_void, terminal_word);
        if (tmp) return tmp;
      }
    }
    return 0;
  }
}

/* protos */
#if DEBUG_PARP_MANAGEMENT
void list_free_parps(AstarStack* stack, char* msg);
#else
#define list_free_parps(stack,msg)
#endif

void print_partial_paths(partial_path** parps, int num_parps, srec* rec, const char* msg);
void print_path(partial_path* path, srec* rec, char* msg);
void sort_partial_paths(partial_path** parps, int num_parps);
void insert_partial_path(partial_path** parps, int *pnum_parps,
                         partial_path* insert_parp);
partial_path* make_new_partial_path(AstarStack* stack);
/*void free_partial_path(AstarStack* stack, partial_path* parp); put the proto in astar.h */

/* functions */

void append_arc_arriving(partial_path* path, partial_path* prev_path)
{
  partial_path** pprev;
  for (pprev = &path->first_prev_arc; (*pprev); pprev = &(*pprev)->linkl_prev_arc)
    ASSERT(*pprev != prev_path);
  *pprev = prev_path;
#if DEBUG_PARP_MANAGEMENT
  if (1)
  {
    int i, j;
    partial_path* path_list[256], *k;
    memset(path_list, 0, sizeof(partial_path*)*32);
    for (i = 0, k = path->first_prev_arc; k; k = k->linkl_prev_arc)
    {
      for (j = 0; j < i; j++)
        if (k == path_list[j])
          ASSERT(0);
      path_list[i++] = k;
    }
  }
#endif
}

static void remove_path_arriving(partial_path* path, partial_path* prev_path)
{
  partial_path** pprev;
  if (!path) return;
  for (pprev = &path->first_prev_arc; (*pprev); pprev = &(*pprev)->linkl_prev_arc)
    if (*pprev == prev_path)
    {
      *pprev = (*pprev)->linkl_prev_arc;
      return;
    }
  ASSERT(0);
}

partial_path* extend_path(AstarStack* stack,
                          partial_path* parp,
                          wtokenID extend_token_index,
                          arc_token* arc_for_extend_token_index,
                          bigcostdata max_cost,
                          word_token* word_token_array,
                          int* pwhether_complete)
{
  asr_int32_t netcost;
  partial_path* extended_parp;
  word_token* wtoken;
  costdata best_cost_for_node;
  wtokenID best_extend_token;
  partial_path* alt_extension;
  int sanity_count;

  wtoken = &word_token_array[ extend_token_index];

  if (wtoken->end_time > word_token_array[parp->token_index].end_time)
  {
    /* 20030921: this should never happen but we keep it for stop gap */
    /* why does it happen: when in srec_process_word_boundary() we
       occasionally kill_fsm_nodes_for_word_backtrace() but we did not kill the
       stokens for this backtrace, neither did we kill the altword_tokens.  it
       would just take too long to go through all of them, and so occasionally
       there may leak some bad backtraces */
    return 0;
  }

  /* finding the netcost of this path extension */
  best_extend_token = word_token_array[ parp->token_index].backtrace;
  best_cost_for_node = word_token_array[ best_extend_token].cost;
  wtoken = &word_token_array[ extend_token_index];
  ASSERT(word_token_array[best_extend_token].end_time ==
         word_token_array[extend_token_index].end_time);
  netcost = wtoken->cost - best_cost_for_node;
  /* ASSERT( netcost > 0); bug: sometimes this fails! fix: just use int32 */
  if (netcost + parp->costsofar > max_cost)
  {
#if PRINT_ASTAR_DETAILS
    printf("netcost %d (%d+%d) + parp->costsofar > max_cost %d\n",
           netcost, wtoken->cost, best_cost_for_node, parp->costsofar, max_cost);
#endif
    return 0;
  }

  /* check if we have a similar thing already extended */
  sanity_count = 0;
  for (alt_extension = parp->first_prev_arc; alt_extension;
       alt_extension = alt_extension->linkl_prev_arc)
  {
    wtokenID alt_token_index = alt_extension->token_index;
    wtokenID alt_bt_token_index;
    wtokenID bt_token_index;
    word_token* alt_wtoken;
    int join_frame_diff; /* need a signed frameID */

    ASSERT(sanity_count++ < 30);
    if (alt_token_index == MAXwtokenID)
      continue;
    alt_wtoken = &word_token_array[alt_token_index];
    if (alt_wtoken->word != wtoken->word)
      continue;

    alt_bt_token_index = alt_wtoken->backtrace;
    bt_token_index = wtoken->backtrace;
    if (alt_bt_token_index == MAXwtokenID && bt_token_index != MAXwtokenID)
      continue;
    else if (alt_bt_token_index != MAXwtokenID && bt_token_index == MAXwtokenID)
      continue;
    else if (alt_bt_token_index != MAXwtokenID && bt_token_index != MAXwtokenID)
    {
      word_token* alt_wtoken_bt;
      word_token* wtoken_bt;
      alt_wtoken_bt = &word_token_array[ alt_wtoken->backtrace];
      wtoken_bt = &word_token_array[ wtoken->backtrace];
      if (alt_wtoken_bt->word != wtoken_bt->word)
        continue;
    }

    join_frame_diff = alt_wtoken->end_time - wtoken->end_time;
    if (join_frame_diff < 0) join_frame_diff = -join_frame_diff;
    if (join_frame_diff > 5)
      continue;

    /* the proposed extension is similar in "all" ways to an existing
       extension, so let's not make this new extension */
#if PRINT_ASTAR_DETAILS
    printf("proposed extension already done elsewhere\n");
#endif
    return 0;
  }

  /* this is a TRUE new extension, so let's extend for sure */
  extended_parp = make_new_partial_path(stack);
  if (!extended_parp)
  {
#if PRINT_ASTAR_DETAILS
    printf("make_new_partial_path returned 0\n");
#endif
    return 0;
  }
  extended_parp->costsofar = parp->costsofar + netcost;
  extended_parp->token_index = extend_token_index;
  if (extend_token_index != MAXwtokenID)
    extended_parp->word = word_token_array[ extend_token_index].word;
  else
    extended_parp->word = MAXwordID;
  if (wtoken->backtrace == MAXwtokenID)
  {
    *pwhether_complete = 1;
    extended_parp->first_prev_arc = PARP_TERMINAL;
  }
  else
  {
    *pwhether_complete = 0;
  }
  extended_parp->arc_for_wtoken = arc_for_extend_token_index;

  extended_parp->refcount = 1;
  parp->refcount++;

  /* maintain the parp tree */
  extended_parp->next = parp;
  append_arc_arriving(parp, extended_parp);
#if PRINT_ASTAR_DETAILS
  printf("extend path returned %x\n", extended_parp);
#endif

  return extended_parp;
}

void check_stack_root_sanity(AstarStack* stack)
{
  partial_path* parp1 = stack->root_path;
  /* append_arc_arriving(stack->root_path, parp); */
  for (; parp1->linkl_prev_arc != NULL; parp1 = parp1->linkl_prev_arc)
    ASSERT(parp1 != parp1->linkl_prev_arc);
}

/*
 * make a blank partial path, free one if necessary
 */

partial_path* make_new_partial_path(AstarStack* stack)
{
  partial_path* return_parp = stack->free_parp_list;
  if (return_parp)
  {
    stack->free_parp_list = return_parp->next;
    memset((void*)return_parp, 0, sizeof(*return_parp)); /* needed */
  }
  else
  {
    log_report("Warning: ran out of partial_paths, reprune\n");
#if PRINT_ASTAR_DETAILS
    printf("Warning: ran out of partial_paths, reprune\n");
#endif
    /* kill the last one, and return it, this may free more than one parp! */
    if (stack->num_active_paths == 0)
      return 0;
    stack->num_active_paths--;
    return_parp = stack->active_paths[stack->num_active_paths];
    hash_del((FixedSizeHash*)stack->pphash, return_parp);
    free_partial_path(stack, return_parp);
    return_parp = stack->free_parp_list;
    stack->free_parp_list = return_parp->next;
    memset((void*)return_parp, 0, sizeof(*return_parp)); /* needed */
  }
  return return_parp;
}

/* free_partial_path
   frees the path that was passed in, and also any backpointers.
   refcount counts the number of parps that depend on this parp */
void free_partial_path(AstarStack* stack, partial_path* parp)
{
  partial_path* next_parp;
  for (; parp; parp = next_parp)
  {
    next_parp = parp->next;
    parp->refcount--;
    if (parp->refcount == 0)
    {    /* first time around this always passes */
      remove_path_arriving(parp->next, parp);
      parp->next = stack->free_parp_list;
      stack->free_parp_list = parp;
    }
    else break;
  }
}

/*
 * make a partial path from a single word at the very end of the graph
 */

partial_path* make_partial_path(AstarStack* stack,
                                wtokenID token_index, srec* rec,
                                int* pwhether_complete)
{
  partial_path* parp;
  word_token* wtoken;

  /* todo: replace this with partial_path_tokens! */
  parp = make_new_partial_path(stack);
  if (!parp) return parp;

  wtoken = &rec->word_token_array[token_index];
  parp->token_index = token_index;
  if (token_index != MAXwtokenID)
    parp->word = rec->word_token_array[ token_index].word;
  else
    parp->word = MAXwordID;
  /* wtoken->end_time should be equal to rec->current_search_frame */
  ASSERT(rec->accumulated_cost_offset[ wtoken->end_time] != 0);
  parp->costsofar = rec->accumulated_cost_offset[ wtoken->end_time];
  parp->costsofar += wtoken->cost;
  /* BKWD: rec->word_token_array[ wtoken->backtrace].cost + acc[] */
  /* FRWD: wtoken->cost + acc[] - rec->word_token_array[ wtoken->backtrace].cost + acc[] */
  parp->next = 0;
  parp->first_prev_arc = parp->linkl_prev_arc = 0;
  if (wtoken->backtrace == MAXwtokenID)
    *pwhether_complete = 1;
  else
    *pwhether_complete = 0;
  parp->arc_for_wtoken = 0;
  parp->refcount = 1;
  return parp;
}

/* initialize astar search */

AstarStack* astar_stack_make(srec* rec, int max_nbest_len)
{
  int i;
  AstarStack *stack;

  /* allocations */
  stack = (AstarStack*)CALLOC_CLR(1, sizeof(AstarStack), "search.astar.base");
  stack->max_active_paths = max_nbest_len + NBEST_LEN_MARGIN * 3;
  stack->max_complete_paths = max_nbest_len + NBEST_LEN_MARGIN;
  stack->complete_paths = (partial_path**)CALLOC_CLR(stack->max_complete_paths, sizeof(partial_path*), "search.astar.cplist");
  stack->complete_path_confidences = (int*)CALLOC_CLR(stack->max_complete_paths, sizeof(int), "search.astar.confvalues");
  stack->active_paths = (partial_path**)CALLOC_CLR(stack->max_active_paths, sizeof(partial_path*), "search.astar.aplist");
  stack->prune_delta = ASTAR_PRUNE_DELTA;

  stack->num_complete_paths = 0;
  stack->num_active_paths = 0;

  stack->partial_path_array = (partial_path*)CALLOC_CLR(MAX_NUM_PARPS, sizeof(stack->partial_path_array[0]), "search.astar.pparray");
  stack->partial_path_array_size = MAX_NUM_PARPS;

  stack->free_parp_list = &stack->partial_path_array[0];
  for (i = 1; i < MAX_NUM_PARPS; i++)
  {
    stack->partial_path_array[i-1].next = &stack->partial_path_array[i];
  }
  stack->partial_path_array[i-1].next = 0;
  stack->root_path = 0;

  stack->pphash = (void*)CALLOC_CLR(1, sizeof(FixedSizeHash), "search.astar.pphash");
  astar_stack_clear(stack);
  return stack;
}

int astar_stack_destroy(srec* rec)
{
  AstarStack *stack = rec->astar_stack;
  FREE(stack->active_paths);
  FREE(stack->complete_paths);
  FREE(stack->complete_path_confidences);
  FREE(stack->partial_path_array);
  FREE(stack->pphash);
  FREE(stack);
  rec->astar_stack = 0;
  return 0;
}

/* prepares for astar after forward search on an utterance */

int astar_stack_prepare(AstarStack* stack, int request_nbest_len, srec* rec)
{
  wtokenID token_index;
  word_token* wtoken;
  partial_path* parp;
  int whether_complete;
  frameID end_frame = rec->current_search_frame;
  int num_wordends;

  list_free_parps(stack, "astar_stack_prepare ");

  stack->num_active_paths = 0;
  stack->num_complete_paths = 0;

  stack->root_path = make_new_partial_path(stack);
  ASSERT(stack->root_path);
  stack->root_path->refcount = 9999;
  stack->root_path->token_index = MAXwtokenID;
  stack->root_path->word = MAXwordID;

  num_wordends = 0;
  for (token_index = rec->word_lattice->words_for_frame[end_frame];
       token_index != MAXwtokenID;
       token_index = wtoken->next_token_index)
  {
    num_wordends++;
    wtoken = &rec->word_token_array[ token_index];
    parp = make_partial_path(stack, token_index, rec, &whether_complete);
    if (!parp)
    {
      log_report("Error: out-of-memory in astar_stack_prepare(), "
                 "num_wordends %d\n", num_wordends);
      stack->num_complete_paths = 0;
      return 1;
    }
    append_arc_arriving(stack->root_path, parp);

    if (parp && whether_complete)
    {
      /* here .. check for dups ?? */
      stack->complete_paths[ stack->num_complete_paths++] = parp;
      if (stack->num_complete_paths == request_nbest_len)
        return 0;
    }
    else if (parp)
    {
      stack->active_paths[ stack->num_active_paths++] = parp;
    }
  }

  list_free_parps(stack, "astar_stack_prepare ");

  return 0;
}

/* cleans up astar after an utterance */

void astar_stack_clear(AstarStack* stack)
{
  int i;

  /* free the partial_path's that were allocated */
  for (i = 0; i < stack->num_active_paths; i++)
    free_partial_path(stack, stack->active_paths[i]);
  for (i = 0; i < stack->num_complete_paths; i++)
    free_partial_path(stack, stack->complete_paths[i]);
  if (stack->root_path)
    free_partial_path(stack, stack->root_path);

  /* this shouldn't be necessary, but there are a couple of bugs
     in parp management, so let's leave it for now */
  stack->free_parp_list = &stack->partial_path_array[0];
  for (i = 1; i < MAX_NUM_PARPS; i++)
    stack->partial_path_array[i-1].next = &stack->partial_path_array[i];
  stack->partial_path_array[i-1].next = 0;
  stack->num_active_paths = 0;
  stack->num_complete_paths = 0;
  stack->root_path = 0;

  list_free_parps(stack, "astar_stack_clear ");

}

/* do the astar search */

int astar_stack_do_backwards_search(srec* rec, int request_nbest_len)
{
  int i;
  AstarStack *stack = rec->astar_stack;
  word_token *wtoken, *btoken;
  partial_path *parp, *extended_parp, *tparp;
  wtokenID token_index, btoken_index;
  int whether_complete = 0;
  bigcostdata max_cost = 0;
  arc_token* arc_for_token_index = NULL;

  arc_token* arc_token_list;   /* to skip graph constraints, just set this to NULL */
  arcID arc_token_list_len;
  srec_word_lattice* lattice;

  int max_complete_paths;

  if (!rec || !rec->context)
  {
    log_report("Error: bad arguments in astar_stack_do_backwards_search()\n");
    return 1;
  }
  max_complete_paths = request_nbest_len < stack->max_complete_paths ?
                       request_nbest_len : stack->max_complete_paths;

  arc_token_list = rec->context->arc_token_list;
  arc_token_list_len = rec->context->arc_token_list_len;
  lattice = rec->word_lattice;

  /* initialization, now from calling function */
  /* astar_stack_prepare(stack, request_nbest_len, rec); */
  hash_init((FixedSizeHash*)stack->pphash, rec);

  /* search */
  while (stack->num_active_paths > 0)
  {

    list_free_parps(stack, "do_astar_back BEG");

    /* extend top path */
    parp = stack->active_paths[0];
    wtoken = &rec->word_token_array[parp->token_index];
    token_index = wtoken->backtrace;
    wtoken = &rec->word_token_array[token_index];
    ASSERT(token_index != MAXwtokenID); /* should have been "complete" */


#if PRINT_ASTAR_DETAILS
    print_partial_paths(stack->complete_paths, stack->num_complete_paths,
                        rec, "=== Complete Paths ===\n");
    print_partial_paths(stack->active_paths, stack->num_active_paths,
                        rec, "=== Active Paths ===\n");
#endif

    /* pop this one */
    for (i = 0; i < stack->num_active_paths - 1; i++)
      stack->active_paths[i] = stack->active_paths[i+1];
    stack->num_active_paths--;

    if (wtoken->end_time != MAXframeID)
    {
      /* sort the word token array by score, so that we pick the best
      scoring paths first */
      /* later add a 'whether_sorted' flag to the lattice_at_frame information */
      sort_word_lattice_at_frame(rec, (frameID)(wtoken->end_time + 1));

      /* extend this path, with every word ending where this word began */
      /* #warning there appear to be duplicates */

      btoken_index = lattice->words_for_frame[ wtoken->end_time+1];
    }
    else
    {
      btoken_index = MAXwtokenID;
    }

#if PRINT_ASTAR_DETAILS
    print_path(parp, rec, "Now Processing Top of Stack(2): ");
    printf("Frame %d\n", wtoken->end_time + 1);
    print_word_token_list(rec, btoken_index, "List of Word at Frame\n");
#endif

    for (; btoken_index != MAXwtokenID; btoken_index = btoken->next_token_index)
    {
      btoken = &rec->word_token_array[btoken_index];

      /* alternate choice must end at same frame */
      //      ASSERT(btoken->end_time == wtoken->end_time);

#if PRINT_ASTAR_DETAILS
      print_path(parp, rec, "Now Processing Top of Stack(3): ");
      print_word_token(rec, btoken_index, "Extending word ");
#endif

      /* check if this potential extension is allowed by the
      word graph, if not just drop it! */

      if (arc_token_list)
      {
        arc_for_token_index = get_arc_for_word(parp->arc_for_wtoken,
                                               btoken->word,
                                               rec->context,
                                               rec->context->beg_silence_word);
        if (arc_for_token_index == NULL)
        {
#if PRINT_ASTAR_DETAILS
          printf("Not allowed by graph!\n");
#endif
          continue;
        }
      }

      /* figure out the cost to beat ! */
      if (stack->num_complete_paths)
      {
        max_cost = stack->complete_paths[0]->costsofar + stack->prune_delta;
      }
      else if (stack->num_active_paths == stack->max_active_paths)
      {
        max_cost = stack->active_paths[ stack->num_active_paths-1]->costsofar;
      }
      else if (stack->num_active_paths > 0)
      {
        max_cost = stack->active_paths[0]->costsofar + stack->prune_delta;
      }
      else
      {
        max_cost = MAXbcostdata;
      }

      extended_parp = extend_path(stack, parp, btoken_index, arc_for_token_index, max_cost, rec->word_token_array, &whether_complete);

      if (extended_parp)
      {
        int fsh_rc = hash_set((FixedSizeHash*)stack->pphash, extended_parp);
        if (fsh_rc == FSH_KEY_OCCUPIED)
        {
          /* seen this path before, let's not bother with it */
#if PRINT_ASTAR_DETAILS
          print_path(extended_parp, rec, "dup!! ");
#endif
          free_partial_path(stack, extended_parp);
          extended_parp = 0;
        }
      }

      if (extended_parp && whether_complete)
      {
        ASSERT(stack->num_complete_paths < stack->max_complete_paths);
        stack->complete_paths[ stack->num_complete_paths++] = extended_parp;
        /*if(stack->num_complete_paths >= request_nbest_len)
          return 0;*/


#if PRINT_ASTAR_DETAILS
        print_path(extended_parp, rec, "&&Extended, complete : ");
#endif
      }
      else if (extended_parp)
      {
        /* todo: check if this extended_parp is already completed on the
           stack->complete_paths, if so just rejoin with that guy somehow */

#if PRINT_ASTAR_DETAILS
        print_path(extended_parp, rec, "&&Extended, incomplete : ");
#endif
        if (stack->num_active_paths == stack->max_active_paths)
        {
          /* kill the last one */
          stack->num_active_paths--;
          tparp = stack->active_paths[stack->num_active_paths];
          hash_del((FixedSizeHash*)stack->pphash, tparp);
          free_partial_path(stack, tparp);
        }
        insert_partial_path(stack->active_paths, &stack->num_active_paths,
                            extended_parp);
      }
#if PRINT_ASTAR_DETAILS
      else
      {
        printf("&&Extended, cost too high (>%d):\n", max_cost);
      }
#endif
      if (stack->num_complete_paths == max_complete_paths)
      {
#if PRINT_ASTAR_DETAILS
        printf("Complete paths are full %d, stopping\n", stack->num_complete_paths);
#endif
        break;
      }
    }
#if PRINT_ASTAR_DETAILS
    if (do_draw_as_dotty > 0)
    {
      char tmp[32];
      sprintf(tmp, "astar.%.3d.dot", do_draw_file_idx++);
      astar_draw_tree_as_dotty(tmp, rec, stack);
      if (do_draw_as_dotty > 1)
        system("C:/tools/graphviz/bin/dotty.exe astar.dot");
    }
#endif

    SREC_STATS_UPDATE_ASTAR(stack);
    hash_del((FixedSizeHash*)stack->pphash, parp);
    free_partial_path(stack, parp); /* done all extensions, now free */
    if (stack->num_complete_paths == max_complete_paths)
    {
#if PRINT_ASTAR_DETAILS
      printf("Complete paths are full %d, stopping\n", stack->num_complete_paths);
#endif
      break;
    }

    list_free_parps(stack, "do_astar_back END");
  }
  sort_partial_paths(stack->complete_paths, stack->num_complete_paths);
  /* if we're doing a search within a grammar, then print the complete choices
     else we're likely just doing reprune_word_tokens() */
#if PRINT_ASTAR_SOMEWHAT
  if (rec->context->arc_token_list)
    print_partial_paths(stack->complete_paths, stack->num_complete_paths,
                        rec, "=== Complete paths ===\n");
#endif
  /* now the caller must call clear */
  /* astar_stack_clear(stack); */

  return 0;
}

void sort_partial_paths(partial_path** parps, int num_parps)
{
  int i, j;
  for (i = 0; i < num_parps; i++)
  {
    for (j = 0; j < num_parps - 1; j++)
    {
      if (parps[j]->costsofar > parps[j+1]->costsofar)
      {
        partial_path* parp = parps[j];
        parps[j] = parps[j+1];
        parps[j+1] = parp;
      }
    }
  }
}

void insert_partial_path(partial_path** parps, int *pnum_parps, partial_path* insert_parp)
{
  int i, j, insert_index;
  int num_parps = *pnum_parps;

  /* maintain the list sorted, search the list linearly for now,
     do priority_q type heap later */
  insert_index = num_parps;
  for (i = 0; i < num_parps; i++)
  {
    if (insert_parp->costsofar < parps[i]->costsofar)
    {
      insert_index = i;
      break;
    }
  }
  for (j = num_parps; j > insert_index; --j)
    parps[j] = parps[j-1];
  parps[j] = insert_parp;
  num_parps++;
  *pnum_parps = num_parps;
}

void print_path(partial_path* ipath, srec* rec, char* msg)
{
  partial_path* path;
  word_token* wtoken;
  word_token* last_wtoken;
  char* p;
  char trans[256];
  int max_trans_len = 255;
  int rc;
#ifndef NDEBUG
  int sanity_count = 0;
#endif
  frameID end_time;

  PLogMessage("%spath score=%d ", msg, ipath->costsofar);

  rc = sprint_word_token_backtrace(trans, max_trans_len, rec, ipath->token_index);
  ASSERT(rc == 0);

  last_wtoken = 0;
  end_time = (ipath && ipath->token_index != MAXwtokenID) ? rec->word_token_array[ipath->token_index].end_time : MAXframeID;
#if SHOW_END_TIMES
  printf("%s@%d || ", trans, end_time);
#else
  printf("%s || ", trans);
#endif

  path = ipath->next;  /* we've already printed this thing */
  for (; path; path = path->next)
  {
    ASSERT(sanity_count++ < 256);
    if (path->token_index == MAXwtokenID) break;
    wtoken = &rec->word_token_array[ path->token_index];
    p = "NULL";
    if (rec->context->olabels->words[wtoken->word])
      p = rec->context->olabels->words[wtoken->word];
#if SHOW_END_TIMES
    printf("%s@%d ", p, wtoken->end_time);
#else
    printf("%s ", p);
#endif
    if (last_wtoken != NULL)
    {
      if (wtoken->end_time < last_wtoken->end_time)
      {
        printf(" Error: wt%d < lwt%d\n", wtoken->end_time, last_wtoken->end_time);
        pfflush(PSTDOUT);
        ASSERT(0);
      }
    }
    last_wtoken = wtoken;
  }
  printf("\n");
}

void print_partial_paths(partial_path** parps, int num_parps,
                         srec* rec, const char* msg)
{
  int i;
  char buf[32];
  printf("%s", msg);
  for (i = 0; i < num_parps; i++)
  {
    sprintf(buf, "%.3d ", i);
    print_path(parps[i], rec, buf);
  }
}


/*--------------------------------------------------------------------------*
 *                                                                          *
 * visualization .. sometimes helps debugging                               *
 *                                                                          *
 *--------------------------------------------------------------------------*/

#if PRINT_ASTAR_DETAILS


int astar_draw_arc_as_dotty(FILE* fp, partial_path* parp, int src_node, int *nodes_used, srec* rec)
{
  word_token* word_token_array = rec->word_token_array;
  partial_path* parp1;
  int sanity_count = 0;
  int to_nodes[32], *pto_nodes, inode;
  pto_nodes = to_nodes;

  fprintf(fp, "%d [label = \"%d\", shape = circle, style = solid]\n",
          src_node, src_node);
  for (parp1 = parp->first_prev_arc; parp1; parp1 = parp1->linkl_prev_arc)
  {
    arc_token* arc = parp1->arc_for_wtoken;
    for (inode = 0; nodes_used[inode]; inode++) ;
    nodes_used[inode] = 1;
    *pto_nodes++ = inode;
    fprintf(fp, "  %d -> %d [label = \"(%d).%d.%s@%d/%d\"];\n",
            src_node, inode, parp1->refcount,
            parp1->token_index,
            (arc && arc != (arc_token*)1) ? rec->context->olabels->words[arc->ilabel] : "NULL",
            word_token_array[ parp1->token_index].end_time,
            parp1->costsofar);
    if (sanity_count++  > 30) break;
  }

  pto_nodes = to_nodes;
  sanity_count = 0;
  for (parp1 = parp->first_prev_arc; parp1; parp1 = parp1->linkl_prev_arc)
  {
    astar_draw_arc_as_dotty(fp, parp1, *pto_nodes, nodes_used, rec);
    pto_nodes++;
    if (sanity_count++  > 30) break;
  }
  return 0;
}

int astar_draw_tree_as_dotty(const char* file, srec* rec, AstarStack* stack)
{
  word_token* word_token_array = rec->word_token_array;
  FILE* fp = fopen(file, "w");
  partial_path* parp;
  int nodes_used[1024];
  memset(nodes_used, 0, 1024*sizeof(int));

  fprintf(fp,
          "digraph FSM {\n"
          "rankdir = LR;\n"
          "size = \"8.5,11\";\n"
          "fontsize = 14;\n"
          "label = \"\\n\\naaron.PCLG\"\n"
          "center = 1;\n"
          "orientation = Landscape\n"
         );
  nodes_used[0] = 1;
  for (parp = stack->root_path; parp; parp = parp->linkl_prev_arc)
    astar_draw_arc_as_dotty(fp, parp, 0, nodes_used, rec);

  fprintf(fp, "}\n");
  fclose(fp);
  printf("....... dotty %s ......\n", file);
  return 0;
}

#endif

/*--------------------------------------------------------------------------*
 *                                                                          *
 * functions relating to in-recognition backtrace                           *
 *                                                                          *
 *--------------------------------------------------------------------------*/

int maybe_add_to_active_paths(AstarStack* stack, word_token* word_token_array, bigcostdata cost, wtokenID wtoken_index);
int astar_stack_prepare_from_active_search(AstarStack* stack, int nbestlen, srec* rec)
{
  wtokenID wtoken_index;
  ftokenID ftoken_index;
  fsmnode_token* ftoken;
  stokenID stoken_index;
  fsmarc_token* stoken;
  /* word_token* wtoken; */
  frameID prune_frame = rec->current_search_frame;
  int i, rc = 0, rc1 = 0;
  bigcostdata parp_costsofar;

  stack->num_active_paths = 0;
  stack->num_complete_paths = 0;
  stack->root_path = 0;

  /* put it on the stack */
  stack->root_path = make_new_partial_path(stack);
  ASSERT(stack->root_path);
  stack->root_path->refcount = 9999;
  stack->root_path->token_index = MAXwtokenID;
  stack->root_path->word = MAXwordID;

  ftoken_index = rec->active_fsmnode_tokens;
  for (; ftoken_index != MAXftokenID; ftoken_index = ftoken->next_token_index)
  {
    ftoken = &rec->fsmnode_token_array[ ftoken_index];
    wtoken_index = ftoken->word_backtrace;
    if (wtoken_index == MAXwtokenID)
      continue;

    /* fix the score */
    parp_costsofar = ftoken->cost;
    parp_costsofar += rec->accumulated_cost_offset[ prune_frame];

    rc += (rc1 = maybe_add_to_active_paths(stack, rec->word_token_array, parp_costsofar, wtoken_index));
    /* we can handle that a path was not added for this ftoken because
       we made sure to flag the wtokens along it's top backtrace */
  }

  stoken_index = rec->active_fsmarc_tokens;
  for (; stoken_index != MAXstokenID; stoken_index = stoken->next_token_index)
  {
    stoken = &rec->fsmarc_token_array[ stoken_index];
    for (i = 0; i < stoken->num_hmm_states; i++)
    {
      wtoken_index = stoken->word_backtrace[i];
      if (wtoken_index == MAXwtokenID)
        continue;
      parp_costsofar = stoken->cost[i];
      parp_costsofar += rec->accumulated_cost_offset[ prune_frame];

      rc += (rc1 = maybe_add_to_active_paths(stack, rec->word_token_array, parp_costsofar, wtoken_index));
      /* we can handle that a path was not added for this stoken because
      we made sure to flag the wtokens along it's top backtrace */
    }
  }

#if PRINT_ASTAR_DETAILS
  print_partial_paths(stack->active_paths, stack->num_active_paths,
                      rec, "== active paths before sorting ==\n");
  sort_partial_paths(stack->active_paths, stack->num_active_paths);
  print_partial_paths(stack->active_paths, stack->num_active_paths,
                      rec, "== active paths after sorting ==\n");
#endif
  list_free_parps(stack, "astar_prepare_from_active_search");
  return 0;
}

int maybe_add_to_active_paths(AstarStack* stack, word_token* word_token_array, bigcostdata parp_costsofar, wtokenID wtoken_index)
{
  int i;
  int replace_index;
  int inserts_index;
  partial_path* parp;
  word_token* wtoken;
  wtoken = &word_token_array[ wtoken_index];

  if (wtoken->backtrace == MAXwtokenID)
  {
    return 0;
  }

  /* see if we already have this word token backtrace */
  replace_index = -1;
  inserts_index = -1;
  for (i = 0; i < stack->num_active_paths; i++)
  {
    if (stack->active_paths[i]->token_index == wtoken_index)
    {
      if (parp_costsofar < stack->active_paths[i]->costsofar)
      {
        /* this one is better than another we already have! */
        replace_index = i;
        if (inserts_index < 0)
          inserts_index = i;
      }
      break;
    }
    else if (parp_costsofar < stack->active_paths[i]->costsofar)
    {
      if (inserts_index < 0)
        inserts_index = i;
    }
  }
#if PRINT_ASTAR_QBT_DETAILS
  printf("maybe_add replace %d insert %d\n", replace_index, inserts_index);
#endif

  if (replace_index >= 0)
  {
    free_partial_path(stack, stack->active_paths[replace_index]);
    /* stack->active_paths[replace_index] = 0; */
    for (i = replace_index; i > inserts_index; --i)
      stack->active_paths[i] = stack->active_paths[i-1];
    stack->active_paths[inserts_index] = 0;
  }
  else if (inserts_index >= 0)
  {
    if (stack->num_active_paths == stack->max_active_paths)
    {
      free_partial_path(stack, stack->active_paths[ stack->num_active_paths-1]);
      stack->num_active_paths--;
    }
    for (i = stack->num_active_paths; i > inserts_index; --i)
      stack->active_paths[i] = stack->active_paths[i-1];
    stack->active_paths[inserts_index] = 0;
    stack->num_active_paths++;
  }
  else if (stack->num_active_paths < stack->max_active_paths)
  {
    /* append if there's space */
    inserts_index = stack->num_active_paths;
    stack->num_active_paths++;
    stack->active_paths[inserts_index] = 0;
  }
  else
  {
    /* no space */
    return 1;
  }

  /* create a parp */
#if PRINT_ASTAR_QBT_DETAILS
  printf("maybe_add .. creating new parp %d\n", parp_costsofar);
#endif
  /* this should always succeed because of above frees */
  ASSERT(stack->free_parp_list);
  parp = make_new_partial_path(stack);
  parp->token_index = wtoken_index;
  if (wtoken_index != MAXwtokenID)
    parp->word = word_token_array[ wtoken_index].word;
  else
    parp->word = MAXwordID;
  parp->next = stack->root_path;
  parp->first_prev_arc = parp->linkl_prev_arc = 0;
  parp->arc_for_wtoken = 0;
  parp->refcount = 1;
  parp->costsofar = parp_costsofar;

  stack->active_paths[ inserts_index] = parp;

#if PRINT_ASTAR_QBT_DETAILS
  printf("maybe_add .. appending to root\n");
#endif
  append_arc_arriving(stack->root_path, parp);
  return 0;
}


int astar_stack_flag_word_tokens_used(AstarStack* stack, srec* rec)
{
  int i;
  wtokenID wtoken_index;
  partial_path* parp;
  int num_flagged_by_path;

#if PRINT_ASTAR_QBT_DETAILS
  print_partial_paths(stack->complete_paths, stack->num_complete_paths,
                      rec, "=== Complete QBT paths ===\n");
#endif

  for (i = 0; i < stack->num_complete_paths; i++)
  {
    num_flagged_by_path = 0;
    for (parp = stack->complete_paths[i]; parp; parp = parp->next)
    {
      wtoken_index = parp->token_index;
      if (wtoken_index == MAXwtokenID) break;
      rec->word_token_array_flags[ wtoken_index]++;
      if (rec->word_token_array_flags[wtoken_index] > 0)
      {
        num_flagged_by_path++;
#if PRINT_ASTAR_QBT_DETAILS
        printf("%d ", wtoken_index);
#endif
      }
    }

    /* also flag the main backtrace of every word token */
    /* we do we need this?  I'm not sure, but it appears
       that some backtrace tokens are not flagged for whatever
       reason.  It's worth revisiting this when other bugs are
       are resolved.  This is in a separate loop from the
       above because it allows us to detect that this is
       happening in the first place */
    for (parp = stack->complete_paths[i]; parp; parp = parp->next)
    {
      word_token *btoken, *last_btoken;
      wtokenID btoken_index;
      wtoken_index = parp->token_index;
      if (wtoken_index == MAXwtokenID) break;
      last_btoken = NULL;
      btoken = &rec->word_token_array[ wtoken_index];
      btoken_index = btoken->backtrace;
      for (; btoken_index != MAXwtokenID; btoken_index = btoken->backtrace)
      {
        btoken = &rec->word_token_array[ btoken_index];
        rec->word_token_array_flags[ btoken_index]++;
        if (rec->word_token_array_flags[ btoken_index] == 1)
        {
          num_flagged_by_path++;
#if PRINT_ASTAR_QBT_DETAILS
          printf("%db ", btoken_index);
#endif
        }
        if (last_btoken && last_btoken->end_time <= btoken->end_time)
        {
          PLogError("bad looping path encountered, breaking");
          break;
        }
        last_btoken = btoken;
      }
    }

#if PRINT_ASTAR_QBT_DETAILS
    printf("complete path %.3d flagged %d\n", i, num_flagged_by_path);
#endif
  }
  return 0;
}


#if DEBUG_PARP_MANAGEMENT
#define PARP_FREE 1
#define PARP_USED 2
void list_free_parps(AstarStack* stack, char* msg)
{
  partial_path* parp;
  int i, num = 0;
  char x[MAX_NUM_PARPS];
  for (i = 0; i < MAX_NUM_PARPS; i++) x[i] = 0;
  for (parp = stack->free_parp_list; parp; parp = parp->next)
  {
    num++;
    x[(parp-stack->partial_path_array)] = PARP_FREE;
  }
  PLogMessage("%sstack->free_parp_list size %d ", msg, num);
  PLogMessage("active %d complete %d\n", stack->num_active_paths, stack->num_complete_paths);

  for (i = 0; i < stack->num_active_paths; i++)
  {
    parp = stack->active_paths[i];
    for (; parp; parp = parp->next) x[(parp-stack->partial_path_array)] = PARP_USED;
  }
  for (i = 0; i < stack->num_complete_paths; i++)
  {
    parp = stack->complete_paths[i];
    for (; parp; parp = parp->next) x[(parp-stack->partial_path_array)] = PARP_USED;
  }
  if (stack->root_path)
    x[(stack->root_path-stack->partial_path_array)] = PARP_USED;
  printf("free: ");
  for (i = 0; i < MAX_NUM_PARPS; i++) if (x[i] == PARP_FREE) printf(" %d", i);
  printf("\n");
  printf("used: ");
  for (i = 0; i < MAX_NUM_PARPS; i++) if (x[i] == PARP_USED) printf(" %d", i);
  printf("\n");
  for (i = 0, num = 0; i < MAX_NUM_PARPS; i++) if (!x[i]) num++;
  printf("unaccounted for %d\n", num);
  ASSERT(num == 0);

}
#endif