trie_tree* trie_tree_create_end()
{
  assert(be_creating);
  assert(!be_inserting);
  trie_tree* tree = (trie_tree*)malloc(sizeof(trie_tree));
  init_array(&tree->node_array, sizeof(trie_node));
  init_array(&successor_array, sizeof(trie_successor));
  append_array(&tree->node_array, 2);
  memset(get_array_elem(&tree->node_array, 0), 0, sizeof(trie_node)*2);
  trie_node* head_node = (trie_node*)get_array_elem(&tree->node_array, HEAD_INDEX);
  head_node->check = HEAD_CHECK;
  head_node->base = HEAD_INDEX;
  for(int input_index = 0; input_index<input_cache.len; input_index++)
  {
    int prefix_index, node_index, base_index;
    trie_input* input_node = (trie_input*)get_array_elem(&input_cache, input_index);
    while( find_prefix(tree, input_node->str, &prefix_index, &node_index) )
    {
      get_all_successors(input_node->str, prefix_index, input_index);
      base_index = find_base_index_by_successors(tree, node_index);
      insert_successors(tree, base_index, node_index);
    }
    mark_word_node(tree, node_index);
  }
  empty_array(&input_cache);
  empty_array(&successor_array);
  be_creating = false;
  return tree;
}

void trie_tree_insert_end(trie_tree* tree)
{
  assert(!be_creating);
  assert(be_inserting);
  init_array(&successor_array, sizeof(trie_successor));
  for(int input_index = 0; input_index<input_cache.len; input_index++)
  {
    int prefix_index, node_index;
    trie_input* input_node = (trie_input*)get_array_elem(&input_cache, input_index);
    while( find_prefix(tree, input_node->str, &prefix_index, &node_index) )
    {
      int base_index = abs(((trie_node*)get_array_elem(&tree->node_array, node_index))->base);
      get_all_successors(input_node->str, prefix_index, input_index);
      delete_existing_successors(tree, node_index);
      if(base_index == node_index || !check_insert_successors(tree, node_index) )
      {
        reset_successors(tree, node_index);
        base_index = find_base_index_by_successors(tree, node_index);
      }
      insert_successors(tree, base_index, node_index);
    }
    mark_word_node(tree, node_index);
  }
  print_node(tree, 1, 0);
  empty_array(&input_cache);
  empty_array(&successor_array);
  be_inserting = false;
}

Array HHVM_FUNCTION(heapgraph_node_in_edges,
  const Resource& resource,
  int64_t index
) {
  auto hgptr = get_valid_heapgraph_context_resource(resource, __FUNCTION__);
  if (!hgptr) return empty_array();
  if (index < 0 || index >= (hgptr->hg.nodes.size())) return empty_array();
  Array result;
  hgptr->hg.eachPredPtr(index, [&](int ptr) {
    result.append(createPhpEdge(hgptr, ptr));
  });
  return result;
}

void AsioSession::onIOWaitExit() {
  runCallback(
    m_onIOWaitExitCallback,
    empty_array(),
    "WaitHandle::onIOWaitExit"
  );
}

Array Variant::toArrayHelper() const {
    switch (m_type) {
    case KindOfUninit:
    case KindOfNull:
        return empty_array();
    case KindOfBoolean:
        return Array::Create(*this);
    case KindOfInt64:
        return Array::Create(m_data.num);
    case KindOfDouble:
        return Array::Create(*this);
    case KindOfStaticString:
    case KindOfString:
        return Array::Create(Variant{m_data.pstr});
    case KindOfPersistentArray:
    case KindOfArray:
        return Array(m_data.parr);
    case KindOfObject:
        return m_data.pobj->toArray();
    case KindOfResource:
        return m_data.pres->data()->o_toArray();
    case KindOfRef:
        return m_data.pref->var()->toArray();
    case KindOfClass:
        break;
    }
    not_reached();
}

Array c_WaitableWaitHandle::getDependencyStack() {
  if (isFinished()) return empty_array();
  Array result = Array::Create();
  hphp_hash_set<c_WaitableWaitHandle*> visited;
  auto current_handle = this;
  auto session = AsioSession::Get();
  while (current_handle != nullptr) {
    result.append(Variant{current_handle});
    visited.insert(current_handle);
    auto context_idx = current_handle->getContextIdx();

    // 1. find parent in the same context
    auto p = current_handle->getParentChain().firstInContext(context_idx);
    if (p && visited.find(p) == visited.end()) {
      current_handle = p;
      continue;
    }

    // 2. cross the context boundary
    auto context = session->getContext(context_idx);
    if (!context) {
      break;
    }
    current_handle = c_ResumableWaitHandle::getRunning(context->getSavedFP());
    auto target_context_idx =
      current_handle ? current_handle->getContextIdx() : 0;
    while (context_idx > target_context_idx) {
      --context_idx;
      result.append(null_object);
    }
  }
  return result;
}

Array HHVM_FUNCTION(stream_get_filters) {
  auto filters = s_stream_user_filters.get()->m_registeredFilters;
  if (UNLIKELY(filters.isNull())) {
    return empty_array();
  }
  return array_keys_helper(filters.filtersAsArray()).toArray();
}

static Array HHVM_FUNCTION(xenon_get_data, void) {
  if (RuntimeOption::XenonForceAlwaysOn ||
      RuntimeOption::XenonPeriodSeconds > 0) {
    TRACE(1, "xenon_get_data\n");
    return s_xenonData->createResponse();
  }
  return empty_array();
}

Array c_WaitableWaitHandle::t_getparents() {
  // no parent data available if finished
  if (isFinished()) {
    return empty_array();
  }

  return getParentChain().toArray();
}

Array HHVM_FUNCTION(apache_response_headers) {
  Transport *transport = g_context->getTransport();
  if (transport) {
    HeaderMap headers;
    transport->getResponseHeaders(headers);
    return get_headers(headers);
  }
  return empty_array();
}

 Array getVar(int64_t type) {
   switch (type) {
     case k_INPUT_GET: return m_GET;
     case k_INPUT_POST: return m_POST;
     case k_INPUT_COOKIE: return m_COOKIE;
     case k_INPUT_SERVER: return m_SERVER;
     case k_INPUT_ENV: return m_ENV;
   }
   return empty_array();
 }

Array HashCollection::toArray() {
  if (!m_size) {
    return empty_array();
  }
  auto ad = arrayData()->toPHPArray(true);
  if (UNLIKELY(ad->size() < m_size)) warnOnStrIntDup();
  assert(m_size);
  assert(ad->m_pos == 0);
  return Array::attach(ad);
}

void EventHook::DoMemoryThresholdCallback() {
  clearSurpriseFlag(MemThresholdFlag);
  if (!g_context->m_memThresholdCallback.isNull()) {
    VMRegAnchor _;
    try {
      vm_call_user_func(g_context->m_memThresholdCallback, empty_array());
    } catch (Object& ex) {
      raise_error("Uncaught exception escaping mem Threshold callback: %s",
                  ex.toString().data());
    }
  }
}

Array HHVM_FUNCTION(libxml_get_errors) {
  xmlErrorVec* error_list = &tl_libxml_request_data->m_errors;
  const auto length = error_list->size();
  if (!length) {
    return empty_array();
  }
  PackedArrayInit ret(length);
  for (int64_t i = 0; i < length; i++) {
    ret.append(create_libxmlerror(error_list->at(i)));
  }
  return ret.toArray();
}

Array c_WaitableWaitHandle::t_getparents() {
  // no parent data available if finished
  if (isFinished()) {
    return empty_array();
  }

  Array result = Array::Create();
  c_BlockableWaitHandle* curr = m_firstParent;

  while (curr) {
    result.append(curr);
    curr = curr->getNextParent();
  }

  return result;
}

Array Variant::toArrayHelper() const {
  switch (m_type) {
  case KindOfUninit:
  case KindOfNull:    return empty_array();
  case KindOfInt64:   return Array::Create(m_data.num);
  case KindOfStaticString:
  case KindOfString:  return Array::Create(m_data.pstr);
  case KindOfArray:   return Array(m_data.parr);
  case KindOfObject:  return m_data.pobj->o_toArray();
  case KindOfResource: return m_data.pres->o_toArray();
  case KindOfRef: return m_data.pref->var()->toArray();
  default:
    break;
  }
  return Array::Create(*this);
}

Variant ArrayUtil::Reverse(const Array& input, bool preserve_keys /* = false */) {
  if (input.empty()) {
    return empty_array();
  }

  auto ret = Array::Create();
  auto pos_limit = input->iter_end();
  for (ssize_t pos = input->iter_last(); pos != pos_limit;
       pos = input->iter_rewind(pos)) {
    auto const key = input->nvGetKey(pos);
    if (preserve_keys || isStringType(key.m_type)) {
      ret.setWithRef(key, input->atPos(pos), true);
    } else {
      ret.appendWithRef(input->atPos(pos));
    }
  }
  return ret;
}

Variant HHVM_FUNCTION(preg_replace_callback_array,
                      const Variant& patterns_and_callbacks,
                      const Variant& subject,
                      int limit /* = -1 */,
                      VRefParam count /* = uninit_null() */) {
  if (!patterns_and_callbacks.isArray()) {
    raise_warning(
      "%s() expects parameter 1 to be an array, %s given",
      __FUNCTION__+2 /* +2 removes the "f_" prefix */,
      getDataTypeString(patterns_and_callbacks.getType()).c_str()
    );
    return init_null();
  }

  // Now see if we need to raise any warnings because of not having a
  // valid callback function
  for (ArrayIter iter(patterns_and_callbacks.toArray()); iter; ++iter) {
    if (!is_callable(iter.second())) {
      raise_warning("Not a valid callback function %s",
                    iter.second().toString().data());
      return subject.isString() ? empty_string_variant()
                                : Variant(empty_array());
    }
  }

  if (subject.isString()) {
    Array subject_arr = Array::Create();
    subject_arr.add(0, subject.toString());
    Variant ret = preg_replace_callback_array_impl(
      patterns_and_callbacks, subject_arr, limit, count
    );
    // ret[0] could be an empty string
    return ret.isArray() ? ret.toArray()[0] : init_null();
  } else if (subject.isArray()) {
    return preg_replace_callback_array_impl(
      patterns_and_callbacks, subject.toArray(), limit, count
    );
  } else {
    // No warning is given here, just return null
    return init_null();
  }
}

Variant HHVM_METHOD(SQLite3, querysingle,
                    const String& sql,
                    bool entire_row /* = false */) {
  auto *data = Native::data<SQLite3>(this_);
  SYNC_VM_REGS_SCOPED();
  data->validate();
  if (!sql.empty()) {
    Variant stmt = HHVM_MN(SQLite3, prepare)(this_, sql);
    if (!same(stmt, false)) {
      Object obj_stmt = stmt.toObject();
      assert(obj_stmt.instanceof(SQLite3Stmt::getClass()));
      sqlite3_stmt *pstmt =
        Native::data<SQLite3Stmt>(obj_stmt)->m_raw_stmt;
      switch (sqlite3_step(pstmt)) {
      case SQLITE_ROW: /* Valid Row */
        if (entire_row) {
          Array ret = Array::Create();
          for (int i = 0; i < sqlite3_data_count(pstmt); i++) {
            ret.set(String((char*)sqlite3_column_name(pstmt, i), CopyString),
                    get_column_value(pstmt, i));
          }
          return ret;
        }
        return get_column_value(pstmt, 0);
      case SQLITE_DONE: /* Valid but no results */
        if (entire_row) {
          return empty_array();
        } else {
          return init_null();
        }
      default:
        raise_warning("Unable to execute statement: %s",
                      sqlite3_errmsg(data->m_raw_db));
      }
    }
  }
  return false;
}

Variant HHVM_FUNCTION(getaddrinfo,
                      const String& host,
                      const String& port,
                      int family /* = 0 */,
                      int socktype /* = 0 */,
                      int protocol /* = 0 */,
                      int flags /* = 0 */) {
  const char *hptr = NULL, *pptr = NULL;
  if (!host.empty()) {
    hptr = host.c_str();
  }
  if (!port.empty()) {
    pptr = port.c_str();
  }

  struct addrinfo hints, *res;
  struct addrinfo *res0 = NULL;
  int error;

  memset(&hints, 0, sizeof(hints));
  hints.ai_family = family;
  hints.ai_socktype = socktype;
  hints.ai_protocol = protocol;
  hints.ai_flags = flags;
  error = getaddrinfo(hptr, pptr, &hints, &res0);

  if (error) {
    raise_warning("%s", gai_strerror(error));

    if (res0) {
      freeaddrinfo(res0);
    }
    return false;
  }

  Array ret = Array::Create();

  for (res = res0; res; res = res->ai_next) {
    Array data = make_map_array(
      s_family, res->ai_family,
      s_socktype, res->ai_socktype,
      s_protocol, res->ai_protocol
    );

    switch (res->ai_addr->sa_family) {
      case AF_INET:
      {
        struct sockaddr_in *a;
        String buffer = ipaddr_convert(res->ai_addr, sizeof(*a));
        if (!buffer.empty()) {
          a = (struct sockaddr_in *)res->ai_addr;
          data.set(
            s_sockaddr,
            make_map_array(
              s_address, buffer,
              s_port, ntohs(a->sin_port)
            )
          );
        }
        break;
      }
      case AF_INET6:
      {
        struct sockaddr_in6 *a;
        String buffer = ipaddr_convert(res->ai_addr, sizeof(*a));
        if (!buffer.empty()) {
          a = (struct sockaddr_in6 *)res->ai_addr;
          data.set(
            s_sockaddr,
            make_map_array(
              s_address, buffer,
              s_port, ntohs(a->sin6_port),
              s_flow_info, (int32_t)a->sin6_flowinfo,
              s_scope_id, (int32_t)a->sin6_scope_id
            )
          );
        }
        break;
      }
      default:
        data.set(s_sockaddr, empty_array());
        break;
    }

    ret.append(data);
  }

  if (res0) {
    freeaddrinfo(res0);
  }

  return ret;
}