/*

   +----------------------------------------------------------------------+

   | Zend Engine, Call Graph                                              |

   +----------------------------------------------------------------------+

   | Copyright © The PHP Group and Contributors.                          |

   +----------------------------------------------------------------------+

   | This source file is subject to the Modified BSD License that is      |

   | bundled with this package in the file LICENSE, and is available      |

   | through the World Wide Web at <https://www.php.net/license/>.        |

   |                                                                      |

   | SPDX-License-Identifier: BSD-3-Clause                                |

   +----------------------------------------------------------------------+

   | Authors: Dmitry Stogov <dmitry@php.net>                              |

   +----------------------------------------------------------------------+

*/

#include "zend_compile.h"

#include "zend_extensions.h"

#include "Optimizer/zend_optimizer.h"

#include "zend_optimizer_internal.h"

#include "zend_inference.h"

#include "zend_call_graph.h"

#include "zend_func_info.h"

static void zend_op_array_calc(zend_op_array *op_array, void *context)

{

  zend_call_graph *call_graph = context;

  call_graph->op_arrays_count++;

}

static void zend_op_array_collect(zend_op_array *op_array, void *context)

{

  zend_call_graph *call_graph = context;

  zend_func_info *func_info = call_graph->func_infos + call_graph->op_arrays_count;

  ZEND_SET_FUNC_INFO(op_array, func_info);

  call_graph->op_arrays[call_graph->op_arrays_count] = op_array;

  func_info->num = call_graph->op_arrays_count;

  call_graph->op_arrays_count++;

}

ZEND_API void zend_analyze_calls(zend_arena **arena, zend_script *script, uint32_t build_flags, zend_op_array *op_array, zend_func_info *func_info)

{

  zend_op *opline = op_array->opcodes;

  zend_op *end = opline + op_array->last;

  zend_function *func;

  zend_call_info *call_info;

  int call = 0;

  zend_call_info **call_stack;

  ALLOCA_FLAG(use_heap);

  bool is_prototype;

  call_stack = do_alloca((op_array->last / 2) * sizeof(zend_call_info*), use_heap);

  call_info = NULL;

  while (opline != end) {

    switch (opline->opcode) {

      case ZEND_INIT_FCALL:

      case ZEND_INIT_METHOD_CALL:

      case ZEND_INIT_STATIC_METHOD_CALL:

      case ZEND_INIT_PARENT_PROPERTY_HOOK_CALL:

        call_stack[call] = call_info;

        func = zend_optimizer_get_called_func(

          script, op_array, opline, &is_prototype);

        if (func) {

          call_info = zend_arena_calloc(arena, 1, sizeof(zend_call_info) + (sizeof(zend_send_arg_info) * ((int)opline->extended_value - 1)));

          call_info->caller_op_array = op_array;

          call_info->caller_init_opline = opline;

          call_info->caller_call_opline = NULL;

          call_info->callee_func = func;

          call_info->num_args = opline->extended_value;

          call_info->next_callee = func_info->callee_info;

          call_info->is_prototype = is_prototype;

          call_info->is_frameless = false;

          func_info->callee_info = call_info;

          if (build_flags & ZEND_CALL_TREE) {

            call_info->next_caller = NULL;

          } else if (func->type == ZEND_INTERNAL_FUNCTION

           || func->op_array.filename != script->filename) {

            call_info->next_caller = NULL;

          } else {

            zend_func_info *callee_func_info = ZEND_FUNC_INFO(&func->op_array);

            if (callee_func_info) {

              call_info->next_caller = callee_func_info->caller_info;

              callee_func_info->caller_info = call_info;

            } else {

              call_info->next_caller = NULL;

            }

          }

        } else {

          call_info = NULL;

        }

        call++;

        break;

      case ZEND_INIT_FCALL_BY_NAME:

      case ZEND_INIT_NS_FCALL_BY_NAME:

      case ZEND_INIT_DYNAMIC_CALL:

      case ZEND_NEW:

      case ZEND_INIT_USER_CALL:

        call_stack[call] = call_info;

        call_info = NULL;

        call++;

        break;

      case ZEND_FRAMELESS_ICALL_0:

      case ZEND_FRAMELESS_ICALL_1:

      case ZEND_FRAMELESS_ICALL_2:

      case ZEND_FRAMELESS_ICALL_3: {

        func = ZEND_FLF_FUNC(opline);

        zend_call_info *call_info = zend_arena_calloc(arena, 1, sizeof(zend_call_info));

        call_info->caller_op_array = op_array;

        call_info->caller_init_opline = opline;

        call_info->caller_call_opline = NULL;

        call_info->callee_func = func;

        call_info->num_args = ZEND_FLF_NUM_ARGS(opline->opcode);

        call_info->next_callee = func_info->callee_info;

        call_info->is_prototype = false;

        call_info->is_frameless = true;

        call_info->next_caller = NULL;

        func_info->callee_info = call_info;

        break;

      }

      case ZEND_DO_FCALL:

      case ZEND_DO_ICALL:

      case ZEND_DO_UCALL:

      case ZEND_DO_FCALL_BY_NAME:

      case ZEND_CALLABLE_CONVERT:

        func_info->flags |= ZEND_FUNC_HAS_CALLS;

        if (call_info) {

          call_info->caller_call_opline = opline;

        }

        call--;

        call_info = call_stack[call];

        break;

      case ZEND_SEND_VAL:

      case ZEND_SEND_VAR:

      case ZEND_SEND_VAL_EX:

      case ZEND_SEND_VAR_EX:

      case ZEND_SEND_FUNC_ARG:

      case ZEND_SEND_REF:

      case ZEND_SEND_VAR_NO_REF:

      case ZEND_SEND_VAR_NO_REF_EX:

      case ZEND_SEND_USER:

        if (call_info) {

          if (opline->op2_type == IS_CONST) {

            call_info->named_args = true;

            break;

          }

          uint32_t num = opline->op2.num;

          if (num > 0) {

            num--;

          }

          call_info->arg_info[num].opline = opline;

        }

        break;

      case ZEND_SEND_ARRAY:

      case ZEND_SEND_UNPACK:

        if (call_info) {

          call_info->send_unpack = true;

        }

        break;

    }

    opline++;

  }

  free_alloca(call_stack, use_heap);

}

static bool zend_is_indirectly_recursive(const zend_op_array *root, const zend_op_array *op_array, zend_bitset visited)

{

  const zend_func_info *func_info;

  zend_call_info *call_info;

  bool ret = false;

  if (op_array == root) {

    return true;

  }

  func_info = ZEND_FUNC_INFO(op_array);

  if (zend_bitset_in(visited, func_info->num)) {

    return false;

  }

  zend_bitset_incl(visited, func_info->num);

  call_info = func_info->caller_info;

  while (call_info) {

    if (zend_is_indirectly_recursive(root, call_info->caller_op_array, visited)) {

      call_info->recursive = true;

      ret = true;

    }

    call_info = call_info->next_caller;

  }

  return ret;

}

static void zend_analyze_recursion(zend_call_graph *call_graph)

{

  const zend_op_array *op_array;

  zend_func_info *func_info;

  zend_call_info *call_info;

  uint32_t set_len = zend_bitset_len(call_graph->op_arrays_count);

  zend_bitset visited;

  ALLOCA_FLAG(use_heap);

  visited = ZEND_BITSET_ALLOCA(set_len, use_heap);

  for (uint32_t i = 0; i < call_graph->op_arrays_count; i++) {

    op_array = call_graph->op_arrays[i];

    func_info = call_graph->func_infos + i;

    call_info = func_info->caller_info;

    for (; call_info; call_info = call_info->next_caller) {

      if (call_info->is_prototype) {

        /* Might be calling an overridden child method and not actually recursive. */

        continue;

      }

      if (call_info->caller_op_array == op_array) {

        call_info->recursive = true;

        func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_DIRECTLY;

      } else {

        memset(visited, 0, sizeof(zend_ulong) * set_len);

        if (zend_is_indirectly_recursive(op_array, call_info->caller_op_array, visited)) {

          call_info->recursive = true;

          func_info->flags |= ZEND_FUNC_RECURSIVE | ZEND_FUNC_RECURSIVE_INDIRECTLY;

        }

      }

    }

  }

  free_alloca(visited, use_heap);

}

static void zend_sort_op_arrays(zend_call_graph *call_graph)

{

  (void) call_graph;

  // TODO: perform topological sort of cyclic call graph

}

ZEND_API void zend_build_call_graph(zend_arena **arena, zend_script *script, zend_call_graph *call_graph) /* {{{ */

{

  call_graph->op_arrays_count = 0;

  zend_foreach_op_array(script, zend_op_array_calc, call_graph);

  call_graph->op_arrays = (zend_op_array**)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_op_array*));

  call_graph->func_infos = (zend_func_info*)zend_arena_calloc(arena, call_graph->op_arrays_count, sizeof(zend_func_info));

  call_graph->op_arrays_count = 0;

  zend_foreach_op_array(script, zend_op_array_collect, call_graph);

}

/* }}} */

ZEND_API void zend_analyze_call_graph(zend_arena **arena, zend_script *script, zend_call_graph *call_graph) /* {{{ */

{

  for (uint32_t i = 0; i < call_graph->op_arrays_count; i++) {

    zend_analyze_calls(arena, script, 0, call_graph->op_arrays[i], call_graph->func_infos + i);

  }

  zend_analyze_recursion(call_graph);

  zend_sort_op_arrays(call_graph);

}

/* }}} */

ZEND_API zend_call_info **zend_build_call_map(zend_arena **arena, const zend_func_info *info, const zend_op_array *op_array) /* {{{ */

{

  zend_call_info **map, *call;

  if (!info->callee_info) {

    /* Don't build call map if function contains no calls */

    return NULL;

  }

  map = zend_arena_calloc(arena, sizeof(zend_call_info *), op_array->last);

  for (call = info->callee_info; call; call = call->next_callee) {

    map[call->caller_init_opline - op_array->opcodes] = call;

    if (call->caller_call_opline) {

      map[call->caller_call_opline - op_array->opcodes] = call;

    }

    if (!call->is_frameless) {

      for (uint32_t i = 0; i < call->num_args; i++) {

        if (call->arg_info[i].opline) {

          map[call->arg_info[i].opline - op_array->opcodes] = call;

        }

      }

    }

  }

  return map;

}

/* }}} */