////////////////////////////////////////////////////////////////////////
//
// Copyright (C) 2006-2022 The Octave Project Developers
//
// See the file COPYRIGHT.md in the top-level directory of this
// distribution or <https://octave.org/copyright/>.
//
// This file is part of Octave.
//
// Octave is free software: you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Octave is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Octave; see the file COPYING.  If not, see
// <https://www.gnu.org/licenses/>.
//
////////////////////////////////////////////////////////////////////////

#if defined (HAVE_CONFIG_H)
#  include "config.h"
#endif

#include <algorithm>
#include <cctype>

#include "dir-ops.h"
#include "file-ops.h"
#include "file-stat.h"
#include "oct-env.h"
#include "pathsearch.h"

#include "defaults.h"
#include "defun.h"
#include "input.h"
#include "interpreter-private.h"
#include "interpreter.h"
#include "load-path.h"
#include "ov-usr-fcn.h"
#include "pager.h"
#include "parse.h"
#include "sysdep.h"
#include "unwind-prot.h"
#include "utils.h"

OCTAVE_BEGIN_NAMESPACE(octave)

  // Canonicalize file name (keeping the path relative) if it exists.
  // Return it unmodified otherwise.

  static std::string
  maybe_canonicalize (const std::string& dir_arg)
  {
    bool is_absolute_path = sys::env::absolute_pathname (dir_arg);

    std::string canonical_dir = sys::canonicalize_file_name (dir_arg);
    std::string dir;
    if (canonical_dir.empty ())
      dir = dir_arg;
    else
      {
        dir = canonical_dir;

        if (! is_absolute_path)
          {
            // Remove current path from absolute path generated by
            // canonicalize_file_name.
            std::string cwd = sys::canonicalize_file_name (".");
            if (dir.compare (0, cwd.length (), cwd) == 0)
              dir.erase (0, cwd.length ()+1);
            if (dir.empty ())
              dir = ".";
          }
      }

    return dir;
  }

  static void
  maybe_add_path_elts (std::string& path, const std::string& dir)
  {
    std::string tpath = genpath (maybe_canonicalize (dir));

    if (! tpath.empty ())
      {
        if (path.empty ())
          path = tpath;
        else
          path += directory_path::path_sep_str () + tpath;
      }
  }

  static std::list<std::string>
  split_path (const std::string& p)
  {
    std::list<std::string> retval;

    std::size_t beg = 0;
    std::size_t end = p.find (directory_path::path_sep_char ());

    std::size_t len = p.length ();

    while (end != std::string::npos)
      {
        std::string elt = p.substr (beg, end-beg);

        if (! elt.empty ())
          retval.push_back (elt);

        beg = end + 1;

        if (beg == len)
          break;

        end = p.find (directory_path::path_sep_char (), beg);
      }

    std::string elt = p.substr (beg);

    if (! elt.empty ())
      retval.push_back (elt);

    return retval;
  }

  // Strip trailing directory separators.

  static std::string
  strip_trailing_separators (const std::string& dir_arg)
  {
    std::string dir = dir_arg;

    std::size_t k = dir.length ();

    while (k > 1 && sys::file_ops::is_dir_sep (dir[k-1]))
      k--;

    if (k < dir.length ())
      dir.resize (k);

    return dir;
  }

  // Should we cache all files in private directories, or is it OK to just
  // look them up each time as needed?

  static std::string
  find_private_file (const std::string& fname)
  {
    std::string retval;

    // Look in private directory corresponding to current function (if
    // any).

    symbol_scope scope = __get_current_scope__ ();

    octave_user_code *curr_code = scope ? scope.user_code () : nullptr;

    if (curr_code)
      {
        // Even for private functions, dir_name doesn't contain the
        // "private" directory component so we append it here in all
        // cases.

        std::string dir_name = curr_code->dir_name ();

        if (! dir_name.empty ())
          {
            std::string pfname = dir_name + sys::file_ops::dir_sep_str ()
                                 + "private" + sys::file_ops::dir_sep_str ()
                                 + fname;

            sys::file_stat fs (pfname);

            if (fs.exists () && fs.is_reg ())
              retval = pfname;
          }
      }

    return retval;
  }

  // True if a path is contained in a path list separated by path_sep_char

  static bool
  in_path_list (const std::string& path_list, const std::string& path)
  {
    std::size_t ps = path.size ();
    std::size_t pls = path_list.size ();
    std::size_t pos = path_list.find (path);
    char psc = directory_path::path_sep_char ();
    while (pos != std::string::npos)
      {
        if ((pos == 0 || path_list[pos-1] == psc)
            && (pos + ps == pls || path_list[pos + ps] == psc))
          return true;
        else
          pos = path_list.find (path, pos + 1);
      }

    return false;
  }

  static void
  rehash_internal (void)
  {
    load_path& lp = __get_load_path__ ();

    lp.update ();

    // Signal the GUI allowing updating the load path dialog
    event_manager& evmgr = __get_event_manager__ ();
    evmgr.update_path_dialog ();

    // FIXME: maybe we should rename this variable since it is being
    // used for more than keeping track of the prompt time.

    // This will force updated functions to be found.
    Vlast_prompt_time.stamp ();
  }

  //! Check if directory contains modified subdirectories.
  //!
  //! @param d directory to check
  //! @param last_checked time of last check
  //!
  //! Path patterns that need to be checked for modifications:
  //!
  //!    private/
  //!
  //!    @class/
  //!    @class/private/
  //!
  //!    +namespace/
  //!    +namespace/private/
  //!    +namespace/@class/
  //!    +namespace/@class/private/
  //!
  //! Recursion into sub-namespaces:
  //!
  //!    +namespace/+subnamespace/<like above>
  //!
  //! @return true if directory contains modified subdirectories

  static bool
  subdirs_modified (const std::string& d, const sys::time& last_checked)
  {
    sys::dir_entry dir (d);

    if (dir)
      {
        string_vector flist = dir.read ();

        octave_idx_type len = flist.numel ();

        for (octave_idx_type i = 0; i < len; i++)
          {
            std::string fname = flist[i];

            std::string full_name = sys::file_ops::concat (d, fname);

            sys::file_stat fs (full_name);

            // Check if directory AND if relevant (@,+,private)
            // AND (if modified OR recursion into (@,+) sub-directories)
            if (fs && fs.is_dir ()
                && (fname[0] == '@' || fname[0] == '+' || fname == "private")
                && ((fs.mtime () + fs.time_resolution () > last_checked)
                    || ((fname[0] == '@' || fname[0] == '+')
                        && subdirs_modified (full_name, last_checked))))
              return true;
          }
      }
    else
      {
        std::string msg = dir.error ();
        warning ("load_path: %s: %s", d.c_str (), msg.c_str ());
      }

    return false;
  }

  std::string load_path::s_sys_path;
  load_path::abs_dir_cache_type load_path::s_abs_dir_cache;

  load_path::load_path (interpreter& interp)
    : add_hook ([=] (const std::string& dir) { this->execute_pkg_add (dir); }),
      remove_hook ([=] (const std::string& dir) { this->execute_pkg_del (dir); }),
      m_interpreter (interp), m_package_map (), m_top_level_package (),
      m_dir_info_list (), m_init_dirs (), m_command_line_path ()
  { }

  void
  load_path::initialize (bool set_initial_path)
  {
    s_sys_path = "";

    if (set_initial_path)
      {
        maybe_add_path_elts (s_sys_path, config::local_ver_oct_file_dir ());
        maybe_add_path_elts (s_sys_path, config::local_api_oct_file_dir ());
        maybe_add_path_elts (s_sys_path, config::local_oct_file_dir ());
        maybe_add_path_elts (s_sys_path, config::local_ver_fcn_file_dir ());
        maybe_add_path_elts (s_sys_path, config::local_api_fcn_file_dir ());
        maybe_add_path_elts (s_sys_path, config::local_fcn_file_dir ());
        maybe_add_path_elts (s_sys_path, config::oct_file_dir ());
        maybe_add_path_elts (s_sys_path, config::fcn_file_dir ());
        maybe_add_path_elts (s_sys_path, config::oct_data_dir ());
      }

    std::string tpath = load_path::m_command_line_path;

    if (tpath.empty ())
      tpath = sys::env::getenv ("OCTAVE_PATH");

    std::string xpath;

    if (! tpath.empty ())
      {
        xpath = tpath;

        if (! s_sys_path.empty ())
          xpath += directory_path::path_sep_str () + s_sys_path;
      }
    else
      xpath = s_sys_path;

    set (xpath, false, true);
  }

  void
  load_path::clear (void)
  {
    m_dir_info_list.clear ();

    m_top_level_package.clear ();

    m_package_map.clear ();
  }

  void
  load_path::set (const std::string& p, bool warn, bool is_init)
  {
    // Use a list when we need to preserve order.
    std::list<std::string> elts = split_path (p);

    for (auto& elt : elts)
      elt = maybe_canonicalize (elt);

    // Use a set when we need to search and order is not important.
    std::set<std::string> elts_set (elts.begin (), elts.end ());

    if (is_init)
      m_init_dirs = elts_set;
    else
      {
        for (const auto& init_dir : m_init_dirs)
          {
            if (elts_set.find (init_dir) == elts_set.end ())
              {
                warning_with_id ("Octave:remove-init-dir",
                                 "default load path altered.  Some built-in functions may not be found.  Try restoredefaultpath() to recover it.");
                break;
              }
          }
      }

    // Temporarily disable add hook.

    unwind_protect frame;
    frame.protect_var (add_hook);

    add_hook = nullptr;

    clear ();

    for (const auto& elt : elts)
      append (elt, warn);

    // Restore add hook and execute for all newly added directories.
    frame.run_first ();

    // FIXME: Shouldn't the test for add_hook be outside the for loop?
    //        Why not use const here?  Does add_hook change dir_info_list?
    for (auto& di : m_dir_info_list)
      {
        if (add_hook)
          add_hook (di.dir_name);
      }

    // Always prepend current directory.
    prepend (".", warn);
  }

  void
  load_path::append (const std::string& dir, bool warn)
  {
    if (! dir.empty ())
      add (dir, true, warn);
  }

  void
  load_path::prepend (const std::string& dir, bool warn)
  {
    if (! dir.empty ())
      add (dir, false, warn);
  }

  bool
  load_path::remove (const std::string& dir_arg)
  {
    bool retval = false;

    if (! dir_arg.empty ())
      {
        if (same_file (dir_arg, "."))
          {
            warning (R"(rmpath: can't remove "." from path)");

            // Avoid additional warnings.
            retval = true;
          }
        else
          {
            std::string dir = sys::file_ops::tilde_expand (dir_arg);

            dir = strip_trailing_separators (dir);

            auto i = find_dir_info (dir);

            if (i != m_dir_info_list.end ())
              {
                retval = true;

                if (remove_hook)
                  remove_hook (dir);

                dir_info& di = *i;

                remove (di);

                m_dir_info_list.erase (i);
              }
          }
      }

    return retval;
  }

  void
  load_path::update (void)
  {
    // I don't see a better way to do this because we need to
    // preserve the correct directory ordering for new files that
    // have appeared.

    m_top_level_package.clear ();

    m_package_map.clear ();

    for (auto& di : m_dir_info_list)
      {
        bool ok = di.update ();

        if (! ok)
          warning_with_id
            ("Octave:load-path:update-failed",
             "load-path: update failed for '%s', removing from path",
             di.dir_name.c_str ());
        else
          add (di, true, "", true);
      }
  }

  bool
  load_path::contains_canonical (const std::string& dir) const
  {
    bool retval = false;

    for (const auto& d : m_dir_info_list)
      {
        if (same_file (dir, d.dir_name))
          {
            retval = true;
            break;
          }
      }

    return retval;
  }

  bool
  load_path::contains_file_in_dir (const std::string& file,
                                   const std::string& dir)
  {
    bool ok = false;
    bool addpath_option = true;

    std::string curr_dir = sys::env::get_current_directory ();

    if (same_file (curr_dir, dir))
      ok = true;
    else
      {
        bool dir_in_load_path = contains_canonical (dir);

        // get base name, allowing "@class/method.m" (bug #41514)
        std::string base_file = (file.length () > dir.length ())
                                ? file.substr (dir.length () + 1)
                                : sys::env::base_pathname (file);

        std::string lp_file = find_file (base_file);

        if (dir_in_load_path)
          {
            if (same_file (lp_file, file))
              ok = true;
          }
        else
          {
            // File directory is not in path.  Is the file in the path in
            // the current directory?  If so, then changing the current
            // directory will be needed.  Adding directory to path is
            // not enough because the file in the current directory would
            // still be found.

            if (same_file (lp_file, base_file))
              {
                if (same_file (curr_dir, dir))
                  ok = true;
                else
                  addpath_option = false;
              }
          }
      }

    if (! ok)
      {
        event_manager& evmgr = m_interpreter.get_event_manager ();

        int action
          = evmgr.debug_cd_or_addpath_error (file, dir, addpath_option);

        switch (action)
          {
          case 1:
            m_interpreter.chdir (dir);
            ok = true;
            break;

          case 2:
            {
              prepend (dir);
              ok = true;
            }
            break;

          default:
            break;
          }
      }

    return ok;
  }

  std::list<std::string>
  load_path::overloads (const std::string& meth) const
  {
    std::list<std::string> retval;

    //  update ();

    m_top_level_package.overloads (meth, retval);

    for (const auto& nm_ldr : m_package_map)
      nm_ldr.second.overloads (meth, retval);

    return retval;
  }

  std::list<std::string>
  load_path::get_all_package_names (bool only_top_level) const
  {
    std::list<std::string> retval;

    for (const auto& dir_ldr : m_package_map)
      {
        if (! only_top_level || dir_ldr.first.find ('.') == std::string::npos)
          retval.push_back (dir_ldr.first);
      }

    return retval;
  }

  std::string
  load_path::find_file (const std::string& file) const
  {
    std::string retval;

    if (sys::env::absolute_pathname (file)
        || sys::env::rooted_relative_pathname (file))
      {
        sys::file_stat fs (file);

        return fs.exists () ? file : retval;
      }
    else
      {
        std::string tfile = find_private_file (file);

        if (! tfile.empty ())
          return tfile;
      }

    if (file.find_first_of (sys::file_ops::dir_sep_chars ())
        != std::string::npos)
      {
        // Given name has a directory separator, so append it to each
        // element of the load path in turn.
        for (const auto& di : m_dir_info_list)
          {
            std::string tfile = sys::file_ops::concat (di.abs_dir_name, file);

            sys::file_stat fs (tfile);

            if (fs.exists ())
              return tfile;
          }
      }
    else
      {
        // Look in cache.
        for (const auto & di : m_dir_info_list)
          {
            string_vector all_files = di.all_files;

            octave_idx_type len = all_files.numel ();

            for (octave_idx_type i = 0; i < len; i++)
              {
                if (all_files[i] == file)
                  return sys::file_ops::concat (di.abs_dir_name, file);
              }
          }
      }

    return retval;
  }

  std::string
  load_path::find_dir (const std::string& dir) const
  {
    std::string retval;

    if (dir.find_first_of (sys::file_ops::dir_sep_chars ()) != std::string::npos
        && (sys::env::absolute_pathname (dir)
            || sys::env::rooted_relative_pathname (dir)))
      {
        sys::file_stat fs (dir);

        if (fs.exists () && fs.is_dir ())
          return dir;
      }
    else
      {
        std::string canon_dir = maybe_canonicalize (dir);
        for (const auto& di : m_dir_info_list)
          {
            std::string dname = di.abs_dir_name;

            std::size_t dname_len = dname.length ();

            if (dname.substr (dname_len - 1)
                == sys::file_ops::dir_sep_str ())
              {
                dname = dname.substr (0, dname_len - 1);
                dname_len--;
              }

            std::size_t dir_len = canon_dir.length ();

            if (dname_len > dir_len
                && sys::file_ops::is_dir_sep (dname[dname_len - dir_len - 1])
                && canon_dir == dname.substr (dname_len - dir_len))
              {
                sys::file_stat fs (di.dir_name);

                if (fs.exists () && fs.is_dir ())
                  return di.abs_dir_name;
              }
          }
      }

    return retval;
  }

  string_vector
  load_path::find_matching_dirs (const std::string& dir) const
  {
    std::list<std::string> retlist;

    if (dir.find_first_of (sys::file_ops::dir_sep_chars ()) != std::string::npos
        && (sys::env::absolute_pathname (dir)
            || sys::env::rooted_relative_pathname (dir)))
      {
        sys::file_stat fs (dir);

        if (fs.exists () && fs.is_dir ())
          retlist.push_back (dir);
      }
    else
      {
        std::string canon_dir = maybe_canonicalize (dir);
        for (const auto& di : m_dir_info_list)
          {
            std::string dname = di.abs_dir_name;

            std::size_t dname_len = dname.length ();

            if (dname.substr (dname_len - 1)
                == sys::file_ops::dir_sep_str ())
              {
                dname = dname.substr (0, dname_len - 1);
                dname_len--;
              }

            std::size_t dir_len = canon_dir.length ();

            if (dname_len > dir_len
                && sys::file_ops::is_dir_sep (dname[dname_len - dir_len - 1])
                && canon_dir == dname.substr (dname_len - dir_len))
              {
                sys::file_stat fs (di.dir_name);

                if (fs.exists () && fs.is_dir ())
                  retlist.push_back (di.abs_dir_name);
              }
          }
      }

    return retlist;
  }

  std::string
  load_path::find_first_of (const string_vector& flist) const
  {
    std::string retval;

    std::string dir_name;
    std::string file_name;

    octave_idx_type flen = flist.numel ();
    octave_idx_type rel_flen = 0;

    string_vector rel_flist (flen);

    for (octave_idx_type i = 0; i < flen; i++)
      {
        std::string file = flist[i];

        if (file.find_first_of (sys::file_ops::dir_sep_chars ())
            != std::string::npos)
          {
            if (sys::env::absolute_pathname (file)
                || sys::env::rooted_relative_pathname (file))
              {
                sys::file_stat fs (file);

                if (fs.exists ())
                  return file;
              }
            else
              {
                for (const auto& di : m_dir_info_list)
                  {
                    std::string tfile;
                    tfile = sys::file_ops::concat (di.abs_dir_name, file);

                    sys::file_stat fs (tfile);

                    if (fs.exists ())
                      return tfile;
                  }
              }
          }
        else
          rel_flist[rel_flen++] = file;
      }

    rel_flist.resize (rel_flen);

    for (const auto& di : m_dir_info_list)
      {
        string_vector all_files = di.all_files;

        octave_idx_type len = all_files.numel ();

        for (octave_idx_type i = 0; i < len; i++)
          {
            for (octave_idx_type j = 0; j < rel_flen; j++)
              {
                if (all_files[i] == rel_flist[j])
                  {
                    dir_name = di.abs_dir_name;
                    file_name = rel_flist[j];

                    goto done;
                  }
              }
          }
      }

  done:

    if (! dir_name.empty ())
      retval = sys::file_ops::concat (dir_name, file_name);

    return retval;
  }

  string_vector
  load_path::find_all_first_of (const string_vector& flist) const
  {
    std::list<std::string> retlist;

    std::string dir_name;
    std::string file_name;

    octave_idx_type flen = flist.numel ();
    octave_idx_type rel_flen = 0;

    string_vector rel_flist (flen);

    for (octave_idx_type i = 0; i < flen; i++)
      {
        std::string file = flist[i];

        if (file.find_first_of (sys::file_ops::dir_sep_chars ())
            != std::string::npos)
          {
            if (sys::env::absolute_pathname (file)
                || sys::env::rooted_relative_pathname (file))
              {
                sys::file_stat fs (file);

                if (fs.exists ())
                  retlist.push_back (file);
              }
            else
              {
                for (const auto& di : m_dir_info_list)
                  {
                    std::string tfile;
                    tfile = sys::file_ops::concat (di.abs_dir_name, file);

                    sys::file_stat fs (tfile);

                    if (fs.exists ())
                      retlist.push_back (tfile);
                  }
              }
          }
        else
          rel_flist[rel_flen++] = file;
      }

    rel_flist.resize (rel_flen);

    for (const auto& di : m_dir_info_list)
      {
        string_vector all_files = di.all_files;

        octave_idx_type len = all_files.numel ();

        for (octave_idx_type i = 0; i < len; i++)
          {
            for (octave_idx_type j = 0; j < rel_flen; j++)
              {
                if (all_files[i] == rel_flist[j])
                  retlist.push_back (sys::file_ops::concat (di.abs_dir_name,
                                                            rel_flist[j]));
              }
          }
      }

    return retlist;
  }

  string_vector
  load_path::dirs (void) const
  {
    std::size_t len = m_dir_info_list.size ();

    string_vector retval (len);

    octave_idx_type k = 0;

    for (const auto& di : m_dir_info_list)
      retval[k++] = di.dir_name;

    return retval;
  }

  std::list<std::string>
  load_path::dir_list (void) const
  {
    std::list<std::string> retval;

    for (const auto& di : m_dir_info_list)
      retval.push_back (di.dir_name);

    return retval;
  }

  string_vector
  load_path::files (const std::string& dir, bool omit_exts) const
  {
    string_vector retval;

    const_dir_info_list_iterator p = find_dir_info (dir);

    if (p != m_dir_info_list.end ())
      retval = p->fcn_files;

    if (omit_exts)
      {
        octave_idx_type len = retval.numel ();

        for (octave_idx_type i = 0; i < len; i++)
          {
            std::string fname = retval[i];

            std::size_t pos = fname.rfind ('.');

            if (pos != std::string::npos)
              retval[i] = fname.substr (0, pos);
          }
      }

    return retval;
  }

  string_vector
  load_path::fcn_names (void) const
  {
    return m_top_level_package.fcn_names ();
  }

  std::string
  load_path::path (void) const
  {
    std::string xpath;

    string_vector xdirs = load_path::dirs ();

    octave_idx_type len = xdirs.numel ();

    if (len > 0)
      xpath = xdirs[0];

    for (octave_idx_type i = 1; i < len; i++)
      xpath += directory_path::path_sep_str () + xdirs[i];

    return xpath;
  }

  void
  load_path::display (std::ostream& os) const
  {
    for (const auto& di : m_dir_info_list)
      {
        string_vector fcn_files = di.fcn_files;

        if (! fcn_files.empty ())
          {
            os << "\n*** function files in " << di.dir_name << ":\n\n";

            fcn_files.list_in_columns (os);
          }

        const dir_info::method_file_map_type& method_file_map
          = di.method_file_map;

        if (! method_file_map.empty ())
          {
            for (const auto& cls_ci : method_file_map)
              {
                os << "\n*** methods in " << di.dir_name
                   << "/@" << cls_ci.first << ":\n\n";

                const dir_info::class_info& ci = cls_ci.second;

                string_vector method_files = get_file_list (ci.method_file_map);

                method_files.list_in_columns (os);
              }
          }
      }

    m_top_level_package.display (os);

    for (const auto& nm_ldr : m_package_map)
      nm_ldr.second.display (os);
  }

  void
  load_path::execute_pkg_add (const std::string& dir)
  {
    execute_pkg_add_or_del (dir, "PKG_ADD");
  }

  void
  load_path::execute_pkg_del (const std::string& dir)
  {
    execute_pkg_add_or_del (dir, "PKG_DEL");
  }

  void load_path::execute_pkg_add_or_del (const std::string& dir,
                                          const std::string& script_file)
  {
    if (! octave_interpreter_ready)
      return;

    std::string file = sys::file_ops::concat (dir, script_file);

    sys::file_stat fs (file);

    if (fs.exists ())
      source_file (file, "base");
  }

  // FIXME: maybe we should also maintain a map to speed up this method of
  //        access.

  load_path::const_dir_info_list_iterator
  load_path::find_dir_info (const std::string& dir_arg) const
  {
    std::string dir = sys::file_ops::tilde_expand (dir_arg);

    dir = maybe_canonicalize (dir);

    auto retval = m_dir_info_list.cbegin ();

    while (retval != m_dir_info_list.cend ())
      {
        if (retval->dir_name == dir)
          break;

        retval++;
      }

    return retval;
  }

  load_path::dir_info_list_iterator
  load_path::find_dir_info (const std::string& dir_arg)
  {
    std::string dir = sys::file_ops::tilde_expand (dir_arg);

    dir = maybe_canonicalize (dir);

    auto retval = m_dir_info_list.begin ();

    while (retval != m_dir_info_list.end ())
      {
        if (retval->dir_name == dir)
          break;

        retval++;
      }

    return retval;
  }

  bool
  load_path::contains (const std::string& dir) const
  {
    return find_dir_info (dir) != m_dir_info_list.end ();
  }

  void
  load_path::move (dir_info_list_iterator i, bool at_end)
  {
    if (m_dir_info_list.size () > 1)
      {
        dir_info di = *i;

        m_dir_info_list.erase (i);

        if (at_end)
          m_dir_info_list.push_back (di);
        else
          m_dir_info_list.push_front (di);

        move (di, at_end);
      }
  }

  void
  load_path::move (const dir_info& di, bool at_end, const std::string& pname)
  {
    package_info& l = get_package (pname);

    l.move (di, at_end);

    dir_info::package_dir_map_type package_dir_map = di.package_dir_map;

    for (const auto& pkg_di : package_dir_map)
      {
        std::string full_name = pkg_di.first;

        if (! pname.empty ())
          full_name = pname + '.' + full_name;

        move (pkg_di.second, at_end, full_name);
      }
  }

  void
  load_path::add (const std::string& dir_arg, bool at_end, bool warn)
  {
    std::size_t len = dir_arg.length ();

    if (len > 1 && dir_arg.substr (len-2) == "//")
      warning_with_id ("Octave:recursive-path-search",
                       "trailing '//' is no longer special in search path elements");

    std::string dir = sys::file_ops::tilde_expand (dir_arg);

    dir = strip_trailing_separators (dir);

    dir = maybe_canonicalize (dir);

    auto i = find_dir_info (dir);

    if (i != m_dir_info_list.end ())
      move (i, at_end);
    else
      {
        sys::file_stat fs (dir);

        if (fs)
          {
            if (fs.is_dir ())
              {
                read_dir_config (dir);

                dir_info di (dir);

                if (at_end)
                  m_dir_info_list.push_back (di);
                else
                  m_dir_info_list.push_front (di);

                add (di, at_end);

                if (add_hook)
                  add_hook (dir);
              }
            else if (warn)
              warning ("addpath: %s: not a directory", dir_arg.c_str ());
          }
        else if (warn)
          {
            std::string msg = fs.error ();
            warning ("addpath: %s: %s", dir_arg.c_str (), msg.c_str ());
          }
      }

    // FIXME: is there a better way to do this?

    i = find_dir_info (".");

    if (i != m_dir_info_list.end ())
      move (i, false);
  }

  void
  load_path::remove (const dir_info& di, const std::string& pname)
  {
    package_info& l = get_package (pname);

    l.remove (di);

    dir_info::package_dir_map_type package_dir_map = di.package_dir_map;

    for (const auto& pkg_di : package_dir_map)
      {
        std::string full_name = pkg_di.first;

        if (! pname.empty ())
          full_name = pname + '.' + full_name;

        remove (pkg_di.second, full_name);
      }
  }

  void
  load_path::read_dir_config (const std::string& dir) const
  {
    // use canonicalized path as key
    const std::string key = sys::canonicalize_file_name (dir);

    // read file with directory configuration
    const std::string
    conf_file = key + sys::file_ops::dir_sep_str () + ".oct-config";

    FILE* cfile = sys::fopen (conf_file, "rb");

    if (! cfile)
      {
        // reset directory encoding
        input_system& input_sys = __get_input_system__ ();

        std::string enc_val = "delete";
        input_sys.set_dir_encoding (key, enc_val);
        return;
      }

    unwind_action close_file ([cfile] (void) { fclose (cfile); });

    // find line with character encoding and read it
    bool eof = false;
    const std::string enc_prop = "encoding";
    while (! eof)
      {
        std::string conf_str = fgets (cfile, eof);

        // delete any preceeding whitespace
        auto it = std::find_if_not (conf_str.begin (), conf_str.end (),
                                    [] (unsigned char c)
                                    { return std::isblank (c); });
        conf_str.erase (conf_str.begin (), it);

        // match identifier
        if (conf_str.compare (0, enc_prop.size (), enc_prop) == 0)
          {
            // skip delimiter characters
            std::size_t pos = conf_str.find_first_not_of (" \t=:",
                                                     enc_prop.size ());
            if (pos == std::string::npos)
              continue;

            std::string enc_val = conf_str.substr (pos);

            // take alphanumeric and '-' characters
            it = std::find_if_not (enc_val.begin (), enc_val.end (),
                                   [] (unsigned char c)
                                   { return std::isalnum (c) || c == '-'; });
            enc_val.erase(it, enc_val.end ());

            if (enc_val.empty ())
              continue;

            // set encoding for this directory in input system
            input_system& input_sys = __get_input_system__ ();
            input_sys.set_dir_encoding (key, enc_val);
            return;
          }
      }

    // reset directory encoding
    input_system& input_sys = __get_input_system__ ();

    std::string enc_val = "delete";
    input_sys.set_dir_encoding (dir, enc_val);

  }

  bool
  load_path::is_package (const std::string& name) const
  {
    for (const auto& di : m_dir_info_list)
      {
        if (di.is_package (name))
          return true;
      }

    return false;
  }

  void
  load_path::add (const dir_info& di, bool at_end,
                  const std::string& pname, bool updating)
  {
    package_info& l = get_package (pname);

    l.add (di, at_end, updating);

    dir_info::package_dir_map_type package_dir_map = di.package_dir_map;

    for (const auto& pkg_di : package_dir_map)
      {
        std::string full_name = pkg_di.first;

        if (! pname.empty ())
          full_name = pname + '.' + full_name;

        add (pkg_di.second, at_end, full_name);
      }
  }

  string_vector
  load_path::get_file_list (const load_path::dir_info::fcn_file_map_type& lst) const
  {
    octave_idx_type n = lst.size ();

    string_vector retval (n);

    octave_idx_type count = 0;

    for (const auto& nm_typ : lst)
      {
        std::string nm = nm_typ.first;

        int types = nm_typ.second;

        if (types & load_path::OCT_FILE)
          nm += ".oct";
        else if (types & load_path::MEX_FILE)
          nm += ".mex";
        else
          nm += ".m";

        retval[count++] = nm;
      }

    return retval;
  }

  load_path::dir_info::fcn_file_map_type
  get_fcn_files (const std::string& d)
  {
    load_path::dir_info::fcn_file_map_type retval;

    string_vector flist;
    std::string msg;

    if (! sys::get_dirlist (d, flist, msg))
      warning ("load_path: %s: %s", d.c_str (), msg.c_str ());
    else
      {
        octave_idx_type len = flist.numel ();

        for (octave_idx_type i = 0; i < len; i++)
          {
            std::string fname = flist[i];

            std::size_t pos = fname.rfind ('.');

            if (pos != std::string::npos)
              {
                std::string base = fname.substr (0, pos);
                std::string ext = fname.substr (pos);

                if (valid_identifier (base))
                  {
                    int t = 0;

                    if (ext == ".m")
                      t = load_path::M_FILE;
                    else if (ext == ".oct")
                      t = load_path::OCT_FILE;
                    else if (ext == ".mex")
                      t = load_path::MEX_FILE;

                    if (t)
                      {
                        load_path::dir_info::fcn_file_map_iterator p
                          = retval.find (base);

                        if (p == retval.end ())
                          retval[base] = t;
                        else
                          p->second |= t;
                      }
                  }
              }
          }
      }

    return retval;
  }

  bool
  load_path::dir_info::update (void)
  {
    sys::file_stat fs (dir_name);

    if (! fs)
      {
        std::string msg = fs.error ();
        warning_with_id ("Octave:load-path:dir-info:update-failed",
                         "load_path: %s: %s", dir_name.c_str (), msg.c_str ());

        return false;
      }

    if (is_relative)
      {
        try
          {
            std::string abs_name = sys::canonicalize_file_name (dir_name);

            const_abs_dir_cache_iterator p = s_abs_dir_cache.find (abs_name);

            if (p != s_abs_dir_cache.end ())
              {
                // The directory is in the cache of all directories we have
                // visited (indexed by absolute name).  If it is out of date,
                // initialize it.  Otherwise, copy the info from the cache.
                // By doing that, we avoid unnecessary calls to stat that can
                // slow things down tremendously for large directories.
                const dir_info& di = p->second;

                if ((fs.mtime () + fs.time_resolution ()
                     > di.dir_time_last_checked)
                    || subdirs_modified (dir_name, dir_time_last_checked))
                  initialize ();
                else
                  {
                    // Copy over info from cache, but leave dir_name and
                    // is_relative unmodified.
                    abs_dir_name = di.abs_dir_name;
                    dir_mtime = di.dir_mtime;
                    dir_time_last_checked = di.dir_time_last_checked;
                    all_files = di.all_files;
                    fcn_files = di.fcn_files;
                    private_file_map = di.private_file_map;
                    method_file_map = di.method_file_map;
                    package_dir_map = di.package_dir_map;
                  }
              }
            else
              {
                // We haven't seen this directory before.
                initialize ();
              }
          }
        catch (const execution_exception& ee)
          {
            // Skip updating if we don't know where we are, but don't
            // treat it as an error.

            interpreter& interp = __get_interpreter__ ();

            interp.recover_from_exception ();
          }
      }
    // Absolute path, check timestamp to see whether it requires re-caching
    else if (fs.mtime () + fs.time_resolution () > dir_time_last_checked
             || subdirs_modified (dir_name, dir_time_last_checked))
      initialize ();

    return true;
  }

  bool
  load_path::dir_info::is_package (const std::string& name) const
  {
    std::size_t pos = name.find ('.');

    if (pos == std::string::npos)
      return package_dir_map.find (name) != package_dir_map.end ();
    else
      {
        std::string name_head = name.substr (0, pos);
        std::string name_tail = name.substr (pos + 1);

        const_package_dir_map_iterator it = package_dir_map.find (name_head);

        if (it != package_dir_map.end ())
          return it->second.is_package (name_tail);
        else
          return false;
      }
  }

  void
  load_path::dir_info::initialize (void)
  {
    is_relative = ! sys::env::absolute_pathname (dir_name);

    dir_time_last_checked = sys::time (static_cast<OCTAVE_TIME_T> (0));

    sys::file_stat fs (dir_name);

    if (fs)
      {
        method_file_map.clear ();
        package_dir_map.clear ();

        dir_mtime = fs.mtime ();
        dir_time_last_checked = sys::time ();

        get_file_list (dir_name);

        try
          {
            abs_dir_name = sys::canonicalize_file_name (dir_name);

            // FIXME: nothing is ever removed from this cache of
            // directory information, so there could be some resource
            // problems.  Perhaps it should be pruned from time to time.

            s_abs_dir_cache[abs_dir_name] = *this;
          }
        catch (const execution_exception&)
          {
            // Skip updating if we don't know where we are but don't treat
            // it as an error.

            interpreter& interp = __get_interpreter__ ();

            interp.recover_from_exception ();
          }
      }
    else
      {
        std::string msg = fs.error ();
        warning ("load_path: %s: %s", dir_name.c_str (), msg.c_str ());
      }
  }

  void
  load_path::dir_info::get_file_list (const std::string& d)
  {
    string_vector flist;
    std::string msg;

    if (! sys::get_dirlist (d, flist, msg))
      {
        warning ("load_path: %s: %s", d.c_str (), msg.c_str ());
        return;
      }

    octave_idx_type len = flist.numel ();

    all_files.resize (len);
    fcn_files.resize (len);

    octave_idx_type all_files_count = 0;
    octave_idx_type fcn_files_count = 0;

    for (octave_idx_type i = 0; i < len; i++)
      {
        std::string fname = flist[i];

        std::string full_name = sys::file_ops::concat (d, fname);

        sys::file_stat fs (full_name);

        if (fs)
          {
            if (fs.is_dir ())
              {
                if (fname == "private")
                  get_private_file_map (full_name);
                else if (fname[0] == '@')
                  get_method_file_map (full_name, fname.substr (1));
                else if (fname[0] == '+')
                  get_package_dir (full_name, fname.substr (1));
              }
            else
              {
                all_files[all_files_count++] = fname;

                std::size_t pos = fname.rfind ('.');

                if (pos != std::string::npos)
                  {
                    std::string ext = fname.substr (pos);

                    if (ext == ".m" || ext == ".oct" || ext == ".mex")
                      {
                        std::string base = fname.substr (0, pos);

                        if (valid_identifier (base))
                          fcn_files[fcn_files_count++] = fname;
                      }
                  }
              }
          }
      }

    all_files.resize (all_files_count);
    fcn_files.resize (fcn_files_count);
  }

  void
  load_path::dir_info::get_private_file_map (const std::string& d)
  {
    private_file_map = get_fcn_files (d);
  }

  void
  load_path::dir_info::get_method_file_map (const std::string& d,
                                            const std::string& class_name)
  {
    method_file_map[class_name].method_file_map = get_fcn_files (d);

    std::string pd = sys::file_ops::concat (d, "private");

    sys::file_stat fs (pd);

    if (fs && fs.is_dir ())
      method_file_map[class_name].private_file_map = get_fcn_files (pd);
  }

  void
  load_path::dir_info::get_package_dir (const std::string& d,
                                        const std::string& package_name)
  {
    package_dir_map[package_name] = dir_info (d);
  }

  void
  load_path::package_info::move (const dir_info& di, bool at_end)
  {
    std::string dir_name = di.abs_dir_name;

    auto s = std::find (m_dir_list.begin (), m_dir_list.end (), dir_name);

    if (s != m_dir_list.end ())
      {
        m_dir_list.erase (s);

        if (at_end)
          m_dir_list.push_back (dir_name);
        else
          m_dir_list.push_front (dir_name);
      }

    move_fcn_map (dir_name, di.fcn_files, at_end);

    // No need to move elements of private function map.

    move_method_map (dir_name, at_end);
  }

  void
  load_path::package_info::remove (const dir_info& di)
  {
    std::string dir = di.abs_dir_name;

    string_vector fcn_files = di.fcn_files;

    m_dir_list.remove (dir);

    remove_fcn_map (dir, fcn_files);

    remove_private_fcn_map (dir);

    remove_method_map (dir);
  }

  void
  load_path::package_info::display (std::ostream& os) const
  {
    os << "*** package_info: "
       << (m_package_name.empty () ? "<top-level>" : m_package_name)
       << "\n\n";

    for (const auto& dir : m_dir_list)
      os << dir << "\n";
    os << "\n";

    for (const auto& dir_fnlst : m_private_fcn_map)
      {
        os << "\n*** private functions in "
           << sys::file_ops::concat (dir_fnlst.first, "private")
           << ":\n\n";

        print_fcn_list (os, dir_fnlst.second);
      }

#if defined (DEBUG_LOAD_PATH)

    for (const auto& nm_filst : m_fcn_map)
      {
        os << nm_filst.first << ":\n";

        const file_info_list_type& file_info_list = nm_filst.second;

        for (const auto& finfo : file_info_list)
          {
            os << "  " << finfo.dir_name << " (";

            print_types (os, finfo.types);

            os << ")\n";
          }
      }

    for (const auto& cls_fnmap : m_method_map)
      {
        os << "CLASS " << cls_fnmap.first << ":\n";

        const fcn_map_type& fm = cls_fnmap.second;

        for (const auto& nm_fnlst : m_fcn_map)
          {
            os << "  " << nm_fnlst.first << ":\n";

            const file_info_list_type& file_info_list = nm_fnlst.second;

            for (const auto& finfo : file_info_list)
              {
                os << "  " << finfo.dir_name << " (";

                print_types (os, finfo.types);

                os << ")\n";
              }
          }
      }

    os << "\n";

#endif
  }

  std::string
  load_path::package_info::find_fcn (const std::string& fcn,
                                     std::string& dir_name,
                                     int type) const
  {
    std::string retval;

    //  update ();

    if (fcn.length () > 0 && fcn[0] == '@')
      {
        std::size_t pos = fcn.find ('/');

        if (pos != std::string::npos)
          {
            std::string class_name = fcn.substr (1, pos-1);
            std::string meth = fcn.substr (pos+1);

            retval = find_method (class_name, meth, dir_name);
          }
        else
          retval = "";
      }
    else
      {
        dir_name = "";

        const_fcn_map_iterator p = m_fcn_map.find (fcn);

        if (p != m_fcn_map.end ())
          {
            const file_info_list_type& file_info_list = p->second;

            for (const auto& fi : file_info_list)
              {
                retval = sys::file_ops::concat (fi.dir_name, fcn);

                if (check_file_type (retval, type, fi.types,
                                     fcn, "load_path::find_fcn"))
                  {
                    dir_name = fi.dir_name;
                    break;
                  }
                else
                  retval = "";
              }
          }
      }

    return retval;
  }

  std::string
  load_path::package_info::find_private_fcn (const std::string& dir,
                                             const std::string& fcn,
                                             int type) const
  {
    std::string retval;

    //  update ();

    const_private_fcn_map_iterator q = m_private_fcn_map.find (dir);

    if (q != m_private_fcn_map.end ())
      {
        const dir_info::fcn_file_map_type& fcn_file_map = q->second;

        dir_info::const_fcn_file_map_iterator p = fcn_file_map.find (fcn);

        if (p != fcn_file_map.end ())
          {
            std::string fname
              = sys::file_ops::concat (sys::file_ops::concat (dir, "private"),
                                       fcn);

            if (check_file_type (fname, type, p->second, fcn,
                                 "load_path::find_private_fcn"))
              retval = fname;
          }
      }

    return retval;
  }

  std::string
  load_path::package_info::find_method (const std::string& class_name,
                                        const std::string& meth,
                                        std::string& dir_name,
                                        int type) const
  {
    std::string retval;

    //  update ();

    dir_name = "";

    const_method_map_iterator q = m_method_map.find (class_name);

    if (q != m_method_map.end ())
      {
        const fcn_map_type& m = q->second;

        const_fcn_map_iterator p = m.find (meth);

        if (p != m.end ())
          {
            const file_info_list_type& file_info_list = p->second;

            for (const auto& fi : file_info_list)
              {
                retval = sys::file_ops::concat (fi.dir_name, meth);

                bool found = check_file_type (retval, type, fi.types,
                                              meth, "load_path::find_method");

                if (found)
                  {
                    dir_name = fi.dir_name;
                    break;
                  }
                else
                  retval = "";
              }
          }
      }

    return retval;
  }

  std::list<std::string>
  load_path::package_info::methods (const std::string& class_name) const
  {
    std::list<std::string> retval;

    //  update ();

    const_method_map_iterator mtd_map_it = m_method_map.find (class_name);

    if (mtd_map_it != m_method_map.end ())
      {
        for (const auto& nm_filst : mtd_map_it->second)
          retval.push_back (nm_filst.first);
      }

    if (! retval.empty ())
      retval.sort ();

    return retval;
  }

  void
  load_path::package_info::overloads (const std::string& meth,
                                      std::list<std::string>& l) const
  {
    for (const auto& cls_fnmap : m_method_map)
      {
        const fcn_map_type& m = cls_fnmap.second;

        if (m.find (meth) != m.end ())
          {
            std::string class_name = cls_fnmap.first;

            if (! m_package_name.empty ())
              class_name = m_package_name + '.' + class_name;

            l.push_back (class_name);
          }
      }
  }

  string_vector
  load_path::package_info::fcn_names (void) const
  {
    std::size_t len = m_fcn_map.size ();

    string_vector retval (len);

    octave_idx_type count = 0;

    for (const auto& nm_filst : m_fcn_map)
      retval[count++] = nm_filst.first;

    return retval;
  }

  void
  load_path::package_info::add_to_fcn_map (const dir_info& di,
                                           bool at_end, bool updating)
  {
    std::string dir_name = di.abs_dir_name;

    string_vector fcn_files = di.fcn_files;

    octave_idx_type len = fcn_files.numel ();

    for (octave_idx_type i = 0; i < len; i++)
      {
        std::string fname = fcn_files[i];

        std::string ext;
        std::string base = fname;

        std::size_t pos = fname.rfind ('.');

        if (pos != std::string::npos)
          {
            base = fname.substr (0, pos);
            ext = fname.substr (pos);
          }

        file_info_list_type& file_info_list = m_fcn_map[base];

        auto p = file_info_list.begin ();

        while (p != file_info_list.end ())
          {
            if (p->dir_name == dir_name)
              break;

            p++;
          }

        int t = 0;
        if (ext == ".m")
          t = load_path::M_FILE;
        else if (ext == ".oct")
          t = load_path::OCT_FILE;
        else if (ext == ".mex")
          t = load_path::MEX_FILE;

        if (p == file_info_list.end ())
          {
            // Warn if a built-in or library function is being shadowed,
            // but not if we are just updating (rehashing) the list.

            if (! updating)
              {
                if (file_info_list.empty ())
                  {
                    symbol_table& symtab = __get_symbol_table__ ();

                    if (symtab.is_built_in_function_name (base))
                      {
                        std::string fcn_path = sys::file_ops::concat (dir_name,
                                                                      fname);

                        warning_with_id ("Octave:shadowed-function",
                                         "function %s shadows a built-in function",
                                         fcn_path.c_str ());
                      }
                  }
                else if (! at_end)
                  {
                    file_info& old = file_info_list.front ();

                    // FIXME: do we need to be more careful about the
                    // way we look for old.dir_name in sys_path to avoid
                    // partial matches?

                    // Don't warn about Contents.m files since we expect
                    // more than one to exist in the load path.

                    if (fname != "Contents.m"
                        && s_sys_path.find (old.dir_name) != std::string::npos
                        && in_path_list (s_sys_path, old.dir_name))
                      {
                        std::string fcn_path = sys::file_ops::concat (dir_name,
                                                                      fname);

                        warning_with_id ("Octave:shadowed-function",
                                         "function %s shadows a core library function",
                                         fcn_path.c_str ());
                      }
                  }
              }

            file_info fi (dir_name, t);

            if (at_end)
              file_info_list.push_back (fi);
            else
              file_info_list.push_front (fi);
          }
        else
          {
            file_info& fi = *p;

            fi.types |= t;
          }
      }
  }

  void
  load_path::package_info::add_to_private_fcn_map (const dir_info& di)
  {
    dir_info::fcn_file_map_type private_file_map = di.private_file_map;

    if (! private_file_map.empty ())
      m_private_fcn_map[di.abs_dir_name] = private_file_map;
  }

  void
  load_path::package_info::add_to_method_map (const dir_info& di, bool at_end)
  {
    std::string dir_name = di.abs_dir_name;

    // <CLASS_NAME, CLASS_INFO>
    dir_info::method_file_map_type method_file_map = di.method_file_map;

    for (const auto& cls_ci : method_file_map)
      {
        std::string class_name = cls_ci.first;

        fcn_map_type& fm = m_method_map[class_name];

        std::string full_dir_name
          = sys::file_ops::concat (dir_name, '@' + class_name);

        const dir_info::class_info& ci = cls_ci.second;

        // <FCN_NAME, TYPES>
        const dir_info::fcn_file_map_type& m = ci.method_file_map;

        for (const auto& nm_typ : m)
          {
            std::string base = nm_typ.first;
            int types = nm_typ.second;

            file_info_list_type& file_info_list = fm[base];

            auto p2 = file_info_list.begin ();
            while (p2 != file_info_list.end ())
              {
                if (p2->dir_name == full_dir_name)
                  break;

                p2++;
              }

            if (p2 == file_info_list.end ())
              {
                file_info fi (full_dir_name, types);

                if (at_end)
                  file_info_list.push_back (fi);
                else
                  file_info_list.push_front (fi);
              }
            else
              {
                // FIXME: is this possible?
                file_info& fi = *p2;

                fi.types = types;
              }
          }

        // <FCN_NAME, TYPES>
        dir_info::fcn_file_map_type private_file_map = ci.private_file_map;

        if (! private_file_map.empty ())
          m_private_fcn_map[full_dir_name] = private_file_map;
      }
  }

  void
  load_path::package_info::move_fcn_map (const std::string& dir_name,
                                         const string_vector& fcn_files,
                                         bool at_end)
  {
    octave_idx_type len = fcn_files.numel ();

    for (octave_idx_type k = 0; k < len; k++)
      {
        std::string fname = fcn_files[k];

        std::string ext;
        std::string base = fname;

        std::size_t pos = fname.rfind ('.');

        if (pos != std::string::npos)
          {
            base = fname.substr (0, pos);
            ext = fname.substr (pos);
          }

        file_info_list_type& file_info_list = m_fcn_map[base];

        if (file_info_list.size () == 1)
          continue;
        else
          {
            for (auto fi_it = file_info_list.begin ();
                 fi_it != file_info_list.end ();
                 fi_it++)
              {
                if (fi_it->dir_name == dir_name)
                  {
                    file_info fi_tmp = *fi_it;

                    file_info_list.erase (fi_it);

                    if (at_end)
                      file_info_list.push_back (fi_tmp);
                    else
                      file_info_list.push_front (fi_tmp);

                    break;
                  }
              }
          }
      }
  }

  void
  load_path::package_info::move_method_map (const std::string& dir_name,
                                            bool at_end)
  {
    for (auto& cls_fnmap : m_method_map)
      {
        std::string class_name = cls_fnmap.first;

        fcn_map_type& fn_map = cls_fnmap.second;

        std::string full_dir_name
          = sys::file_ops::concat (dir_name, '@' + class_name);

        for (auto& nm_filst : fn_map)
          {
            file_info_list_type& file_info_list = nm_filst.second;

            if (file_info_list.size () == 1)
              continue;
            else
              {
                for (auto fi_it = file_info_list.begin ();
                     fi_it != file_info_list.end (); fi_it++)
                  {
                    if (fi_it->dir_name == full_dir_name)
                      {
                        file_info fi_tmp = *fi_it;

                        file_info_list.erase (fi_it);

                        if (at_end)
                          file_info_list.push_back (fi_tmp);
                        else
                          file_info_list.push_front (fi_tmp);

                        break;
                      }
                  }
              }
          }
      }
  }

  void
  load_path::package_info::remove_fcn_map (const std::string& dir,
                                           const string_vector& fcn_files)
  {
    octave_idx_type len = fcn_files.numel ();

    for (octave_idx_type k = 0; k < len; k++)
      {
        std::string fname = fcn_files[k];

        std::string ext;
        std::string base = fname;

        std::size_t pos = fname.rfind ('.');

        if (pos != std::string::npos)
          {
            base = fname.substr (0, pos);
            ext = fname.substr (pos);
          }

        file_info_list_type& file_info_list = m_fcn_map[base];

        for (auto fi_it = file_info_list.begin ();
             fi_it != file_info_list.end ();
             fi_it++)
          {
            if (fi_it->dir_name == dir)
              {
                file_info_list.erase (fi_it);

                if (file_info_list.empty ())
                  m_fcn_map.erase (fname);

                break;
              }
          }
      }
  }

  void
  load_path::package_info::remove_private_fcn_map (const std::string& dir)
  {
    auto p = m_private_fcn_map.find (dir);

    if (p != m_private_fcn_map.end ())
      m_private_fcn_map.erase (p);
  }

  void
  load_path::package_info::remove_method_map (const std::string& dir)
  {
    for (auto& cls_fnmap : m_method_map)
      {
        std::string class_name = cls_fnmap.first;

        fcn_map_type& fn_map = cls_fnmap.second;

        std::string full_dir_name
          = sys::file_ops::concat (dir, '@' + class_name);

        for (auto& nm_filst : fn_map)
          {
            file_info_list_type& file_info_list = nm_filst.second;

            if (file_info_list.size () == 1)
              continue;
            else
              {
                for (auto fi_it = file_info_list.begin ();
                     fi_it != file_info_list.end (); fi_it++)
                  {
                    if (fi_it->dir_name == full_dir_name)
                      {
                        file_info_list.erase (fi_it);
                        // FIXME: if there are no other elements, we
                        // should remove this element of fn_map but calling
                        // erase here would invalidate the iterator fi_it.

                        break;
                      }
                  }
              }
          }
      }
  }

  bool
  load_path::package_info::check_file_type (std::string& fname, int type,
                                            int possible_types,
                                            const std::string& fcn,
                                            const char *who) const
  {
    bool retval = false;

    if (type == load_path::OCT_FILE)
      {
        if ((type & possible_types) == load_path::OCT_FILE)
          {
            fname += ".oct";
            retval = true;
          }
      }
    else if (type == load_path::M_FILE)
      {
        if ((type & possible_types) == load_path::M_FILE)
          {
            fname += ".m";
            retval = true;
          }
      }
    else if (type == load_path::MEX_FILE)
      {
        if ((type & possible_types) == load_path::MEX_FILE)
          {
            fname += ".mex";
            retval = true;
          }
      }
    else if (type == (load_path::M_FILE | load_path::OCT_FILE))
      {
        if (possible_types & load_path::OCT_FILE)
          {
            fname += ".oct";
            retval = true;
          }
        else if (possible_types & load_path::M_FILE)
          {
            fname += ".m";
            retval = true;
          }
      }
    else if (type == (load_path::M_FILE | load_path::MEX_FILE))
      {
        if (possible_types & load_path::MEX_FILE)
          {
            fname += ".mex";
            retval = true;
          }
        else if (possible_types & load_path::M_FILE)
          {
            fname += ".m";
            retval = true;
          }
      }
    else if (type == (load_path::OCT_FILE | load_path::MEX_FILE))
      {
        if (possible_types & load_path::OCT_FILE)
          {
            fname += ".oct";
            retval = true;
          }
        else if (possible_types & load_path::MEX_FILE)
          {
            fname += ".mex";
            retval = true;
          }
      }
    else if (type == (load_path::M_FILE | load_path::OCT_FILE
                      | load_path::MEX_FILE))
      {
        if (possible_types & load_path::OCT_FILE)
          {
            fname += ".oct";
            retval = true;
          }
        else if (possible_types & load_path::MEX_FILE)
          {
            fname += ".mex";
            retval = true;
          }
        else if (possible_types & load_path::M_FILE)
          {
            fname += ".m";
            retval = true;
          }
      }
    else
      error ("%s: %s: invalid type code = %d", who, fcn.c_str (), type);

    return retval;
  }

  void
  load_path::package_info::print_types (std::ostream& os, int types) const
  {
    bool printed_type = false;

    if (types & load_path::OCT_FILE)
      {
        os << "oct";
        printed_type = true;
      }

    if (types & load_path::MEX_FILE)
      {
        if (printed_type)
          os << '|';
        os << "mex";
        printed_type = true;
      }

    if (types & load_path::M_FILE)
      {
        if (printed_type)
          os << '|';
        os << 'm';
        printed_type = true;
      }
  }

  void
  load_path::package_info::print_fcn_list (std::ostream& os,
                                           const load_path::dir_info::fcn_file_map_type& lst) const
  {
    for (const auto& nm_typ : lst)
      {
        os << "  " << nm_typ.first << " (";

        print_types (os, nm_typ.second);

        os << ")\n";
      }
  }

  std::string
  genpath (const std::string& dirname, const string_vector& skip)
  {
    std::string retval;
    string_vector dirlist;
    std::string msg;

    if (! sys::get_dirlist (dirname, dirlist, msg))
      return retval;

    retval = dirname;

    dirlist = dirlist.sort (false);

    octave_idx_type len = dirlist.numel ();

    for (octave_idx_type i = 0; i < len; i++)
      {
        std::string elt = dirlist[i];

        bool skip_p = (elt == "." || elt == ".." || elt[0] == '@'
                       || elt[0] == '+');

        if (! skip_p)
          {
            for (octave_idx_type j = 0; j < skip.numel (); j++)
              {
                skip_p = (elt == skip[j]);
                if (skip_p)
                  break;
              }

            if (! skip_p)
              {
                std::string nm = sys::file_ops::concat (dirname, elt);

                sys::file_stat fs (nm);

                if (fs && fs.is_dir ())
                  retval += (directory_path::path_sep_str ()
                             + genpath (nm, skip));
              }
          }
      }

    return retval;
  }

DEFUN (genpath, args, ,
       doc: /* -*- texinfo -*-
@deftypefn  {} {@var{pathstr} =} genpath (@var{dir})
@deftypefnx {} {@var{pathstr} =} genpath (@var{dir}, @var{skipdir1}, @dots{})
Return a path constructed from @var{dir} and all its subdirectories.

The path does not include package directories (beginning with @samp{+}),
old-style class directories (beginning with @samp{@@}), @file{private}
directories, or any subdirectories of these types.

If additional string parameters are given, the resulting path will exclude
directories with those names.
@seealso{path, addpath}
@end deftypefn */)
{
  int nargin = args.length ();

  if (nargin == 0)
    print_usage ();

  octave_value retval;

  if (nargin == 1)
    {
      std::string dirname = args(0).xstring_value ("genpath: DIR must be a string");

      retval = genpath (dirname);
    }
  else
    {
      std::string dirname = args(0).xstring_value ("genpath: all arguments must be strings");

      string_vector skip (nargin - 1);

      for (octave_idx_type i = 1; i < nargin; i++)
        skip[i-1] = args(i).xstring_value ("genpath: all arguments must be strings");

      retval = genpath (dirname, skip);
    }

  return retval;
}

DEFUN (rehash, , ,
       doc: /* -*- texinfo -*-
@deftypefn {} {} rehash ()
Reinitialize Octave's load path directory cache.
@end deftypefn */)
{
  rehash_internal ();

  return ovl ();
}

DEFMETHOD (command_line_path, interp, args, ,
           doc: /* -*- texinfo -*-
@deftypefn {} {@var{pathstr} =} command_line_path ()
Return the path argument given to Octave at the command line when the
interpreter was started (@w{@env{--path @var{arg}}}).

@seealso{path, addpath, rmpath, genpath, pathdef, savepath, pathsep}
@end deftypefn */)
{
  if (! args.empty ())
    print_usage ();

  load_path& lp = interp.get_load_path ();

  return ovl (lp.get_command_line_path ());
}

DEFMETHOD (restoredefaultpath, interp, args, ,
           doc: /* -*- texinfo -*-
@deftypefn {} {@var{pathstr} =} restoredefaultpath ()
Restore Octave's path to its initial state at startup.

The re-initialized path is returned as an output.
@seealso{path, addpath, rmpath, genpath, pathdef, savepath, pathsep}
@end deftypefn */)
{
  if (! args.empty ())
    print_usage ();

  load_path& lp = interp.get_load_path ();

  lp.initialize (true);

  return ovl (lp.system_path ());
}

// Return Octave's original default list of directories in which to
// search for function files.  This corresponds to the path that
// exists prior to running the system's octaverc file or the user's
// ~/.octaverc file

DEFMETHOD (__pathorig__, interp, , ,
           doc: /* -*- texinfo -*-
@deftypefn {} {@var{str} =} __pathorig__ ()
Undocumented internal function.
@end deftypefn */)
{
  load_path& lp = interp.get_load_path ();

  return ovl (lp.system_path ());
}

DEFMETHOD (path, interp, args, nargout,
           doc: /* -*- texinfo -*-
@deftypefn  {} {} path ()
@deftypefnx {} {@var{str} =} path ()
@deftypefnx {} {@var{str} =} path (@var{path1}, @dots{})
Modify or display Octave's load path.

If @var{nargin} and @var{nargout} are zero, display the elements of
Octave's load path in an easy to read format.

If @var{nargin} is zero and nargout is greater than zero, return the
current load path.

If @var{nargin} is greater than zero, concatenate the arguments,
separating them with @code{pathsep}.  Set the internal search path
to the result and return it.

No checks are made for duplicate elements.
@seealso{addpath, rmpath, genpath, pathdef, savepath, pathsep}
@end deftypefn */)
{
  int nargin = args.length ();

  string_vector argv = args.make_argv ("path");

  load_path& lp = interp.get_load_path ();

  if (nargin > 0)
    {
      std::string path = argv[1];

      for (int i = 2; i <= nargin; i++)
        path += directory_path::path_sep_str () + argv[i];

      lp.set (path, true);

      rehash_internal ();
    }

  if (nargout > 0)
    return ovl (lp.path ());
  else if (nargin == 0 && nargout == 0)
    {
      octave_stdout <<
        "\nOctave's search path contains the following directories:\n\n";

      string_vector dirs = lp.dirs ();

      dirs.list_in_columns (octave_stdout);

      octave_stdout << "\n";
    }

  return ovl ();
}

DEFMETHOD (addpath, interp, args, nargout,
           doc: /* -*- texinfo -*-
@deftypefn  {} {} addpath (@var{dir1}, @dots{})
@deftypefnx {} {} addpath (@var{dir1}, @dots{}, @var{option})
@deftypefnx {} {@var{oldpath} =} addpath (@dots{})
Add named directories to the function search path.

If @var{option} is @qcode{"-begin"} or 0 (the default), prepend the directory
name(s) to the current path.  If @var{option} is @qcode{"-end"} or 1, append
the directory name(s) to the current path.  Directories added to the path must
exist.

In addition to accepting individual directory arguments, lists of
directory names separated by @code{pathsep} are also accepted.  For example:

@example
addpath ("dir1:/dir2:~/dir3")
@end example

The newly added paths appear in the load path in the same order that they
appear in the arguments of @code{addpath}.  When extending the load path to
the front, the last path in the list of arguments is added first.  When
extending the load path to the end, the first path in the list of arguments
is added first.

For each directory that is added, and that was not already in the path,
@code{addpath} checks for the existence of a file named @file{PKG_ADD}
(note lack of .m extension) and runs it if it exists.

@seealso{path, rmpath, genpath, pathdef, savepath, pathsep}
@end deftypefn */)
{
  // Originally written by Bill Denney and Etienne Grossman.
  // Heavily modified and translated to C++ by jwe.

  int nargin = args.length ();

  if (nargin == 0)
    print_usage ();

  load_path& lp = interp.get_load_path ();

  octave_value retval;

  if (nargout > 0)
    retval = lp.path ();

  bool append = false;

  octave_value option_arg = args(nargin-1);

  if (option_arg.is_string ())
    {
      std::string option = option_arg.string_value ();

      if (option == "-end")
        {
          append = true;
          nargin--;
        }
      else if (option == "-begin")
        nargin--;
    }
  else if (option_arg.isnumeric ())
    {
      int val = option_arg.xint_value ("addpath: OPTION must be '-begin'/0 or '-end'/1");

      if (val == 0)
        nargin--;
      else if (val == 1)
        {
          append = true;
          nargin--;
        }
      else
        error ("addpath: OPTION must be '-begin'/0 or '-end'/1");
    }

  bool need_to_update = false;

  octave_value_list arglist (args.slice (0, nargin));
  if (! append)
    arglist.reverse ();

  for (int i = 0; i < arglist.length (); i++)
    {
      std::string arg = arglist(i).xstring_value ("addpath: all arguments must be strings");

      std::list<std::string> dir_elts = split_path (arg);

      if (! append)
        std::reverse (dir_elts.begin (), dir_elts.end ());

      for (auto dir : dir_elts)
        {
          // Remove duplicate directory separators
          auto it_start = dir.begin ();
#if defined (OCTAVE_HAVE_WINDOWS_FILESYSTEM)
          // In Windows, start check at second character (for UNC paths).
          it_start++;
#endif
          dir.erase (std::unique
                     (it_start, dir.end (),
                      [] (char l, char r)
                      {
                        return l == r && sys::file_ops::is_dir_sep (l);
                      }),
                     dir.end ());

          auto pos = dir.find_last_of (sys::file_ops::dir_sep_chars ());
          if (pos == std::string::npos)
            {
              if (! dir.empty () && dir[0] == '+')
                warning_with_id ("Octave:addpath-pkg",
                                 "addpath: package directories should not be "
                                 "added to path: %s\n", dir.c_str ());
            }
          else
            {
              if (pos + 1 < dir.length () && dir[pos+1] == '+')
                warning_with_id ("Octave:addpath-pkg",
                                 "addpath: package directories should not be "
                                 "added to path: %s\n", dir.c_str ());
            }

          if (append)
            lp.append (dir, true);
          else
            lp.prepend (dir, true);

          need_to_update = true;
        }
    }

  if (need_to_update)
    rehash_internal ();

  return retval;
}

DEFMETHOD (rmpath, interp, args, nargout,
           doc: /* -*- texinfo -*-
@deftypefn  {} {} rmpath (@var{dir1}, @dots{})
@deftypefnx {} {@var{oldpath} =} rmpath (@var{dir1}, @dots{})
Remove @var{dir1}, @dots{} from the current function search path.

In addition to accepting individual directory arguments, lists of
directory names separated by @code{pathsep} are also accepted.  For example:

@example
rmpath ("dir1:/dir2:~/dir3")
@end example

For each directory that is removed, @code{rmpath} checks for the
existence of a file named @file{PKG_DEL} (note lack of .m extension)
and runs it if it exists.

@seealso{path, addpath, genpath, pathdef, savepath, pathsep}
@end deftypefn */)
{
  // Originally written by Etienne Grossmann.  Heavily modified and translated
  // to C++ by jwe.

  int nargin = args.length ();

  if (nargin == 0)
    print_usage ();

  octave_value retval;

  load_path& lp = interp.get_load_path ();

  if (nargout > 0)
    retval = lp.path ();

  bool need_to_update = false;

  for (int i = 0; i < nargin; i++)
    {
      std::string arg = args(i).xstring_value ("rmpath: all arguments must be strings");
      std::list<std::string> dir_elts = split_path (arg);

      for (const auto& dir : dir_elts)
        {
          //dir = regexprep (dir_elts{j}, '//+', "/");
          //dir = regexprep (dir, '/$', "");

          if (! lp.remove (dir))
            warning ("rmpath: %s: not found", dir.c_str ());
          else
            need_to_update = true;
        }
    }

  if (need_to_update)
    rehash_internal ();

  return retval;
}

DEFMETHOD (__dump_load_path__, interp, , ,
           doc: /* -*- texinfo -*-
@deftypefn {} {} __dump_load_path__ ()
Pretty print Octave path directories and the files within each directory.
@end deftypefn */)
{
  load_path& lp = interp.get_load_path ();

  lp.display (octave_stdout);

  return ovl ();
}

OCTAVE_END_NAMESPACE(octave)