#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <errno.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <mcpu-elf.h>

#include "mcpu-dependency.h"
#include "mcpu-dyn.h"
#include "mcpu-exec.h"


typedef struct dependency_node dependency_node;
struct dependency_node
{
  char                    *path;
  cpu_dyn_dependency_info  info;
};


typedef struct dependency_graph dependency_graph;
struct dependency_graph
{
  const mcpu_tool_options *options;
  char                   **preload_path;
  cpu_dyn_dependency_info *preload_info;
  size_t                   preload_count;
  dependency_node         *node;
  size_t                   node_count;
  size_t                   node_capacity;
  char                    *err;
  size_t                   errsz;
};


static void
free_string_vector( char **v, size_t n )
{
  while( n != 0 )
    free( v[--n] );
  free( v );

} /* End of free_string_vector() */


static int
split_path_list( const char *list, char ***result, size_t *count,
                 char *err, size_t errsz )
{
  const char *begin;
  char      **v = NULL;
  size_t      n = 0, capacity = 0;

  if( result == NULL || count == NULL )
  {
    if( err != NULL && errsz != 0 )
      snprintf( err, errsz, "invalid module-list arguments" );
    return( -1 );
  }

  *result = NULL;
  *count = 0;
  if( list == NULL || *list == 0 )
    return( 0 );

  begin = list;
  for( ;; )
  {
    const char *colon = strchr( begin, ':' );
    size_t      length = colon ? (size_t)(colon - begin) : strlen(begin);
    char       *copy;

    if( length == 0 )
    {
      snprintf( err, errsz, "empty path in resolved module list" );
      goto bad;
    }

    if( n == capacity )
    {
      size_t  new_capacity = capacity ? capacity * 2U : 4U;
      char  **p;

      if( new_capacity < capacity ||
          new_capacity > SIZE_MAX / sizeof(*p) )
      {
        snprintf( err, errsz, "too many resolved modules" );
        goto bad;
      }
      p = (char **)realloc( v, new_capacity * sizeof(*p) );
      if( p == NULL )
      {
        snprintf( err, errsz, "out of memory" );
        goto bad;
      }
      v = p;
      capacity = new_capacity;
    }

    copy = (char *)malloc( length + 1U );
    if( copy == NULL )
    {
      snprintf( err, errsz, "out of memory" );
      goto bad;
    }
    memcpy( copy, begin, length );
    copy[length] = 0;
    v[n++] = copy;

    if( colon == NULL )
      break;
    begin = colon + 1;
  }

  *result = v;
  *count = n;
  return( 0 );

bad:
  free_string_vector( v, n );
  return( -1 );

} /* End of split_path_list() */


static void
dependency_graph_free( dependency_graph *graph )
{
  size_t i;

  if( graph == NULL )
    return;

  for( i = 0; i < graph->preload_count; ++i )
  {
    free( graph->preload_path[i] );
    cpu_dyn_dependency_free( &graph->preload_info[i] );
  }
  free( graph->preload_path );
  free( graph->preload_info );

  for( i = 0; i < graph->node_count; ++i )
  {
    free( graph->node[i].path );
    cpu_dyn_dependency_free( &graph->node[i].info );
  }
  free( graph->node );
  memset( graph, 0, sizeof(*graph) );

} /* End of dependency_graph_free() */


static int
preload_has_soname( const dependency_graph *graph, const char *soname )
{
  size_t i;

  for( i = graph->preload_count; i != 0; --i )
  {
    const cpu_dyn_dependency_info *info = &graph->preload_info[i - 1U];

    if( info->soname != NULL && strcmp(info->soname, soname) == 0 )
      return( 1 );
  }
  return( 0 );

} /* End of preload_has_soname() */


static dependency_node *
find_node( dependency_graph *graph, const char *soname )
{
  size_t i;

  for( i = 0; i < graph->node_count; ++i )
    if( graph->node[i].info.soname != NULL &&
        strcmp(graph->node[i].info.soname, soname) == 0 )
      return( &graph->node[i] );

  return( NULL );

} /* End of find_node() */


static dependency_node *
add_node( dependency_graph *graph, char *path,
          cpu_dyn_dependency_info *info )
{
  dependency_node *node;

  if( graph->node_count == graph->node_capacity )
  {
    size_t           capacity = graph->node_capacity ?
                        graph->node_capacity * 2U : 8U;
    dependency_node *p;

    if( capacity < graph->node_capacity ||
        capacity > SIZE_MAX / sizeof(*p) )
    {
      errno = EOVERFLOW;
      return( NULL );
    }
    p = (dependency_node *)realloc( graph->node,
                                    capacity * sizeof(*p) );
    if( p == NULL )
      return( NULL );
    graph->node = p;
    graph->node_capacity = capacity;
  }

  node = &graph->node[graph->node_count++];
  memset( node, 0, sizeof(*node) );
  node->path = path;
  node->info = *info;
  memset( info, 0, sizeof(*info) );
  return( node );

} /* End of add_node() */


static int
enqueue_needed( dependency_graph *graph, const char *soname )
{
  dependency_node         *node;
  cpu_dyn_dependency_info  info;
  char                    *path = NULL;

  if( preload_has_soname(graph, soname) )
    return( 0 );

  node = find_node( graph, soname );
  if( node != NULL )
    return( 0 );

  if( mcpu_tool_resolve_library(graph->options, soname, &path) != 0 )
  {
    snprintf( graph->err, graph->errsz,
              "cannot resolve DT_NEEDED '%s': %s", soname, strerror(errno) );
    return( -1 );
  }

  memset( &info, 0, sizeof(info) );
  if( cpu_dyn_dependency_read(path, 0, &info,
                              graph->err, graph->errsz) != 0 )
  {
    free( path );
    return( -1 );
  }

  if( info.abi != MELF_ABIVERSION_DYNAMIC_NEEDED || info.soname == NULL )
  {
    snprintf( graph->err, graph->errsz,
              "%s: DT_NEEDED '%s' did not resolve to an ABI-v3 library",
              path, soname );
    cpu_dyn_dependency_free( &info );
    free( path );
    return( -1 );
  }
  if( strcmp(info.soname, soname) != 0 )
  {
    snprintf( graph->err, graph->errsz,
              "%s: DT_NEEDED '%s' resolved to SONAME '%s'",
              path, soname, info.soname );
    cpu_dyn_dependency_free( &info );
    free( path );
    return( -1 );
  }

  node = add_node( graph, path, &info );
  if( node == NULL )
  {
    snprintf( graph->err, graph->errsz, "out of memory" );
    cpu_dyn_dependency_free( &info );
    free( path );
    return( -1 );
  }

  return( 0 );

} /* End of enqueue_needed() */


static int
inspect_preloads( dependency_graph *graph, const char *resolved_preload )
{
  size_t i;

  if( split_path_list(resolved_preload, &graph->preload_path,
                      &graph->preload_count, graph->err, graph->errsz) != 0 )
    return( -1 );

  if( graph->preload_count == 0 )
    return( 0 );

  graph->preload_info = (cpu_dyn_dependency_info *)calloc(
      graph->preload_count, sizeof(*graph->preload_info) );
  if( graph->preload_info == NULL )
  {
    snprintf( graph->err, graph->errsz, "out of memory" );
    return( -1 );
  }

  for( i = 0; i < graph->preload_count; ++i )
    if( cpu_dyn_dependency_read(graph->preload_path[i], 0,
                                &graph->preload_info[i],
                                graph->err, graph->errsz) != 0 )
      return( -1 );

  return( 0 );

} /* End of inspect_preloads() */


static int
append_load_path( char **buffer, size_t *length, size_t *capacity,
                  const char *path )
{
  size_t path_length = strlen( path );
  size_t add = path_length + (*length != 0 ? 1U : 0U);
  char  *p;

  if( strchr(path, ':') != NULL )
  {
    errno = EINVAL;
    return( -1 );
  }
  if( add > SIZE_MAX - *length - 1U )
  {
    errno = EOVERFLOW;
    return( -1 );
  }

  if( *length + add + 1U > *capacity )
  {
    size_t new_capacity = *capacity ? *capacity : 128U;

    while( new_capacity < *length + add + 1U )
    {
      if( new_capacity > SIZE_MAX / 2U )
      {
        errno = EOVERFLOW;
        return( -1 );
      }
      new_capacity *= 2U;
    }
    p = (char *)realloc( *buffer, new_capacity );
    if( p == NULL )
      return( -1 );
    *buffer = p;
    *capacity = new_capacity;
  }

  if( *length != 0 )
    (*buffer)[(*length)++] = ':';
  memcpy( *buffer + *length, path, path_length );
  *length += path_length;
  (*buffer)[*length] = 0;
  return( 0 );

} /* End of append_load_path() */


static int
build_load_list( dependency_graph *graph, char **load_list )
{
  char   *buffer = NULL;
  size_t  length = 0, capacity = 0, i;

  for( i = 0; i < graph->node_count; ++i )
    if( append_load_path(&buffer, &length, &capacity,
                         graph->node[i].path) != 0 )
      goto bad;

  /* Explicit preloads remain after normal dependencies in their original
     command-line order.  The loader receives preload_count separately and
     applies the ABI-v3 scope policy explicitly rather than inferring it from
     this flattened transport list. */
  for( i = 0; i < graph->preload_count; ++i )
    if( append_load_path(&buffer, &length, &capacity,
                         graph->preload_path[i]) != 0 )
      goto bad;

  *load_list = buffer;
  return( 0 );

bad:
  free( buffer );
  snprintf( graph->err, graph->errsz,
            "cannot build runtime module list: %s", strerror(errno) );
  return( -1 );

} /* End of build_load_list() */


int
mcpu_dependency_build_load_list( const mcpu_tool_options *options,
                                 const char *executable,
                                 const char *resolved_preload,
                                 char **load_list,
                                 size_t *preload_count,
                                 char *err, size_t errsz )
{
  dependency_graph         graph;
  cpu_dyn_dependency_info  main_info;
  unsigned                 abi;
  size_t                   i, j;
  int                      rc = -1;

  if( options == NULL || executable == NULL || load_list == NULL ||
      preload_count == NULL || err == NULL || errsz == 0 )
    return( -1 );

  *load_list = NULL;
  *preload_count = 0;
  memset( &graph, 0, sizeof(graph) );
  memset( &main_info, 0, sizeof(main_info) );
  graph.options = options;
  graph.err = err;
  graph.errsz = errsz;

  if( cpu_exec_abi_version(executable, &abi, err, errsz) != 0 )
    goto done;

  if( abi == MELF_ABIVERSION_MCPU_1 )
  {
    if( resolved_preload != NULL && *resolved_preload != 0 )
    {
      *load_list = strdup( resolved_preload );
      if( *load_list == NULL )
      {
        snprintf( err, errsz, "out of memory" );
        goto done;
      }
    }
    rc = 0;
    goto done;
  }

  if( inspect_preloads(&graph, resolved_preload) != 0 )
    goto done;

  if( cpu_dyn_dependency_read(executable, 1, &main_info,
                              err, errsz) != 0 )
    goto done;

  /* Seed the breadth-first scope with every direct dependency before
     descending into any transitive dependency.  Main DT_NEEDED entries come
     first in their recorded order; explicit-preload dependencies follow in
     command-line order. */
  for( i = 0; i < main_info.needed_count; ++i )
    if( enqueue_needed(&graph, main_info.needed[i]) != 0 )
      goto done;

  for( i = 0; i < graph.preload_count; ++i )
    for( j = 0; j < graph.preload_info[i].needed_count; ++j )
      if( enqueue_needed(&graph, graph.preload_info[i].needed[j]) != 0 )
        goto done;

  /* node[] is a queue.  Appending children while walking it yields a stable
     breadth-first dependency order, naturally deduplicating cycles by SONAME. */
  for( i = 0; i < graph.node_count; ++i )
    for( j = 0; j < graph.node[i].info.needed_count; ++j )
      if( enqueue_needed(&graph, graph.node[i].info.needed[j]) != 0 )
        goto done;

  if( build_load_list(&graph, load_list) != 0 )
    goto done;

  *preload_count = graph.preload_count;
  rc = 0;

done:
  cpu_dyn_dependency_free( &main_info );
  dependency_graph_free( &graph );
  if( rc != 0 )
  {
    free( *load_list );
    *load_list = NULL;
  }
  return( rc );

} /* End of mcpu_dependency_build_load_list() */