#include "source/extensions/http/header_validators/envoy_default/path_normalizer.h"

#include "envoy/http/header_validator_errors.h"

#include "source/common/http/header_utility.h"

#include "source/common/http/headers.h"

#include "source/common/runtime/runtime_features.h"

#include "source/extensions/http/header_validators/envoy_default/character_tables.h"

#include "absl/strings/match.h"

namespace Envoy {

namespace Extensions {

namespace Http {

namespace HeaderValidators {

namespace EnvoyDefault {

using ::envoy::extensions::http::header_validators::envoy_default::v3::HeaderValidatorConfig;

using ::envoy::extensions::http::header_validators::envoy_default::v3::

    HeaderValidatorConfig_UriPathNormalizationOptions;

using ::Envoy::Http::HeaderUtility;

using ::Envoy::Http::PathNormalizerResponseCodeDetail;

using ::Envoy::Http::RequestHeaderMap;

using ::Envoy::Http::testCharInTable;

using ::Envoy::Http::UhvResponseCodeDetail;

PathNormalizer::PathNormalizer(const HeaderValidatorConfig& config,

                               const ConfigOverrides& config_overrides)

PathNormalizer::DecodedOctet

PathNormalizer::normalizeAndDecodeOctet(std::string::iterator iter,

  // From RFC 3986: https://datatracker.ietf.org/doc/html/rfc3986#section-2.1

  //

  // SPELLCHECKER(off)

  // pct-encoded = "%" HEXDIG HEXDIG

  //

  // The uppercase hexadecimal digits 'A' through 'F' are equivalent to

  // the lowercase digits 'a' through 'f', respectively. If two URIs

  // differ only in the case of hexadecimal digits used in percent-encoded

  // octets, they are equivalent. For consistency, URI producers and

  // normalizers should use uppercase hexadecimal digits for all percent-

  // encodings.

  //

  // Also from RFC 3986: https://datatracker.ietf.org/doc/html/rfc3986#section-2.4

  //

  // When a URI is dereferenced, the components and subcomponents significant

  // to the scheme-specific dereferencing process (if any) must be parsed and

  // separated before the percent-encoded octets within those components can

  // be safely decoded, as otherwise the data may be mistaken for component

  // delimiters. The only exception is for percent-encoded octets corresponding

  // to characters in the unreserved set, which can be decoded at any time.

  // SPELLCHECKER(on)

  // Normalize and decode the octet

    // normalize

    // decode

    // Based on RFC, only decode characters in the UNRESERVED set.

    // We decoded a slash character and how we handle it depends on the active configuration.

      // default implementation: normalize the encoded octet and accept the path

      // Reject the entire request

      // Decode the slash and accept the path.

      // Decode the slash and response with a redirect to the normalized path.

      // This should never occur but it's here to make the compiler happy because of the extra

      // values added by protobuf.

  // The octet is a valid encoding but it wasn't be decoded because it was outside the UNRESERVED

  // character set.

/*

 * Find the start of the previous segment within the path. The start of the previous segment is the

 * first non-slash character that directly follows a slash. For example:

 *

 *   path = "/hello/world/..";

 *           ^      ^    ^-- current argument

 *           |      |-- start of previous segment (return value)

 *           |-- begin argument

 *

 * Duplicate slashes that are encountered are ignored. For example:

 *

 * path = "/parent//child////..";

 *                  ^       ^-- current argument

 *                  |-- start of previous segment

 *

 * The ``current`` argument must point to a slash character. The ``begin`` iterator must be the

 * start of the path and it is returned on error.

 */

std::string::iterator findStartOfPreviousSegment(std::string::iterator current,

PathNormalizer::PathNormalizationResult

  // Parse and normalize the :path header and update it in the map. From RFC 9112,

  // https://www.rfc-editor.org/rfc/rfc9112.html#section-3.2:

  //

  // request-target = origin-form

  //                / absolute-form

  //                / authority-form

  //                / asterisk-form

  //

  // origin-form    = absolute-path [ "?" query ]

  // absolute-form  = absolute-URI

  // authority-form = uri-host ":" port

  // asterisk-form  = "*"

  //

  // TODO(#23887) - potentially separate path normalization into multiple independent operations.

    // asterisk-form, only valid for OPTIONS request

    // The :path can only be empty for standard CONNECT methods, where the request-target is in

    // authority-form for HTTP/1 requests, or :path is empty for HTTP/2 requests.

  // Split the path and the query parameters / fragment component.

  // Make a copy of the original path and then create a readonly string_view to it. The string_view

  // is used for optimized sub-strings and the path is modified in place.

  // Start normalizing the path.

  // Path normalization is based on RFC 3986:

  // https://datatracker.ietf.org/doc/html/rfc3986#section-3.3

  //

  // SPELLCHECKER(off)

  // path          = path-abempty    ; begins with "/" or is empty

  //               / path-absolute   ; begins with "/" but not "//"

  //               / path-noscheme   ; begins with a non-colon segment

  //               / path-rootless   ; begins with a segment

  //               / path-empty      ; zero characters

  //

  // path-abempty  = *( "/" segment )

  // path-absolute = "/" [ segment-nz *( "/" segment ) ]

  // path-noscheme = segment-nz-nc *( "/" segment )

  // path-rootless = segment-nz *( "/" segment )

  // path-empty    = 0<pchar>

  // segment       = *pchar

  // segment-nz    = 1*pchar

  // segment-nz-nc = 1*( unreserved / pct-encoded / sub-delims / "@" )

  //               ; non-zero-length segment without any colon ":"

  //

  // pchar         = unreserved / pct-encoded / sub-delims / ":" / "@"

  // SPELLCHECKER(on)

    // pass 1: normalize and decode percent-encoded octets

  // The `envoy.uhv.allow_non_compliant_characters_in_path` flag allows the \ (back slash)

  // character, which legacy path normalization was changing to / (forward slash).

    // pass 2: merge duplicate slashes (if configured to do so)

    // pass 3: collapse dot and dot-dot segments

  // Update the :path header. We need to honor the normalized path and the original query/fragment

  // components.

      // TODO(#23885) - add and honor config to not reject invalid percent-encoded octets.

          // Write the % character that starts invalid URL encoded sequence and then continue

          // scanning from the next character.

        // Reject the request

        // Valid encoding but outside the UNRESERVED character set. The encoding was normalized to

        // UPPERCASE and the octet must not be decoded. Copy the normalized encoding.

        // The encoding was properly decoded but, based on the config, the request should be

        // redirected to the normalized path.

        // The encoding was decoded. Store the decoded octet in the last character of the percent

        // encoding (read[2]) so it will be processed in the next iteration. We can safely advance

        // 2 positions since we know that the value was correctly decoded.

        // Duplicate slash, merge it

        // Not a duplicate slash

PathNormalizer::PathNormalizationResult

        // attempt to read ahead 2 characters to see if we are in a "./" or "../" segment.

          // This is a "/./" segment or the path is terminated by "/.", ignore it

          // Advance the read iterator by 1 if the path ends with "." or 2 if the segment is "./"

          // This is a "/../" segment or the path is terminated by "/..", navigate one segment up.

          // Back up write 1 position to the previous slash to find the previous segment start.

            // This is an invalid ".." segment, most likely the full path is "/..", which attempts

            // to go above the root.

          // Set the write position to overwrite the previous segment

          // Advance the read iterator by 2 if the path ends with ".." or 3 if the segment is "../"

std::tuple<absl::string_view, absl::string_view>

  // Split on the query (?) or fragment (#) delimiter, whichever one is first.

  // TODO(#23886) - add and honor config option for handling the path fragment component.

    // no query/fragment component

} // namespace EnvoyDefault

} // namespace HeaderValidators

} // namespace Http

} // namespace Extensions

} // namespace Envoy