text:
#include "guac_sftp.h"
#include "guac_ssh.h"

#include <guacamole/client.h>
#include <guacamole/object.h>
#include <guacamole/protocol.h>
#include <guacamole/socket.h>
#include <guacamole/user.h>
#include <libssh2.h>

#include <fcntl.h>
#include <libgen.h>
#include <stdlib.h>
#include <string.h>

/**
 * Translates the last error message received by the SFTP layer of an SSH
 * session into a Guacamole protocol status code.
 *
 * @param filesystem
 *     The object (not guac_object) defining the filesystem associated with the
 *     SFTP and SSH sessions.
 *
 * @return
 *     The Guacamole protocol status code corresponding to the last reported
 *     error of the SFTP layer, if nay, or GUAC_PROTOCOL_STATUS_SUCCESS if no
 *     error has occurred.
 */
static guac_protocol_status guac_sftp_get_status(
        guac_common_ssh_sftp_filesystem* filesystem) {

    /* Get libssh2 objects */
    LIBSSH2_SFTP*    sftp    = filesystem->sftp_session;
    LIBSSH2_SESSION* session = filesystem->ssh_session->session;

    /* Return success code if no error occurred */
    if (libssh2_session_last_errno(session) != LIBSSH2_ERROR_SFTP_PROTOCOL)
        return GUAC_PROTOCOL_STATUS_SUCCESS;

    /* Translate SFTP error codes defined by
     * https://tools.ietf.org/html/draft-ietf-secsh-filexfer-02 (the most
     * commonly-implemented standard) */
    switch (libssh2_sftp_last_error(sftp)) {

        /* SSH_FX_OK (not an error) */
        case 0:
            return GUAC_PROTOCOL_STATUS_SUCCESS;

        /* SSH_FX_EOF (technically not an error) */
        case 1:
            return GUAC_PROTOCOL_STATUS_SUCCESS;

        /* SSH_FX_NO_SUCH_FILE */
        case 2:
            return GUAC_PROTOCOL_STATUS_RESOURCE_NOT_FOUND;

        /* SSH_FX_PERMISSION_DENIED */
        case 3:
            return GUAC_PROTOCOL_STATUS_CLIENT_FORBIDDEN;

        /* SSH_FX_FAILURE */
        case 4:
            return GUAC_PROTOCOL_STATUS_UPSTREAM_ERROR;

        /* SSH_FX_BAD_MESSAGE */
        case 5:
            return GUAC_PROTOCOL_STATUS_SERVER_ERROR;

        /* SSH_FX_NO_CONNECTION / SSH_FX_CONNECTION_LOST */
        case 6:
        case 7:
            return GUAC_PROTOCOL_STATUS_UPSTREAM_TIMEOUT;

        /* SSH_FX_OP_UNSUPPORTED */
        case 8:
            return GUAC_PROTOCOL_STATUS_UNSUPPORTED;

        /* Return generic error if cause unknown */
        default:
            return GUAC_PROTOCOL_STATUS_UPSTREAM_ERROR;

    }

}

/**
 * Concatenates the given filename with the given path, separating the two
 * with a single forward slash. The full result must be no more than
 * GUAC_COMMON_SSH_SFTP_MAX_PATH bytes long, counting null terminator.
 *
 * @param fullpath
 *     The buffer to store the result within. This buffer must be at least
 *     GUAC_COMMON_SSH_SFTP_MAX_PATH bytes long.
 *
 * @param path
 *     The path to append the filename to.
 *
 * @param filename
 *     The filename to append to the path.
 *
 * @return
 *     Non-zero if the filename is valid and was successfully appended to the
 *     path, zero otherwise.
 */
static int guac_ssh_append_filename(char* fullpath, const char* path,
        const char* filename) {

    int i;

    /* Disallow "." as a filename */
    if (strcmp(filename, ".") == 0)
        return 0;

    /* Disallow ".." as a filename */
    if (strcmp(filename, "..") == 0)
        return 0;

    /* Copy path, append trailing slash */
    for (i=0; i<GUAC_COMMON_SSH_SFTP_MAX_PATH; i++) {

        /*
         * Append trailing slash only if:
         *  1) Trailing slash is not already present
         *  2) Path is non-empty
         */

        char c = path[i];
        if (c == '\0') {
            if (i > 0 && path[i-1] != '/')
                fullpath[i++] = '/';
            break;
        }

        /* Copy character if not end of string */
        fullpath[i] = c;

    }

    /* Append filename */
    for (; i<GUAC_COMMON_SSH_SFTP_MAX_PATH; i++) {

        char c = *(filename++);
        if (c == '\0')
            break;

        /* Filenames may not contain slashes */
        if (c == '\\' || c == '/')
            return 0;

        /* Append each character within filename */
        fullpath[i] = c;

    }

    /* Verify path length is within maximum */
    if (i == GUAC_COMMON_SSH_SFTP_MAX_PATH)
        return 0;

    /* Terminate path string */
    fullpath[i] = '\0';

    /* Append was successful */
    return 1;

}

/**
 * Handler for blob messages which continue an inbound SFTP data transfer
 * (upload). The data associated with the given stream is expected to be a
 * pointer to an open LIBSSH2_SFTP_HANDLE for the file to which the data
 * should be written.
 *
 * @param user
 *     The user receiving the blob message.
 *
 * @param stream
 *     The Guacamole protocol stream associated with the received blob message.
 *
 * @param data
 *     The data received within the blob.
 *
 * @param length
 *     The length of the received data, in bytes.
 *
 * @return
 *     Zero if the blob is handled successfully, or non-zero on error.
 */
static int guac_common_ssh_sftp_blob_handler(guac_user* user,
        guac_stream* stream, void* data, int length) {

    /* Pull file from stream */
    LIBSSH2_SFTP_HANDLE* file = (LIBSSH2_SFTP_HANDLE*) stream->data;

    /* Attempt write */
    if (libssh2_sftp_write(file, data, length) == length) {
        guac_user_log(user, GUAC_LOG_DEBUG, "%i bytes written", length);
        guac_protocol_send_ack(user->socket, stream, "SFTP: OK",
                GUAC_PROTOCOL_STATUS_SUCCESS);
        guac_socket_flush(user->socket);
    }

    /* Inform of any errors */
    else {
        guac_user_log(user, GUAC_LOG_INFO, "Unable to write to file");
        guac_protocol_send_ack(user->socket, stream, "SFTP: Write failed",
                GUAC_PROTOCOL_STATUS_SERVER_ERROR);
        guac_socket_flush(user->socket);
    }

    return 0;

}

/**
 * Handler for end messages which terminate an inbound SFTP data transfer
 * (upload). The data associated with the given stream is expected to be a
 * pointer to an open LIBSSH2_SFTP_HANDLE for the file to which the data
 * has been written and which should now be closed.
 *
 * @param user
 *     The user receiving the end message.
 *
 * @param stream
 *     The Guacamole protocol stream associated with the received end message.
 *
 * @return
 *     Zero if the file is closed successfully, or non-zero on error.
 */
static int guac_common_ssh_sftp_end_handler(guac_user* user,
        guac_stream* stream) {

    /* Pull file from stream */
    LIBSSH2_SFTP_HANDLE* file = (LIBSSH2_SFTP_HANDLE*) stream->data;

    /* Attempt to close file */
    if (libssh2_sftp_close(file) == 0) {
        guac_user_log(user, GUAC_LOG_DEBUG, "File closed");
        guac_protocol_send_ack(user->socket, stream, "SFTP: OK",
                GUAC_PROTOCOL_STATUS_SUCCESS);
        guac_socket_flush(user->socket);
    }
    else {
        guac_user_log(user, GUAC_LOG_INFO, "Unable to close file");
        guac_protocol_send_ack(user->socket, stream, "SFTP: Close failed",
                GUAC_PROTOCOL_STATUS_SERVER_ERROR);
        guac_socket_flush(user->socket);
    }

    return 0;

}

int guac_common_ssh_sftp_handle_file_stream(
        guac_common_ssh_sftp_filesystem* filesystem, guac_user* user,
        guac_stream* stream, char* mimetype, char* filename) {

    char fullpath[GUAC_COMMON_SSH_SFTP_MAX_PATH];
    LIBSSH2_SFTP_HANDLE* file;

    /* Concatenate filename with path */
    if (!guac_ssh_append_filename(fullpath, filesystem->upload_path,
                filename)) {

        guac_user_log(user, GUAC_LOG_DEBUG,
                "Filename \"%s\" is invalid or resulting path is too long",
                filename);

        /* Abort transfer - invalid filename */
        guac_protocol_send_ack(user->socket, stream,
                "SFTP: Illegal filename",
                GUAC_PROTOCOL_STATUS_CLIENT_BAD_REQUEST);

        guac_socket_flush(user->socket);
        return 0;
    }

    /* Open file via SFTP */
    file = libssh2_sftp_open(filesystem->sftp_session, fullpath,
            LIBSSH2_FXF_WRITE | LIBSSH2_FXF_CREAT | LIBSSH2_FXF_TRUNC,
            S_IRUSR | S_IWUSR);

    /* Inform of status */
    if (file != NULL) {

        guac_user_log(user, GUAC_LOG_DEBUG,
                "File \"%s\" opened",
                fullpath);

        guac_protocol_send_ack(user->socket, stream, "SFTP: File opened",
                GUAC_PROTOCOL_STATUS_SUCCESS);
        guac_socket_flush(user->socket);
    }
    else {
        guac_user_log(user, GUAC_LOG_INFO,
                "Unable to open file \"%s\"", fullpath);
        guac_protocol_send_ack(user->socket, stream, "SFTP: Open failed",
                guac_sftp_get_status(filesystem));
        guac_socket_flush(user->socket);
    }

    /* Set handlers for file stream */
    stream->blob_handler = guac_common_ssh_sftp_blob_handler;
    stream->end_handler = guac_common_ssh_sftp_end_handler;

    /* Store file within stream */
    stream->data = file;
    return 0;

}

/**
 * Handler for ack messages which continue an outbound SFTP data transfer
 * (download), signalling the current status and requesting additional data.
 * The data associated with the given stream is expected to be a pointer to an
 * open LIBSSH2_SFTP_HANDLE for the file from which the data is to be read.
 *
 * @param user
 *     The user receiving the ack message.
 *
 * @param stream
 *     The Guacamole protocol stream associated with the received ack message.
 *
 * @param message
 *     An arbitrary human-readable message describing the nature of the
 *     success or failure denoted by the ack message.
 *
 * @param status
 *     The status code associated with the ack message, which may indicate
 *     success or an error.
 *
 * @return
 *     Zero if the file is read from successfully, or non-zero on error.
 */
static int guac_common_ssh_sftp_ack_handler(guac_user* user,
        guac_stream* stream, char* message, guac_protocol_status status) {

    /* Pull file from stream */
    LIBSSH2_SFTP_HANDLE* file = (LIBSSH2_SFTP_HANDLE*) stream->data;

    /* If successful, read data */
    if (status == GUAC_PROTOCOL_STATUS_SUCCESS) {

        /* Attempt read into buffer */
        char buffer[4096];
        int bytes_read = libssh2_sftp_read(file, buffer, sizeof(buffer));

        /* If bytes read, send as blob */
        if (bytes_read > 0) {
            guac_protocol_send_blob(user->socket, stream,
                    buffer, bytes_read);

            guac_user_log(user, GUAC_LOG_DEBUG, "%i bytes sent to user",
                    bytes_read);

        }

        /* If EOF, send end */
        else if (bytes_read == 0) {
            guac_user_log(user, GUAC_LOG_DEBUG, "File sent");
            guac_protocol_send_end(user->socket, stream);
            guac_user_free_stream(user, stream);
        }

        /* Otherwise, fail stream */
        else {
            guac_user_log(user, GUAC_LOG_INFO, "Error reading file");
            guac_protocol_send_end(user->socket, stream);
            guac_user_free_stream(user, stream);
        }

        guac_socket_flush(user->socket);

    }

    /* Otherwise, return stream to user */
    else
        guac_user_free_stream(user, stream);

    return 0;
}

guac_stream* guac_common_ssh_sftp_download_file(
        guac_common_ssh_sftp_filesystem* filesystem, guac_user* user,
        char* filename) {

    guac_stream* stream;
    LIBSSH2_SFTP_HANDLE* file;

    /* Attempt to open file for reading */
    file = libssh2_sftp_open(filesystem->sftp_session, filename,
            LIBSSH2_FXF_READ, 0);
    if (file == NULL) {
        guac_user_log(user, GUAC_LOG_INFO,
                "Unable to read file \"%s\"", filename);
        return NULL;
    }

    /* Allocate stream */
    stream = guac_user_alloc_stream(user);
    stream->ack_handler = guac_common_ssh_sftp_ack_handler;
    stream->data = file;

    /* Send stream start, strip name */
    filename = basename(filename);
    guac_protocol_send_file(user->socket, stream,
            "application/octet-stream", filename);
    guac_socket_flush(user->socket);

    guac_user_log(user, GUAC_LOG_DEBUG, "Sending file \"%s\"", filename);
    return stream;

}

void guac_common_ssh_sftp_set_upload_path(
        guac_common_ssh_sftp_filesystem* filesystem, const char* path) {

    guac_client* client = filesystem->ssh_session->client;

    /* Ignore requests which exceed maximum-allowed path */
    int length = strnlen(path, GUAC_COMMON_SSH_SFTP_MAX_PATH)+1;
    if (length > GUAC_COMMON_SSH_SFTP_MAX_PATH) {
        guac_client_log(client, GUAC_LOG_ERROR,
                "Submitted path exceeds limit of %i bytes",
                GUAC_COMMON_SSH_SFTP_MAX_PATH);
        return;
    }

    /* Copy path */
    memcpy(filesystem->upload_path, path, length);
    guac_client_log(client, GUAC_LOG_DEBUG, "Upload path set to \"%s\"", path);

}

/**
 * Handler for ack messages received due to receipt of a "body" or "blob"
 * instruction associated with a SFTP directory list operation.
 *
 * @param user
 *     The user receiving the ack message.
 *
 * @param stream
 *     The Guacamole protocol stream associated with the received ack message.
 *
 * @param message
 *     An arbitrary human-readable message describing the nature of the
 *     success or failure denoted by this ack message.
 *
 * @param status
 *     The status code associated with this ack message, which may indicate
 *     success or an error.
 *
 * @return
 *     Zero on success, non-zero on error.
 */
static int guac_common_ssh_sftp_ls_ack_handler(guac_user* user,
        guac_stream* stream, char* message, guac_protocol_status status) {

    int bytes_read;
    int blob_written = 0;

    char filename[GUAC_COMMON_SSH_SFTP_MAX_PATH];
    LIBSSH2_SFTP_ATTRIBUTES attributes;

    guac_common_ssh_sftp_ls_state* list_state =
        (guac_common_ssh_sftp_ls_state*) stream->data;

    guac_common_ssh_sftp_filesystem* filesystem = list_state->filesystem;

    LIBSSH2_SFTP* sftp = filesystem->sftp_session;

    /* If unsuccessful, free stream and abort */
    if (status != GUAC_PROTOCOL_STATUS_SUCCESS) {
        libssh2_sftp_closedir(list_state->directory);
        guac_user_free_stream(user, stream);
        free(list_state);
        return 0;
    }

    /* While directory entries remain */
    while ((bytes_read = libssh2_sftp_readdir(list_state->directory,
                filename, sizeof(filename), &attributes)) > 0
            && !blob_written) {

        char absolute_path[GUAC_COMMON_SSH_SFTP_MAX_PATH];

        /* Skip current and parent directory entries */
        if (strcmp(filename, ".") == 0 || strcmp(filename, "..") == 0)
            continue;

        /* Concatenate into absolute path - skip if invalid */
        if (!guac_ssh_append_filename(absolute_path,
                    list_state->directory_name, filename)) {

            guac_user_log(user, GUAC_LOG_DEBUG,
                    "Skipping filename \"%s\" - filename is invalid or "
                    "resulting path is too long", filename);

            continue;
        }

        /* Stat explicitly if symbolic link (might point to directory) */
        if (LIBSSH2_SFTP_S_ISLNK(attributes.permissions))
            libssh2_sftp_stat(sftp, absolute_path, &attributes);

        /* Determine mimetype */
        const char* mimetype;
        if (LIBSSH2_SFTP_S_ISDIR(attributes.permissions))
            mimetype = GUAC_USER_STREAM_INDEX_MIMETYPE;
        else
            mimetype = "application/octet-stream";

        /* Write entry */
        blob_written |= guac_common_json_write_property(user, stream,
                &list_state->json_state, absolute_path, mimetype);

    }

    /* Complete JSON and cleanup at end of directory */
    if (bytes_read <= 0) {

        /* Complete JSON object */
        guac_common_json_end_object(user, stream, &list_state->json_state);
        guac_common_json_flush(user, stream, &list_state->json_state);

        /* Clean up resources */
        libssh2_sftp_closedir(list_state->directory);
        free(list_state);

        /* Signal of stream */
        guac_protocol_send_end(user->socket, stream);
        guac_user_free_stream(user, stream);

    }

    guac_socket_flush(user->socket);
    return 0;

}

/**
 * Handler for get messages. In context of SFTP and the filesystem exposed via
 * the Guacamole protocol, get messages request the body of a file within the
 * filesystem.
 *
 * @param user
 *     The user who sent the get message.
 *
 * @param object
 *     The Guacamole protocol object associated with the get request itself.
 *
 * @param name
 *     The name of the input stream (file) being requested.
 *
 * @return
 *     Zero on success, non-zero on error.
 */
static int guac_common_ssh_sftp_get_handler(guac_user* user,
        guac_object* object, char* name) {

    guac_common_ssh_sftp_filesystem* filesystem =
        (guac_common_ssh_sftp_filesystem*) object->data;

    LIBSSH2_SFTP* sftp = filesystem->sftp_session;
    LIBSSH2_SFTP_ATTRIBUTES attributes;

    /* Attempt to read file information */
    if (libssh2_sftp_stat(sftp, name, &attributes)) {
        guac_user_log(user, GUAC_LOG_INFO, "Unable to read file \"%s\"",
                name);
        return 0;
    }

    /* If directory, send contents of directory */
    if (LIBSSH2_SFTP_S_ISDIR(attributes.permissions)) {

        /* Open as directory */
        LIBSSH2_SFTP_HANDLE* dir = libssh2_sftp_opendir(sftp, name);
        if (dir == NULL) {
            guac_user_log(user, GUAC_LOG_INFO,
                    "Unable to read directory \"%s\"", name);
            return 0;
        }

        /* Init directory listing state */
        guac_common_ssh_sftp_ls_state* list_state =
            malloc(sizeof(guac_common_ssh_sftp_ls_state));

        list_state->directory = dir;
        list_state->filesystem = filesystem;
        strncpy(list_state->directory_name, name,
                sizeof(list_state->directory_name) - 1);

        /* Allocate stream for body */
        guac_stream* stream = guac_user_alloc_stream(user);
        stream->ack_handler = guac_common_ssh_sftp_ls_ack_handler;
        stream->data = list_state;

        /* Init JSON object state */
        guac_common_json_begin_object(user, stream, &list_state->json_state);

        /* Associate new stream with get request */
        guac_protocol_send_body(user->socket, object, stream,
                GUAC_USER_STREAM_INDEX_MIMETYPE, name);

    }

    /* Otherwise, send file contents */
    else {

        /* Open as normal file */
        LIBSSH2_SFTP_HANDLE* file = libssh2_sftp_open(sftp, name,
            LIBSSH2_FXF_READ, 0);
        if (file == NULL) {
            guac_user_log(user, GUAC_LOG_INFO,
                    "Unable to read file \"%s\"", name);
            return 0;
        }

        /* Allocate stream for body */
        guac_stream* stream = guac_user_alloc_stream(user);
        stream->ack_handler = guac_common_ssh_sftp_ack_handler;
        stream->data = file;

        /* Associate new stream with get request */
        guac_protocol_send_body(user->socket, object, stream,
                "application/octet-stream", name);

    }

    guac_socket_flush(user->socket);
    return 0;
}

/**
 * Handler for put messages. In context of SFTP and the filesystem exposed via
 * the Guacamole protocol, put messages request write access to a file within
 * the filesystem.
 *
 * @param user
 *     The user who sent the put message.
 *
 * @param object
 *     The Guacamole protocol object associated with the put request itself.
 *
 * @param stream
 *     The Guacamole protocol stream along which the user will be sending
 *     file data.
 *
 * @param mimetype
 *     The mimetype of the data being send along the stream.
 *
 * @param name
 *     The name of the input stream (file) being requested.
 *
 * @return
 *     Zero on success, non-zero on error.
 */
static int guac_common_ssh_sftp_put_handler(guac_user* user,
        guac_object* object, guac_stream* stream, char* mimetype, char* name) {

    guac_common_ssh_sftp_filesystem* filesystem =
        (guac_common_ssh_sftp_filesystem*) object->data;

    LIBSSH2_SFTP* sftp = filesystem->sftp_session;

    /* Open file via SFTP */
    LIBSSH2_SFTP_HANDLE* file = libssh2_sftp_open(sftp, name,
            LIBSSH2_FXF_WRITE | LIBSSH2_FXF_CREAT | LIBSSH2_FXF_TRUNC,
            S_IRUSR | S_IWUSR);

    /* Acknowledge stream if successful */
    if (file != NULL) {
        guac_user_log(user, GUAC_LOG_DEBUG, "File \"%s\" opened", name);
        guac_protocol_send_ack(user->socket, stream, "SFTP: File opened",
                GUAC_PROTOCOL_STATUS_SUCCESS);
    }

    /* Abort on failure */
    else {
        guac_user_log(user, GUAC_LOG_INFO,
                "Unable to open file \"%s\"", name);
        guac_protocol_send_ack(user->socket, stream, "SFTP: Open failed",
                guac_sftp_get_status(filesystem));
    }

    /* Set handlers for file stream */
    stream->blob_handler = guac_common_ssh_sftp_blob_handler;
    stream->end_handler = guac_common_ssh_sftp_end_handler;

    /* Store file within stream */
    stream->data = file;

    guac_socket_flush(user->socket);
    return 0;
}

void* guac_common_ssh_expose_sftp_filesystem(guac_user* user, void* data) {

    guac_common_ssh_sftp_filesystem* filesystem =
        (guac_common_ssh_sftp_filesystem*) data;

    /* No need to expose if there is no filesystem or the user has left */
    if (user == NULL || filesystem == NULL)
        return NULL;

    /* Allocate and expose filesystem object for user */
    return guac_common_ssh_alloc_sftp_filesystem_object(filesystem, user);

}

guac_object* guac_common_ssh_alloc_sftp_filesystem_object(
        guac_common_ssh_sftp_filesystem* filesystem, guac_user* user) {

    /* Init filesystem */
    guac_object* fs_object = guac_user_alloc_object(user);
    fs_object->get_handler = guac_common_ssh_sftp_get_handler;
    fs_object->put_handler = guac_common_ssh_sftp_put_handler;
    fs_object->data = filesystem;

    /* Send filesystem to user */
    guac_protocol_send_filesystem(user->socket, fs_object, filesystem->name);
    guac_socket_flush(user->socket);

    return fs_object;

}

guac_common_ssh_sftp_filesystem* guac_common_ssh_create_sftp_filesystem(
        guac_common_ssh_session* session, const char* name) {

    /* Request SFTP */
    LIBSSH2_SFTP* sftp_session = libssh2_sftp_init(session->session);
    if (sftp_session == NULL)
        return NULL;

    /* Allocate data for SFTP session */
    guac_common_ssh_sftp_filesystem* filesystem =
        malloc(sizeof(guac_common_ssh_sftp_filesystem));

    /* Associate SSH session with SFTP data and user */
    filesystem->name = strdup(name);
    filesystem->ssh_session = session;
    filesystem->sftp_session = sftp_session;

    /* Initially upload files to current directory */
    strcpy(filesystem->upload_path, ".");

    /* Return allocated filesystem */
    return filesystem;

}

void guac_common_ssh_destroy_sftp_filesystem(
        guac_common_ssh_sftp_filesystem* filesystem) {

    /* Shutdown SFTP session */
    libssh2_sftp_shutdown(filesystem->sftp_session);

    /* Free associated memory */
    free(filesystem->name);
    free(filesystem);

}


text:
class ImageOrVideo {
    bool isImage;
    ofImage image;
    ofVideoPlayer video;

public:
    bool load(const std::string& path);
    void update();
    void draw(float width, float height);
    int getWidth() const;
    int getHeight() const;
    void play();
};

class testApp : public ofBaseApp{
    ofxDome::ofxDome dome;
    ofxPanel gui;
    ofxButton panoramaButton, polarButton, cubeButton;

    ImageOrVideo images[5];

	public:
		void setup();
		void update();
		void draw();
        void drawGui(ofEventArgs& e);

        void onPanoramaButtonPressed();
        void onPolarButtonPressed();
        void onCubeButtonPressed();

		void keyPressed(int key);
		void mouseReleased(int x, int y, int button);
};

redpajama_set_name: RedPajamaGithub


text:
<!DOCTYPE html>

    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />
    <title>默认的 DLL 搜索路径优先级 — 码志</title>
    <link rel="stylesheet" href="/assets/vendor/primer-css/css/primer.css">
    <link rel="stylesheet" href="/assets/vendor/primer-markdown/dist/user-content.min.css">
    <link rel="stylesheet" href="/assets/vendor/octicons/octicons/octicons.css">
    <link rel="stylesheet" href="/assets/css/components/collection.css">
    <link rel="stylesheet" href="/assets/css/components/repo-card.css">
    <link rel="stylesheet" href="/assets/css/sections/repo-list.css">
    <link rel="stylesheet" href="/assets/css/sections/mini-repo-list.css">
    <link rel="stylesheet" href="/assets/css/components/boxed-group.css">
    <link rel="stylesheet" href="/assets/css/globals/common.css">
    <link rel="stylesheet" href="/assets/vendor/share.js/dist/css/share.min.css">
    <link rel="stylesheet" href="/assets/css/globals/responsive.css">
    <link rel="stylesheet" href="/assets/css/posts/index.css">

    <link rel="alternate" type="application/atom+xml" title="码志" href="/feed.xml">
    <link rel="shortcut icon" href="/favicon.ico">

    <meta property="og:title" content="默认的 DLL 搜索路径优先级">

    <meta name="keywords" content="Dll, Windows">
    <meta name="og:keywords" content="Dll, Windows">

    <meta name="description" content="结论">
    <meta name="og:description" content="结论">

    <meta property="og:url" content="https://mazhuang.org/2014/07/13/dllsearch/">
    <meta property="og:site_name" content="码志">
    <meta property="og:type" content="article">
    <meta property="og:locale" content="zh_CN" />

    <meta property="article:published_time" content="2014-07-13">

 码志

            <button class="collapsed mobile-visible" type="button" onclick="toggleMenu();">

            </button>

                首页

                分类

                维基

                链接

                关于

默认的 DLL 搜索路径优先级

             2014/07/13

            Windows

结论

在默认情况下,Windows 加载程序在用户磁盘上搜索 DLL 的搜索顺序:

包含可执行文件的目录。

Windows 的系统目录,该目录可以通过 GetSystemDirectory 得到,一般为 System32 目录,若为 32 位程序跑在 64 位系统下,则为 SysWOW64 目录。

16 位的系统目录,即 Windows 目录中的 System 目录。

Windows 目录,该目录可以通过 GetWindowsDirectory 得到。

进程的当前目录。

PATH 环境变量中所列出的目录。

如果调用 LoadLibrary 时传入的是绝对路径,那么加载程序将只尝试从该绝对路径搜索 DLL。

附注

以上结论在「Windows 核心编程」中列出,书中指出:

注意,对应用程序当前目录的搜索位于 Windows 目录之后,这个改变始于 Windows XP SP2,其目的是防止加载程序在应用程序的当前目录中找到伪造的系统 DLL 并将它们载入,从而保证系统 DLL 始终都是从它们在 Windows 目录的正式位置载入的。

我对这个说法持保留意见,因为在我的验证中,在一个 Windows XP SP1 的环境中已经应用了此搜索顺序。

另外,有一些其它方法可以改变加载程序的搜索顺序,已知的有:

SetDllDirectory 函数。如果传入一个有效路径,那么它将被插入在默认顺序的 1 与 2 之间。

HKEY_LOCAL_MACHINES\SYSTEM\CurrentControlSet\Control\Session Manager 下的 SafeDllSearchMode 键值。

调用 LoadLibraryEx 函数时使用 LOAD_WITH_ALTERED_SEARCH_PATH 等标志。

验证

证明代码片段:

#include <Windows.h>
#include <stdio.h>

BOOL WINAPI DllMain(HINSTANCE hinstDLL, DWORD fdwReason, LPVOID lpvReserved)
{
    switch (fdwReason)
    {
    case DLL_PROCESS_ATTACH:
        {
            char szPath[MAX_PATH] = {0};
            GetModuleFileName(hinstDLL, szPath, MAX_PATH);
            printf("lib.dll is in %s\n", szPath);
        }
        break;

    case DLL_THREAD_ATTACH:
        break;

    case DLL_THREAD_DETACH:
        break;

    case DLL_PROCESS_DETACH:
        break;
    }

    return (TRUE);
}

用如下命令行生成 lib.dll 文件:

gcc lib.c -shared -o lib.dll

加载 lib.dll 的程序:

#include <Windows.h>

int main()
{
    SetCurrentDirectory("D:\\test");
    HMODULE hDll = (HMODULE)LoadLibrary("lib.dll");
    if (hDll)
    {
        FreeLibrary(hDll);
    }

    return 0;
}

用如下命令行生成 test.exe 程序:

gcc test.c -o test.exe

测试方法:

在结论中提及的所有路径中各放置一份 lib.dll 文件。

运行 test.exe,可以看到控制台输出加载的 lib.dll 文件的路径。

把本次 test.exe 加载到的 lib.dll 文件删掉。

重复 2-3 步骤。

          Please enable JavaScript to view the comments powered by Disqus.

Search

    <input type="text" id="search_box" placeholder="Search">
    <button class="btn btn-default" id="site_search_do"></button>

<link rel="stylesheet" type="text/css" href="/assets/css/modules/sidebar-search.css">

Post Directory

                    © 2015
                    Zhuang Ma
                    TOP

                    TOP

                    首页

                    分类

                    维基

                    链接

                    关于

    <link rel="stylesheet" href="/assets/css/globals/prism.css">


text:
namespace re2 {

// Regular expression parse state.
// The list of parsed regexps so far is maintained as a vector of
// Regexp pointers called the stack.  Left parenthesis and vertical
// bar markers are also placed on the stack, as Regexps with
// non-standard opcodes.
// Scanning a left parenthesis causes the parser to push a left parenthesis
// marker on the stack.
// Scanning a vertical bar causes the parser to pop the stack until it finds a
// vertical bar or left parenthesis marker (not popping the marker),
// concatenate all the popped results, and push them back on
// the stack (DoConcatenation).
// Scanning a right parenthesis causes the parser to act as though it
// has seen a vertical bar, which then leaves the top of the stack in the
// form LeftParen regexp VerticalBar regexp VerticalBar ... regexp VerticalBar.
// The parser pops all this off the stack and creates an alternation of the
// regexps (DoAlternation).

class Regexp::ParseState {
 public:
  ParseState(ParseFlags flags, const StringPiece& whole_regexp,
             RegexpStatus* status);
  ~ParseState();

  ParseFlags flags() { return flags_; }
  int rune_max() { return rune_max_; }

  // Parse methods.  All public methods return a bool saying
  // whether parsing should continue.  If a method returns
  // false, it has set fields in *status_, and the parser
  // should return NULL.

  // Pushes the given regular expression onto the stack.
  // Could check for too much memory used here.
  bool PushRegexp(Regexp* re);

  // Pushes the literal rune r onto the stack.
  bool PushLiteral(Rune r);

  // Pushes a regexp with the given op (and no args) onto the stack.
  bool PushSimpleOp(RegexpOp op);

  // Pushes a ^ onto the stack.
  bool PushCarat();

  // Pushes a \b (word == true) or \B (word == false) onto the stack.
  bool PushWordBoundary(bool word);

  // Pushes a $ onto the stack.
  bool PushDollar();

  // Pushes a . onto the stack
  bool PushDot();

  // Pushes a repeat operator regexp onto the stack.
  // A valid argument for the operator must already be on the stack.
  // s is the name of the operator, for use in error messages.
  bool PushRepeatOp(RegexpOp op, const StringPiece& s, bool nongreedy);

  // Pushes a repetition regexp onto the stack.
  // A valid argument for the operator must already be on the stack.
  bool PushRepetition(int min, int max, const StringPiece& s, bool nongreedy);

  // Checks whether a particular regexp op is a marker.
  bool IsMarker(RegexpOp op);

  // Processes a left parenthesis in the input.
  // Pushes a marker onto the stack.
  bool DoLeftParen(const StringPiece& name);
  bool DoLeftParenNoCapture();

  // Processes a vertical bar in the input.
  bool DoVerticalBar();

  // Processes a right parenthesis in the input.
  bool DoRightParen();

  // Processes the end of input, returning the final regexp.
  Regexp* DoFinish();

  // Finishes the regexp if necessary, preparing it for use
  // in a more complicated expression.
  // If it is a CharClassBuilder, converts into a CharClass.
  Regexp* FinishRegexp(Regexp*);

  // These routines don't manipulate the parse stack
  // directly, but they do need to look at flags_.
  // ParseCharClass also manipulates the internals of Regexp
  // while creating *out_re.

  // Parse a character class into *out_re.
  // Removes parsed text from s.
  bool ParseCharClass(StringPiece* s, Regexp** out_re,
                      RegexpStatus* status);

  // Parse a character class character into *rp.
  // Removes parsed text from s.
  bool ParseCCCharacter(StringPiece* s, Rune *rp,
                        const StringPiece& whole_class,
                        RegexpStatus* status);

  // Parse a character class range into rr.
  // Removes parsed text from s.
  bool ParseCCRange(StringPiece* s, RuneRange* rr,
                    const StringPiece& whole_class,
                    RegexpStatus* status);

  // Parse a Perl flag set or non-capturing group from s.
  bool ParsePerlFlags(StringPiece* s);

  // Finishes the current concatenation,
  // collapsing it into a single regexp on the stack.
  void DoConcatenation();

  // Finishes the current alternation,
  // collapsing it to a single regexp on the stack.
  void DoAlternation();

  // Generalized DoAlternation/DoConcatenation.
  void DoCollapse(RegexpOp op);

  // Maybe concatenate Literals into LiteralString.
  bool MaybeConcatString(int r, ParseFlags flags);

private:
  ParseFlags flags_;
  StringPiece whole_regexp_;
  RegexpStatus* status_;
  Regexp* stacktop_;
  int ncap_;  // number of capturing parens seen
  int rune_max_;  // maximum char value for this encoding

  DISALLOW_COPY_AND_ASSIGN(ParseState);
};

// Pseudo-operators - only on parse stack.
const RegexpOp kLeftParen = static_cast<RegexpOp>(kMaxRegexpOp+1);
const RegexpOp kVerticalBar = static_cast<RegexpOp>(kMaxRegexpOp+2);

Regexp::ParseState::ParseState(ParseFlags flags,
                               const StringPiece& whole_regexp,
                               RegexpStatus* status)
  : flags_(flags), whole_regexp_(whole_regexp),
    status_(status), stacktop_(NULL), ncap_(0) {
  if (flags_ & Latin1)
    rune_max_ = 0xFF;
  else
    rune_max_ = Runemax;
}

// Cleans up by freeing all the regexps on the stack.
Regexp::ParseState::~ParseState() {
  Regexp* next;
  for (Regexp* re = stacktop_; re != NULL; re = next) {
    next = re->down_;
    re->down_ = NULL;
    if (re->op() == kLeftParen)
      delete re->name_;
    re->Decref();
  }
}

// Finishes the regexp if necessary, preparing it for use in
// a more complex expression.
// If it is a CharClassBuilder, converts into a CharClass.
Regexp* Regexp::ParseState::FinishRegexp(Regexp* re) {
  if (re == NULL)
    return NULL;
  re->down_ = NULL;

  if (re->op_ == kRegexpCharClass && re->ccb_ != NULL) {
    CharClassBuilder* ccb = re->ccb_;
    re->ccb_ = NULL;
    re->cc_ = ccb->GetCharClass();
    delete ccb;
  }

  return re;
}

// Pushes the given regular expression onto the stack.
// Could check for too much memory used here.
bool Regexp::ParseState::PushRegexp(Regexp* re) {
  MaybeConcatString(-1, NoParseFlags);

  // Special case: a character class of one character is just
  // a literal.  This is a common idiom for escaping
  // single characters (e.g., [.] instead of \.), and some
  // analysis does better with fewer character classes.
  // Similarly, [Aa] can be rewritten as a literal A with ASCII case folding.
  if (re->op_ == kRegexpCharClass) {
    if (re->ccb_->size() == 1) {
      Rune r = re->ccb_->begin()->lo;
      re->Decref();
      re = new Regexp(kRegexpLiteral, flags_);
      re->rune_ = r;
    } else if (re->ccb_->size() == 2) {
      Rune r = re->ccb_->begin()->lo;
      if ('A' <= r && r <= 'Z' && re->ccb_->Contains(r + 'a' - 'A')) {
        re->Decref();
        re = new Regexp(kRegexpLiteral, flags_ | FoldCase);
        re->rune_ = r + 'a' - 'A';
      }
    }
  }

  if (!IsMarker(re->op()))
    re->simple_ = re->ComputeSimple();
  re->down_ = stacktop_;
  stacktop_ = re;
  return true;
}

// Searches the case folding tables and returns the CaseFold* that contains r.
// If there isn't one, returns the CaseFold* with smallest f->lo bigger than r.
// If there isn't one, returns NULL.
const CaseFold* LookupCaseFold(const CaseFold *f, int n, Rune r) {
  const CaseFold* ef = f + n;

  // Binary search for entry containing r.
  while (n > 0) {
    int m = n/2;
    if (f[m].lo <= r && r <= f[m].hi)
      return &f[m];
    if (r < f[m].lo) {
      n = m;
    } else {
      f += m+1;
      n -= m+1;
    }
  }

  // There is no entry that contains r, but f points
  // where it would have been.  Unless f points at
  // the end of the array, it points at the next entry
  // after r.
  if (f < ef)
    return f;

  // No entry contains r; no entry contains runes > r.
  return NULL;
}

// Returns the result of applying the fold f to the rune r.
Rune ApplyFold(const CaseFold *f, Rune r) {
  switch (f->delta) {
    default:
      return r + f->delta;

    case EvenOddSkip:  // even <-> odd but only applies to every other
      if ((r - f->lo) % 2)
        return r;
      // fall through
    case EvenOdd:  // even <-> odd
      if (r%2 == 0)
        return r + 1;
      return r - 1;

    case OddEvenSkip:  // odd <-> even but only applies to every other
      if ((r - f->lo) % 2)
        return r;
      // fall through
    case OddEven:  // odd <-> even
      if (r%2 == 1)
        return r + 1;
      return r - 1;
  }
}

// Returns the next Rune in r's folding cycle (see unicode_casefold.h).
// Examples:
//   CycleFoldRune('A') = 'a'
//   CycleFoldRune('a') = 'A'
//
//   CycleFoldRune('K') = 'k'
//   CycleFoldRune('k') = 0x212A (Kelvin)
//   CycleFoldRune(0x212A) = 'K'
//
//   CycleFoldRune('?') = '?'
Rune CycleFoldRune(Rune r) {
  const CaseFold* f = LookupCaseFold(unicode_casefold, num_unicode_casefold, r);
  if (f == NULL || r < f->lo)
    return r;
  return ApplyFold(f, r);
}

// Add lo-hi to the class, along with their fold-equivalent characters.
// If lo-hi is already in the class, assume that the fold-equivalent
// chars are there too, so there's no work to do.
static void AddFoldedRange(CharClassBuilder* cc, Rune lo, Rune hi, int depth) {
  // AddFoldedRange calls itself recursively for each rune in the fold cycle.
  // Most folding cycles are small: there aren't any bigger than four in the
  // current Unicode tables.  make_unicode_casefold.py checks that
  // the cycles are not too long, and we double-check here using depth.
  if (depth > 10) {
    LOG(DFATAL) << "AddFoldedRange recurses too much.";
    return;
  }

  if (!cc->AddRange(lo, hi))  // lo-hi was already there? we're done
    return;

  while (lo <= hi) {
    const CaseFold* f = LookupCaseFold(unicode_casefold, num_unicode_casefold, lo);
    if (f == NULL)  // lo has no fold, nor does anything above lo
      break;
    if (lo < f->lo) {  // lo has no fold; next rune with a fold is f->lo
      lo = f->lo;
      continue;
    }

    // Add in the result of folding the range lo - f->hi
    // and that range's fold, recursively.
    Rune lo1 = lo;
    Rune hi1 = min<Rune>(hi, f->hi);
    switch (f->delta) {
      default:
        lo1 += f->delta;
        hi1 += f->delta;
        break;
      case EvenOdd:
        if (lo1%2 == 1)
          lo1--;
        if (hi1%2 == 0)
          hi1++;
        break;
      case OddEven:
        if (lo1%2 == 0)
          lo1--;
        if (hi1%2 == 1)
          hi1++;
        break;
    }
    AddFoldedRange(cc, lo1, hi1, depth+1);

    // Pick up where this fold left off.
    lo = f->hi + 1;
  }
}

// Pushes the literal rune r onto the stack.
bool Regexp::ParseState::PushLiteral(Rune r) {
  // Do case folding if needed.
  if ((flags_ & FoldCase) && CycleFoldRune(r) != r) {
    Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase);
    re->ccb_ = new CharClassBuilder;
    Rune r1 = r;
    do {
      if (!(flags_ & NeverNL) || r != '\n') {
        re->ccb_->AddRange(r, r);
      }
      r = CycleFoldRune(r);
    } while (r != r1);
    re->ccb_->RemoveAbove(rune_max_);
    return PushRegexp(re);
  }

  // Exclude newline if applicable.
  if ((flags_ & NeverNL) && r == '\n')
    return PushRegexp(new Regexp(kRegexpNoMatch, flags_));

  // No fancy stuff worked.  Ordinary literal.
  if (MaybeConcatString(r, flags_))
    return true;

  Regexp* re = new Regexp(kRegexpLiteral, flags_);
  re->rune_ = r;
  return PushRegexp(re);
}

// Pushes a ^ onto the stack.
bool Regexp::ParseState::PushCarat() {
  if (flags_ & OneLine) {
    return PushSimpleOp(kRegexpBeginText);
  }
  return PushSimpleOp(kRegexpBeginLine);
}

// Pushes a \b or \B onto the stack.
bool Regexp::ParseState::PushWordBoundary(bool word) {
  if (word)
    return PushSimpleOp(kRegexpWordBoundary);
  return PushSimpleOp(kRegexpNoWordBoundary);
}

// Pushes a $ onto the stack.
bool Regexp::ParseState::PushDollar() {
  if (flags_ & OneLine) {
    // Clumsy marker so that MimicsPCRE() can tell whether
    // this kRegexpEndText was a $ and not a \z.
    Regexp::ParseFlags oflags = flags_;
    flags_ = flags_ | WasDollar;
    bool ret = PushSimpleOp(kRegexpEndText);
    flags_ = oflags;
    return ret;
  }
  return PushSimpleOp(kRegexpEndLine);
}

// Pushes a . onto the stack.
bool Regexp::ParseState::PushDot() {
  if ((flags_ & DotNL) && !(flags_ & NeverNL))
    return PushSimpleOp(kRegexpAnyChar);
  // Rewrite . into [^\n]
  Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase);
  re->ccb_ = new CharClassBuilder;
  re->ccb_->AddRange(0, '\n' - 1);
  re->ccb_->AddRange('\n' + 1, rune_max_);
  return PushRegexp(re);
}

// Pushes a regexp with the given op (and no args) onto the stack.
bool Regexp::ParseState::PushSimpleOp(RegexpOp op) {
  Regexp* re = new Regexp(op, flags_);
  return PushRegexp(re);
}

// Pushes a repeat operator regexp onto the stack.
// A valid argument for the operator must already be on the stack.
// The char c is the name of the operator, for use in error messages.
bool Regexp::ParseState::PushRepeatOp(RegexpOp op, const StringPiece& s,
                                      bool nongreedy) {
  if (stacktop_ == NULL || IsMarker(stacktop_->op())) {
    status_->set_code(kRegexpRepeatArgument);
    status_->set_error_arg(s);
    return false;
  }
  Regexp::ParseFlags fl = flags_;
  if (nongreedy)
    fl = fl ^ NonGreedy;
  Regexp* re = new Regexp(op, fl);
  re->AllocSub(1);
  re->down_ = stacktop_->down_;
  re->sub()[0] = FinishRegexp(stacktop_);
  re->simple_ = re->ComputeSimple();
  stacktop_ = re;
  return true;
}

// Pushes a repetition regexp onto the stack.
// A valid argument for the operator must already be on the stack.
bool Regexp::ParseState::PushRepetition(int min, int max,
                                        const StringPiece& s,
                                        bool nongreedy) {
  if ((max != -1 && max < min) || min > 1000 || max > 1000) {
    status_->set_code(kRegexpRepeatSize);
    status_->set_error_arg(s);
    return false;
  }
  if (stacktop_ == NULL || IsMarker(stacktop_->op())) {
    status_->set_code(kRegexpRepeatArgument);
    status_->set_error_arg(s);
    return false;
  }
  Regexp::ParseFlags fl = flags_;
  if (nongreedy)
    fl = fl ^ NonGreedy;
  Regexp* re = new Regexp(kRegexpRepeat, fl);
  re->min_ = min;
  re->max_ = max;
  re->AllocSub(1);
  re->down_ = stacktop_->down_;
  re->sub()[0] = FinishRegexp(stacktop_);
  re->simple_ = re->ComputeSimple();

  stacktop_ = re;
  return true;
}

// Checks whether a particular regexp op is a marker.
bool Regexp::ParseState::IsMarker(RegexpOp op) {
  return op >= kLeftParen;
}

// Processes a left parenthesis in the input.
// Pushes a marker onto the stack.
bool Regexp::ParseState::DoLeftParen(const StringPiece& name) {
  Regexp* re = new Regexp(kLeftParen, flags_);
  re->cap_ = ++ncap_;
  if (name.data() != NULL)
    re->name_ = new string(name.as_string());
  return PushRegexp(re);
}

// Pushes a non-capturing marker onto the stack.
bool Regexp::ParseState::DoLeftParenNoCapture() {
  Regexp* re = new Regexp(kLeftParen, flags_);
  re->cap_ = -1;
  return PushRegexp(re);
}

// Adds r to cc, along with r's upper case if foldascii is set.
static void AddLiteral(CharClassBuilder* cc, Rune r, bool foldascii) {
  cc->AddRange(r, r);
  if (foldascii && 'a' <= r && r <= 'z')
    cc->AddRange(r + 'A' - 'a', r + 'A' - 'a');
}

// Processes a vertical bar in the input.
bool Regexp::ParseState::DoVerticalBar() {
  MaybeConcatString(-1, NoParseFlags);
  DoConcatenation();

  // Below the vertical bar is a list to alternate.
  // Above the vertical bar is a list to concatenate.
  // We just did the concatenation, so either swap
  // the result below the vertical bar or push a new
  // vertical bar on the stack.
  Regexp* r1;
  Regexp* r2;
  if ((r1 = stacktop_) != NULL &&
      (r2 = stacktop_->down_) != NULL &&
      r2->op() == kVerticalBar) {
    // If above and below vertical bar are literal or char class,
    // can merge into a single char class.
    Regexp* r3;
    if ((r1->op() == kRegexpLiteral ||
         r1->op() == kRegexpCharClass ||
         r1->op() == kRegexpAnyChar) &&
        (r3 = r2->down_) != NULL) {
      Rune rune;
      switch (r3->op()) {
        case kRegexpLiteral:  // convert to char class
          rune = r3->rune_;
          r3->op_ = kRegexpCharClass;
          r3->cc_ = NULL;
          r3->ccb_ = new CharClassBuilder;
          AddLiteral(r3->ccb_, rune, r3->parse_flags_ & Regexp::FoldCase);
          // fall through
        case kRegexpCharClass:
          if (r1->op() == kRegexpLiteral)
            AddLiteral(r3->ccb_, r1->rune_,
                       r1->parse_flags_ & Regexp::FoldCase);
          else if (r1->op() == kRegexpCharClass)
            r3->ccb_->AddCharClass(r1->ccb_);
          if (r1->op() == kRegexpAnyChar || r3->ccb_->full()) {
            delete r3->ccb_;
            r3->ccb_ = NULL;
            r3->op_ = kRegexpAnyChar;
          }
          // fall through
        case kRegexpAnyChar:
          // pop r1
          stacktop_ = r2;
          r1->Decref();
          return true;
        default:
          break;
      }
    }

    // Swap r1 below vertical bar (r2).
    r1->down_ = r2->down_;
    r2->down_ = r1;
    stacktop_ = r2;
    return true;
  }
  return PushSimpleOp(kVerticalBar);
}

// Processes a right parenthesis in the input.
bool Regexp::ParseState::DoRightParen() {
  // Finish the current concatenation and alternation.
  DoAlternation();

  // The stack should be: LeftParen regexp
  // Remove the LeftParen, leaving the regexp,
  // parenthesized.
  Regexp* r1;
  Regexp* r2;
  if ((r1 = stacktop_) == NULL ||
      (r2 = r1->down_) == NULL ||
      r2->op() != kLeftParen) {
    status_->set_code(kRegexpMissingParen);
    status_->set_error_arg(whole_regexp_);
    return false;
  }

  // Pop off r1, r2.  Will Decref or reuse below.
  stacktop_ = r2->down_;

  // Restore flags from when paren opened.
  Regexp* re = r2;
  flags_ = re->parse_flags();

  // Rewrite LeftParen as capture if needed.
  if (re->cap_ > 0) {
    re->op_ = kRegexpCapture;
    // re->cap_ is already set
    re->AllocSub(1);
    re->sub()[0] = FinishRegexp(r1);
    re->simple_ = re->ComputeSimple();
  } else {
    re->Decref();
    re = r1;
  }
  return PushRegexp(re);
}

// Processes the end of input, returning the final regexp.
Regexp* Regexp::ParseState::DoFinish() {
  DoAlternation();
  Regexp* re = stacktop_;
  if (re != NULL && re->down_ != NULL) {
    status_->set_code(kRegexpMissingParen);
    status_->set_error_arg(whole_regexp_);
    return NULL;
  }
  stacktop_ = NULL;
  return FinishRegexp(re);
}

// Returns the leading regexp that re starts with.
// The returned Regexp* points into a piece of re,
// so it must not be used after the caller calls re->Decref().
Regexp* Regexp::LeadingRegexp(Regexp* re) {
  if (re->op() == kRegexpEmptyMatch)
    return NULL;
  if (re->op() == kRegexpConcat && re->nsub() >= 2) {
    Regexp** sub = re->sub();
    if (sub[0]->op() == kRegexpEmptyMatch)
      return NULL;
    return sub[0];
  }
  return re;
}

// Removes LeadingRegexp(re) from re and returns what's left.
// Consumes the reference to re and may edit it in place.
// If caller wants to hold on to LeadingRegexp(re),
// must have already Incref'ed it.
Regexp* Regexp::RemoveLeadingRegexp(Regexp* re) {
  if (re->op() == kRegexpEmptyMatch)
    return re;
  if (re->op() == kRegexpConcat && re->nsub() >= 2) {
    Regexp** sub = re->sub();
    if (sub[0]->op() == kRegexpEmptyMatch)
      return re;
    sub[0]->Decref();
    sub[0] = NULL;
    if (re->nsub() == 2) {
      // Collapse concatenation to single regexp.
      Regexp* nre = sub[1];
      sub[1] = NULL;
      re->Decref();
      return nre;
    }
    // 3 or more -> 2 or more.
    re->nsub_--;
    memmove(sub, sub + 1, re->nsub_ * sizeof sub[0]);
    return re;
  }
  Regexp::ParseFlags pf = re->parse_flags();
  re->Decref();
  return new Regexp(kRegexpEmptyMatch, pf);
}

// Returns the leading string that re starts with.
// The returned Rune* points into a piece of re,
// so it must not be used after the caller calls re->Decref().
Rune* Regexp::LeadingString(Regexp* re, int *nrune,
                            Regexp::ParseFlags *flags) {
  while (re->op() == kRegexpConcat && re->nsub() > 0)
    re = re->sub()[0];

  *flags = static_cast<Regexp::ParseFlags>(re->parse_flags_ & Regexp::FoldCase);

  if (re->op() == kRegexpLiteral) {
    *nrune = 1;
    return &re->rune_;
  }

  if (re->op() == kRegexpLiteralString) {
    *nrune = re->nrunes_;
    return re->runes_;
  }

  *nrune = 0;
  return NULL;
}

// Removes the first n leading runes from the beginning of re.
// Edits re in place.
void Regexp::RemoveLeadingString(Regexp* re, int n) {
  // Chase down concats to find first string.
  // For regexps generated by parser, nested concats are
  // flattened except when doing so would overflow the 16-bit
  // limit on the size of a concatenation, so we should never
  // see more than two here.
  Regexp* stk[4];
  int d = 0;
  while (re->op() == kRegexpConcat) {
    if (d < arraysize(stk))
      stk[d++] = re;
    re = re->sub()[0];
  }

  // Remove leading string from re.
  if (re->op() == kRegexpLiteral) {
    re->rune_ = 0;
    re->op_ = kRegexpEmptyMatch;
  } else if (re->op() == kRegexpLiteralString) {
    if (n >= re->nrunes_) {
      delete[] re->runes_;
      re->runes_ = NULL;
      re->nrunes_ = 0;
      re->op_ = kRegexpEmptyMatch;
    } else if (n == re->nrunes_ - 1) {
      Rune rune = re->runes_[re->nrunes_ - 1];
      delete[] re->runes_;
      re->runes_ = NULL;
      re->nrunes_ = 0;
      re->rune_ = rune;
      re->op_ = kRegexpLiteral;
    } else {
      re->nrunes_ -= n;
      memmove(re->runes_, re->runes_ + n, re->nrunes_ * sizeof re->runes_[0]);
    }
  }

  // If re is now empty, concatenations might simplify too.
  while (d-- > 0) {
    re = stk[d];
    Regexp** sub = re->sub();
    if (sub[0]->op() == kRegexpEmptyMatch) {
      sub[0]->Decref();
      sub[0] = NULL;
      // Delete first element of concat.
      switch (re->nsub()) {
        case 0:
        case 1:
          // Impossible.
          LOG(DFATAL) << "Concat of " << re->nsub();
          re->submany_ = NULL;
          re->op_ = kRegexpEmptyMatch;
          break;

        case 2: {
          // Replace re with sub[1].
          Regexp* old = sub[1];
          sub[1] = NULL;
          re->Swap(old);
          old->Decref();
          break;
        }

        default:
          // Slide down.
          re->nsub_--;
          memmove(sub, sub + 1, re->nsub_ * sizeof sub[0]);
          break;
      }
    }
  }
}

// Factors common prefixes from alternation.
// For example,
//     ABC|ABD|AEF|BCX|BCY
// simplifies to
//     A(B(C|D)|EF)|BC(X|Y)
// which the normal parse state routines will further simplify to
//     A(B[CD]|EF)|BC[XY]
//
// Rewrites sub to contain simplified list to alternate and returns
// the new length of sub.  Adjusts reference counts accordingly
// (incoming sub[i] decremented, outgoing sub[i] incremented).

// It's too much of a pain to write this code with an explicit stack,
// so instead we let the caller specify a maximum depth and
// don't simplify beyond that.  There are around 15 words of local
// variables and parameters in the frame, so allowing 8 levels
// on a 64-bit machine is still less than a kilobyte of stack and
// probably enough benefit for practical uses.
const int kFactorAlternationMaxDepth = 8;

int Regexp::FactorAlternation(
    Regexp** sub, int n,
    Regexp::ParseFlags altflags) {
  return FactorAlternationRecursive(sub, n, altflags,
                                    kFactorAlternationMaxDepth);
}

int Regexp::FactorAlternationRecursive(
    Regexp** sub, int n,
    Regexp::ParseFlags altflags,
    int maxdepth) {

  if (maxdepth <= 0)
    return n;

  // Round 1: Factor out common literal prefixes.
  Rune *rune = NULL;
  int nrune = 0;
  Regexp::ParseFlags runeflags = Regexp::NoParseFlags;
  int start = 0;
  int out = 0;
  for (int i = 0; i <= n; i++) {
    // Invariant: what was in sub[0:start] has been Decref'ed
    // and that space has been reused for sub[0:out] (out <= start).
    //
    // Invariant: sub[start:i] consists of regexps that all begin
    // with the string rune[0:nrune].

    Rune* rune_i = NULL;
    int nrune_i = 0;
    Regexp::ParseFlags runeflags_i = Regexp::NoParseFlags;
    if (i < n) {
      rune_i = LeadingString(sub[i], &nrune_i, &runeflags_i);
      if (runeflags_i == runeflags) {
        int same = 0;
        while (same < nrune && same < nrune_i && rune[same] == rune_i[same])
          same++;
        if (same > 0) {
          // Matches at least one rune in current range.  Keep going around.
          nrune = same;
          continue;
        }
      }
    }

    // Found end of a run with common leading literal string:
    // sub[start:i] all begin with rune[0:nrune] but sub[i]
    // does not even begin with rune[0].
    //
    // Factor out common string and append factored expression to sub[0:out].
    if (i == start) {
      // Nothing to do - first iteration.
    } else if (i == start+1) {
      // Just one: don't bother factoring.
      sub[out++] = sub[start];
    } else {
      // Construct factored form: prefix(suffix1|suffix2|...)
      Regexp* x[2];  // x[0] = prefix, x[1] = suffix1|suffix2|...
      x[0] = LiteralString(rune, nrune, runeflags);
      for (int j = start; j < i; j++)
        RemoveLeadingString(sub[j], nrune);
      int nn = FactorAlternationRecursive(sub + start, i - start, altflags,
                                          maxdepth - 1);
      x[1] = AlternateNoFactor(sub + start, nn, altflags);
      sub[out++] = Concat(x, 2, altflags);
    }

    // Prepare for next round (if there is one).
    if (i < n) {
      start = i;
      rune = rune_i;
      nrune = nrune_i;
      runeflags = runeflags_i;
    }
  }
  n = out;

  // Round 2: Factor out common complex prefixes,
  // just the first piece of each concatenation,
  // whatever it is.  This is good enough a lot of the time.
  start = 0;
  out = 0;
  Regexp* first = NULL;
  for (int i = 0; i <= n; i++) {
    // Invariant: what was in sub[0:start] has been Decref'ed
    // and that space has been reused for sub[0:out] (out <= start).
    //
    // Invariant: sub[start:i] consists of regexps that all begin with first.

    Regexp* first_i = NULL;
    if (i < n) {
      first_i = LeadingRegexp(sub[i]);
      if (first != NULL && Regexp::Equal(first, first_i)) {
        continue;
      }
    }

    // Found end of a run with common leading regexp:
    // sub[start:i] all begin with first but sub[i] does not.
    //
    // Factor out common regexp and append factored expression to sub[0:out].
    if (i == start) {
      // Nothing to do - first iteration.
    } else if (i == start+1) {
      // Just one: don't bother factoring.
      sub[out++] = sub[start];
    } else {
      // Construct factored form: prefix(suffix1|suffix2|...)
      Regexp* x[2];  // x[0] = prefix, x[1] = suffix1|suffix2|...
      x[0] = first->Incref();
      for (int j = start; j < i; j++)
        sub[j] = RemoveLeadingRegexp(sub[j]);
      int nn = FactorAlternationRecursive(sub + start, i - start, altflags,
                                   maxdepth - 1);
      x[1] = AlternateNoFactor(sub + start, nn, altflags);
      sub[out++] = Concat(x, 2, altflags);
    }

    // Prepare for next round (if there is one).
    if (i < n) {
      start = i;
      first = first_i;
    }
  }
  n = out;

  // Round 3: Collapse runs of single literals into character classes.
  start = 0;
  out = 0;
  for (int i = 0; i <= n; i++) {
    // Invariant: what was in sub[0:start] has been Decref'ed
    // and that space has been reused for sub[0:out] (out <= start).
    //
    // Invariant: sub[start:i] consists of regexps that are either
    // literal runes or character classes.

    if (i < n &&
        (sub[i]->op() == kRegexpLiteral ||
         sub[i]->op() == kRegexpCharClass))
      continue;

    // sub[i] is not a char or char class;
    // emit char class for sub[start:i]...
    if (i == start) {
      // Nothing to do.
    } else if (i == start+1) {
      sub[out++] = sub[start];
    } else {
      // Make new char class.
      CharClassBuilder ccb;
      for (int j = start; j < i; j++) {
        Regexp* re = sub[j];
        if (re->op() == kRegexpCharClass) {
          CharClass* cc = re->cc();
          for (CharClass::iterator it = cc->begin(); it != cc->end(); ++it)
            ccb.AddRange(it->lo, it->hi);
        } else if (re->op() == kRegexpLiteral) {
          ccb.AddRangeFlags(re->rune(), re->rune(), re->parse_flags());
        } else {
          LOG(DFATAL) << "RE2: unexpected op: " << re->op() << " "
                      << re->ToString();
        }
        re->Decref();
      }
      sub[out++] = NewCharClass(ccb.GetCharClass(), altflags);
    }

    // ... and then emit sub[i].
    if (i < n)
      sub[out++] = sub[i];
    start = i+1;
  }
  n = out;

  // Round 4: Collapse runs of empty matches into single empty match.
  start = 0;
  out = 0;
  for (int i = 0; i < n; i++) {
    if (i + 1 < n &&
        sub[i]->op() == kRegexpEmptyMatch &&
        sub[i+1]->op() == kRegexpEmptyMatch) {
      sub[i]->Decref();
      continue;
    }
    sub[out++] = sub[i];
  }
  n = out;

  return n;
}

// Collapse the regexps on top of the stack, down to the
// first marker, into a new op node (op == kRegexpAlternate
// or op == kRegexpConcat).
void Regexp::ParseState::DoCollapse(RegexpOp op) {
  // Scan backward to marker, counting children of composite.
  int n = 0;
  Regexp* next = NULL;
  Regexp* sub;
  for (sub = stacktop_; sub != NULL && !IsMarker(sub->op()); sub = next) {
    next = sub->down_;
    if (sub->op_ == op)
      n += sub->nsub_;
    else
      n++;
  }

  // If there's just one child, leave it alone.
  // (Concat of one thing is that one thing; alternate of one thing is same.)
  if (stacktop_ != NULL && stacktop_->down_ == next)
    return;

  // Construct op (alternation or concatenation), flattening op of op.
  Regexp** subs = new Regexp*[n];
  next = NULL;
  int i = n;
  for (sub = stacktop_; sub != NULL && !IsMarker(sub->op()); sub = next) {
    next = sub->down_;
    if (sub->op_ == op) {
      Regexp** sub_subs = sub->sub();
      for (int k = sub->nsub_ - 1; k >= 0; k--)
        subs[--i] = sub_subs[k]->Incref();
      sub->Decref();
    } else {
      subs[--i] = FinishRegexp(sub);
    }
  }

  Regexp* re = ConcatOrAlternate(op, subs, n, flags_, true);
  delete[] subs;
  re->simple_ = re->ComputeSimple();
  re->down_ = next;
  stacktop_ = re;
}

// Finishes the current concatenation,
// collapsing it into a single regexp on the stack.
void Regexp::ParseState::DoConcatenation() {
  Regexp* r1 = stacktop_;
  if (r1 == NULL || IsMarker(r1->op())) {
    // empty concatenation is special case
    Regexp* re = new Regexp(kRegexpEmptyMatch, flags_);
    PushRegexp(re);
  }
  DoCollapse(kRegexpConcat);
}

// Finishes the current alternation,
// collapsing it to a single regexp on the stack.
void Regexp::ParseState::DoAlternation() {
  DoVerticalBar();
  // Now stack top is kVerticalBar.
  Regexp* r1 = stacktop_;
  stacktop_ = r1->down_;
  r1->Decref();
  DoCollapse(kRegexpAlternate);
}

// Incremental conversion of concatenated literals into strings.
// If top two elements on stack are both literal or string,
// collapse into single string.
// Don't walk down the stack -- the parser calls this frequently
// enough that below the bottom two is known to be collapsed.
// Only called when another regexp is about to be pushed
// on the stack, so that the topmost literal is not being considered.
// (Otherwise ab* would turn into (ab)*.)
// If r >= 0, consider pushing a literal r on the stack.
// Return whether that happened.
bool Regexp::ParseState::MaybeConcatString(int r, ParseFlags flags) {
  Regexp* re1;
  Regexp* re2;
  if ((re1 = stacktop_) == NULL || (re2 = re1->down_) == NULL)
    return false;

  if (re1->op_ != kRegexpLiteral && re1->op_ != kRegexpLiteralString)
    return false;
  if (re2->op_ != kRegexpLiteral && re2->op_ != kRegexpLiteralString)
    return false;
  if ((re1->parse_flags_ & FoldCase) != (re2->parse_flags_ & FoldCase))
    return false;

  if (re2->op_ == kRegexpLiteral) {
    // convert into string
    Rune rune = re2->rune_;
    re2->op_ = kRegexpLiteralString;
    re2->nrunes_ = 0;
    re2->runes_ = NULL;
    re2->AddRuneToString(rune);
  }

  // push re1 into re2.
  if (re1->op_ == kRegexpLiteral) {
    re2->AddRuneToString(re1->rune_);
  } else {
    for (int i = 0; i < re1->nrunes_; i++)
      re2->AddRuneToString(re1->runes_[i]);
    re1->nrunes_ = 0;
    delete[] re1->runes_;
    re1->runes_ = NULL;
  }

  // reuse re1 if possible
  if (r >= 0) {
    re1->op_ = kRegexpLiteral;
    re1->rune_ = r;
    re1->parse_flags_ = flags;
    return true;
  }

  stacktop_ = re2;
  re1->Decref();
  return false;
}

// Lexing routines.

// Parses a decimal integer, storing it in *n.
// Sets *s to span the remainder of the string.
// Sets *out_re to the regexp for the class.
static bool ParseInteger(StringPiece* s, int* np) {
  if (s->size() == 0 || !isdigit((*s)[0] & 0xFF))
    return false;
  // Disallow leading zeros.
  if (s->size() >= 2 && (*s)[0] == '0' && isdigit((*s)[1] & 0xFF))
    return false;
  int n = 0;
  int c;
  while (s->size() > 0 && isdigit(c = (*s)[0] & 0xFF)) {
    // Avoid overflow.
    if (n >= 100000000)
      return false;
    n = n*10 + c - '0';
    s->remove_prefix(1);  // digit
  }
  *np = n;
  return true;
}

// Parses a repetition suffix like {1,2} or {2} or {2,}.
// Sets *s to span the remainder of the string on success.
// Sets *lo and *hi to the given range.
// In the case of {2,}, the high number is unbounded;
// sets *hi to -1 to signify this.
// {,2} is NOT a valid suffix.
// The Maybe in the name signifies that the regexp parse
// doesn't fail even if ParseRepetition does, so the StringPiece
// s must NOT be edited unless MaybeParseRepetition returns true.
static bool MaybeParseRepetition(StringPiece* sp, int* lo, int* hi) {
  StringPiece s = *sp;
  if (s.size() == 0 || s[0] != '{')
    return false;
  s.remove_prefix(1);  // '{'
  if (!ParseInteger(&s, lo))
    return false;
  if (s.size() == 0)
    return false;
  if (s[0] == ',') {
    s.remove_prefix(1);  // ','
    if (s.size() == 0)
      return false;
    if (s[0] == '}') {
      // {2,} means at least 2
      *hi = -1;
    } else {
      // {2,4} means 2, 3, or 4.
      if (!ParseInteger(&s, hi))
        return false;
    }
  } else {
    // {2} means exactly two
    *hi = *lo;
  }
  if (s.size() == 0 || s[0] != '}')
    return false;
  s.remove_prefix(1);  // '}'
  *sp = s;
  return true;
}

// Removes the next Rune from the StringPiece and stores it in *r.
// Returns number of bytes removed from sp.
// Behaves as though there is a terminating NUL at the end of sp.
// Argument order is backwards from usual Google style
// but consistent with chartorune.
static int StringPieceToRune(Rune *r, StringPiece *sp, RegexpStatus* status) {
  int n;
  if (fullrune(sp->data(), sp->size())) {
    n = chartorune(r, sp->data());
    // Some copies of chartorune have a bug that accepts
    // encodings of values in (10FFFF, 1FFFFF] as valid.
    // Those values break the character class algorithm,
    // which assumes Runemax is the largest rune.
    if (*r > Runemax) {
      n = 1;
      *r = Runeerror;
    }
    if (!(n == 1 && *r == Runeerror)) {  // no decoding error
      sp->remove_prefix(n);
      return n;
    }
  }

  status->set_code(kRegexpBadUTF8);
  status->set_error_arg(NULL);
  return -1;
}

// Return whether name is valid UTF-8.
// If not, set status to kRegexpBadUTF8.
static bool IsValidUTF8(const StringPiece& s, RegexpStatus* status) {
  StringPiece t = s;
  Rune r;
  while (t.size() > 0) {
    if (StringPieceToRune(&r, &t, status) < 0)
      return false;
  }
  return true;
}

// Is c a hex digit?
static int IsHex(int c) {
  return ('0' <= c && c <= '9') ||
         ('A' <= c && c <= 'F') ||
         ('a' <= c && c <= 'f');
}

// Convert hex digit to value.
static int UnHex(int c) {
  if ('0' <= c && c <= '9')
    return c - '0';
  if ('A' <= c && c <= 'F')
    return c - 'A' + 10;
  if ('a' <= c && c <= 'f')
    return c - 'a' + 10;
  LOG(DFATAL) << "Bad hex digit " << c;
  return 0;
}

// Parse an escape sequence (e.g., \n, \{).
// Sets *s to span the remainder of the string.
// Sets *rp to the named character.
static bool ParseEscape(StringPiece* s, Rune* rp,
                        RegexpStatus* status, int rune_max) {
  const char* begin = s->begin();
  if (s->size() < 1 || (*s)[0] != '\\') {
    // Should not happen - caller always checks.
    status->set_code(kRegexpInternalError);
    status->set_error_arg(NULL);
    return false;
  }
  if (s->size() < 2) {
    status->set_code(kRegexpTrailingBackslash);
    status->set_error_arg(NULL);
    return false;
  }
  Rune c, c1;
  s->remove_prefix(1);  // backslash
  if (StringPieceToRune(&c, s, status) < 0)
    return false;
  int code;
  switch (c) {
    default:
      if (c < Runeself && !isalpha(c) && !isdigit(c)) {
        // Escaped non-word characters are always themselves.
        // PCRE is not quite so rigorous: it accepts things like
        // \q, but we don't.  We once rejected \_, but too many
        // programs and people insist on using it, so allow \_.
        *rp = c;
        return true;
      }
      goto BadEscape;

    // Octal escapes.
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
      // Single non-zero octal digit is a backreference; not supported.
      if (s->size() == 0 || (*s)[0] < '0' || (*s)[0] > '7')
        goto BadEscape;
      // fall through
    case '0':
      // consume up to three octal digits; already have one.
      code = c - '0';
      if (s->size() > 0 && '0' <= (c = (*s)[0]) && c <= '7') {
        code = code * 8 + c - '0';
        s->remove_prefix(1);  // digit
        if (s->size() > 0) {
          c = (*s)[0];
          if ('0' <= c && c <= '7') {
            code = code * 8 + c - '0';
            s->remove_prefix(1);  // digit
          }
        }
      }
      if (code > rune_max)
        goto BadEscape;
      *rp = code;
      return true;

    // Hexadecimal escapes
    case 'x':
      if (s->size() == 0)
        goto BadEscape;
      if (StringPieceToRune(&c, s, status) < 0)
        return false;
      if (c == '{') {
        // Any number of digits in braces.
        // Update n as we consume the string, so that
        // the whole thing gets shown in the error message.
        // Perl accepts any text at all; it ignores all text
        // after the first non-hex digit.  We require only hex digits,
        // and at least one.
        if (StringPieceToRune(&c, s, status) < 0)
          return false;
        int nhex = 0;
        code = 0;
        while (IsHex(c)) {
          nhex++;
          code = code * 16 + UnHex(c);
          if (code > rune_max)
            goto BadEscape;
          if (s->size() == 0)
            goto BadEscape;
          if (StringPieceToRune(&c, s, status) < 0)
            return false;
        }
        if (c != '}' || nhex == 0)
          goto BadEscape;
        *rp = code;
        return true;
      }
      // Easy case: two hex digits.
      if (s->size() == 0)
        goto BadEscape;
      if (StringPieceToRune(&c1, s, status) < 0)
        return false;
      if (!IsHex(c) || !IsHex(c1))
        goto BadEscape;
      *rp = UnHex(c) * 16 + UnHex(c1);
      return true;

    // C escapes.
    case 'n':
      *rp = '\n';
      return true;
    case 'r':
      *rp = '\r';
      return true;
    case 't':
      *rp = '\t';
      return true;

    // Less common C escapes.
    case 'a':
      *rp = '\a';
      return true;
    case 'f':
      *rp = '\f';
      return true;
    case 'v':
      *rp = '\v';
      return true;

    // This code is disabled to avoid misparsing
    // the Perl word-boundary \b as a backspace
    // when in POSIX regexp mode.  Surprisingly,
    // in Perl, \b means word-boundary but [\b]
    // means backspace.  We don't support that:
    // if you want a backspace embed a literal
    // backspace character or use \x08.
    //
    // case 'b':
    //   *rp = '\b';
    //   return true;
  }

  LOG(DFATAL) << "Not reached in ParseEscape.";

BadEscape:
  // Unrecognized escape sequence.
  status->set_code(kRegexpBadEscape);
  status->set_error_arg(StringPiece(begin, s->data() - begin));
  return false;
}

// Add a range to the character class, but exclude newline if asked.
// Also handle case folding.
void CharClassBuilder::AddRangeFlags(
    Rune lo, Rune hi, Regexp::ParseFlags parse_flags) {

  // Take out \n if the flags say so.
  bool cutnl = !(parse_flags & Regexp::ClassNL) ||
               (parse_flags & Regexp::NeverNL);
  if (cutnl && lo <= '\n' && '\n' <= hi) {
    if (lo < '\n')
      AddRangeFlags(lo, '\n' - 1, parse_flags);
    if (hi > '\n')
      AddRangeFlags('\n' + 1, hi, parse_flags);
    return;
  }

  // If folding case, add fold-equivalent characters too.
  if (parse_flags & Regexp::FoldCase)
    AddFoldedRange(this, lo, hi, 0);
  else
    AddRange(lo, hi);
}

// Look for a group with the given name.
static const UGroup* LookupGroup(const StringPiece& name,
                                 const UGroup *groups, int ngroups) {
  // Simple name lookup.
  for (int i = 0; i < ngroups; i++)
    if (StringPiece(groups[i].name) == name)
      return &groups[i];
  return NULL;
}

// Fake UGroup containing all Runes
static URange16 any16[] = { { 0, 65535 } };
static URange32 any32[] = { { 65536, Runemax } };
static UGroup anygroup = { "Any", +1, any16, 1, any32, 1 };

// Look for a POSIX group with the given name (e.g., "[:^alpha:]")
static const UGroup* LookupPosixGroup(const StringPiece& name) {
  return LookupGroup(name, posix_groups, num_posix_groups);
}

static const UGroup* LookupPerlGroup(const StringPiece& name) {
  return LookupGroup(name, perl_groups, num_perl_groups);
}

// Look for a Unicode group with the given name (e.g., "Han")
static const UGroup* LookupUnicodeGroup(const StringPiece& name) {
  // Special case: "Any" means any.
  if (name == StringPiece("Any"))
    return &anygroup;
  return LookupGroup(name, unicode_groups, num_unicode_groups);
}

// Add a UGroup or its negation to the character class.
static void AddUGroup(CharClassBuilder *cc, const UGroup *g, int sign,
                      Regexp::ParseFlags parse_flags) {
  if (sign == +1) {
    for (int i = 0; i < g->nr16; i++) {
      cc->AddRangeFlags(g->r16[i].lo, g->r16[i].hi, parse_flags);
    }
    for (int i = 0; i < g->nr32; i++) {
      cc->AddRangeFlags(g->r32[i].lo, g->r32[i].hi, parse_flags);
    }
  } else {
    if (parse_flags & Regexp::FoldCase) {
      // Normally adding a case-folded group means
      // adding all the extra fold-equivalent runes too.
      // But if we're adding the negation of the group,
      // we have to exclude all the runes that are fold-equivalent
      // to what's already missing.  Too hard, so do in two steps.
      CharClassBuilder ccb1;
      AddUGroup(&ccb1, g, +1, parse_flags);
      // If the flags say to take out \n, put it in, so that negating will take it out.
      // Normally AddRangeFlags does this, but we're bypassing AddRangeFlags.
      bool cutnl = !(parse_flags & Regexp::ClassNL) ||
                   (parse_flags & Regexp::NeverNL);
      if (cutnl) {
        ccb1.AddRange('\n', '\n');
      }
      ccb1.Negate();
      cc->AddCharClass(&ccb1);
      return;
    }
    int next = 0;
    for (int i = 0; i < g->nr16; i++) {
      if (next < g->r16[i].lo)
        cc->AddRangeFlags(next, g->r16[i].lo - 1, parse_flags);
      next = g->r16[i].hi + 1;
    }
    for (int i = 0; i < g->nr32; i++) {
      if (next < g->r32[i].lo)
        cc->AddRangeFlags(next, g->r32[i].lo - 1, parse_flags);
      next = g->r32[i].hi + 1;
    }
    if (next <= Runemax)
      cc->AddRangeFlags(next, Runemax, parse_flags);
  }
}

// Maybe parse a Perl character class escape sequence.
// Only recognizes the Perl character classes (\d \s \w \D \S \W),
// not the Perl empty-string classes (\b \B \A \Z \z).
// On success, sets *s to span the remainder of the string
// and returns the corresponding UGroup.
// The StringPiece must *NOT* be edited unless the call succeeds.
const UGroup* MaybeParsePerlCCEscape(StringPiece* s, Regexp::ParseFlags parse_flags) {
  if (!(parse_flags & Regexp::PerlClasses))
    return NULL;
  if (s->size() < 2 || (*s)[0] != '\\')
    return NULL;
  // Could use StringPieceToRune, but there aren't
  // any non-ASCII Perl group names.
  StringPiece name(s->begin(), 2);
  const UGroup *g = LookupPerlGroup(name);
  if (g == NULL)
    return NULL;
  s->remove_prefix(name.size());
  return g;
}

enum ParseStatus {
  kParseOk,  // Did some parsing.
  kParseError,  // Found an error.
  kParseNothing,  // Decided not to parse.
};

// Maybe parses a Unicode character group like \p{Han} or \P{Han}
// (the latter is a negated group).
ParseStatus ParseUnicodeGroup(StringPiece* s, Regexp::ParseFlags parse_flags,
                              CharClassBuilder *cc,
                              RegexpStatus* status) {
  // Decide whether to parse.
  if (!(parse_flags & Regexp::UnicodeGroups))
    return kParseNothing;
  if (s->size() < 2 || (*s)[0] != '\\')
    return kParseNothing;
  Rune c = (*s)[1];
  if (c != 'p' && c != 'P')
    return kParseNothing;

  // Committed to parse.  Results:
  int sign = +1;  // -1 = negated char class
  if (c == 'P')
    sign = -1;
  StringPiece seq = *s;  // \p{Han} or \pL
  StringPiece name;  // Han or L
  s->remove_prefix(2);  // '\\', 'p'

  if (!StringPieceToRune(&c, s, status))
    return kParseError;
  if (c != '{') {
    // Name is the bit of string we just skipped over for c.
    const char* p = seq.begin() + 2;
    name = StringPiece(p, s->begin() - p);
  } else {
    // Name is in braces. Look for closing }
    size_t end = s->find('}', 0);
    if (end == s->npos) {
      if (!IsValidUTF8(seq, status))
        return kParseError;
      status->set_code(kRegexpBadCharRange);
      status->set_error_arg(seq);
      return kParseError;
    }
    name = StringPiece(s->begin(), end);  // without '}'
    s->remove_prefix(end + 1);  // with '}'
    if (!IsValidUTF8(name, status))
      return kParseError;
  }

  // Chop seq where s now begins.
  seq = StringPiece(seq.begin(), s->begin() - seq.begin());

  // Look up group
  if (name.size() > 0 && name[0] == '^') {
    sign = -sign;
    name.remove_prefix(1);  // '^'
  }
  const UGroup *g = LookupUnicodeGroup(name);
  if (g == NULL) {
    status->set_code(kRegexpBadCharRange);
    status->set_error_arg(seq);
    return kParseError;
  }

  AddUGroup(cc, g, sign, parse_flags);
  return kParseOk;
}

// Parses a character class name like [:alnum:].
// Sets *s to span the remainder of the string.
// Adds the ranges corresponding to the class to ranges.
static ParseStatus ParseCCName(StringPiece* s, Regexp::ParseFlags parse_flags,
                               CharClassBuilder *cc,
                               RegexpStatus* status) {
  // Check begins with [:
  const char* p = s->data();
  const char* ep = s->data() + s->size();
  if (ep - p < 2 || p[0] != '[' || p[1] != ':')
    return kParseNothing;

  // Look for closing :].
  const char* q;
  for (q = p+2; q <= ep-2 && (*q != ':' || *(q+1) != ']'); q++)
    ;

  // If no closing :], then ignore.
  if (q > ep-2)
    return kParseNothing;

  // Got it.  Check that it's valid.
  q += 2;
  StringPiece name(p, q-p);

  const UGroup *g = LookupPosixGroup(name);
  if (g == NULL) {
    status->set_code(kRegexpBadCharRange);
    status->set_error_arg(name);
    return kParseError;
  }

  s->remove_prefix(name.size());
  AddUGroup(cc, g, g->sign, parse_flags);
  return kParseOk;
}

// Parses a character inside a character class.
// There are fewer special characters here than in the rest of the regexp.
// Sets *s to span the remainder of the string.
// Sets *rp to the character.
bool Regexp::ParseState::ParseCCCharacter(StringPiece* s, Rune *rp,
                                          const StringPiece& whole_class,
                                          RegexpStatus* status) {
  if (s->size() == 0) {
    status->set_code(kRegexpMissingBracket);
    status->set_error_arg(whole_class);
    return false;
  }

  // Allow regular escape sequences even though
  // many need not be escaped in this context.
  if (s->size() >= 1 && (*s)[0] == '\\')
    return ParseEscape(s, rp, status, rune_max_);

  // Otherwise take the next rune.
  return StringPieceToRune(rp, s, status) >= 0;
}

// Parses a character class character, or, if the character
// is followed by a hyphen, parses a character class range.
// For single characters, rr->lo == rr->hi.
// Sets *s to span the remainder of the string.
// Sets *rp to the character.
bool Regexp::ParseState::ParseCCRange(StringPiece* s, RuneRange* rr,
                                      const StringPiece& whole_class,
                                      RegexpStatus* status) {
  StringPiece os = *s;
  if (!ParseCCCharacter(s, &rr->lo, whole_class, status))
    return false;
  // [a-] means (a|-), so check for final ].
  if (s->size() >= 2 && (*s)[0] == '-' && (*s)[1] != ']') {
    s->remove_prefix(1);  // '-'
    if (!ParseCCCharacter(s, &rr->hi, whole_class, status))
      return false;
    if (rr->hi < rr->lo) {
      status->set_code(kRegexpBadCharRange);
      status->set_error_arg(StringPiece(os.data(), s->data() - os.data()));
      return false;
    }
  } else {
    rr->hi = rr->lo;
  }
  return true;
}

// Parses a possibly-negated character class expression like [^abx-z[:digit:]].
// Sets *s to span the remainder of the string.
// Sets *out_re to the regexp for the class.
bool Regexp::ParseState::ParseCharClass(StringPiece* s,
                                        Regexp** out_re,
                                        RegexpStatus* status) {
  StringPiece whole_class = *s;
  if (s->size() == 0 || (*s)[0] != '[') {
    // Caller checked this.
    status->set_code(kRegexpInternalError);
    status->set_error_arg(NULL);
    return false;
  }
  bool negated = false;
  Regexp* re = new Regexp(kRegexpCharClass, flags_ & ~FoldCase);
  re->ccb_ = new CharClassBuilder;
  s->remove_prefix(1);  // '['
  if (s->size() > 0 && (*s)[0] == '^') {
    s->remove_prefix(1);  // '^'
    negated = true;
    if (!(flags_ & ClassNL) || (flags_ & NeverNL)) {
      // If NL can't match implicitly, then pretend
      // negated classes include a leading \n.
      re->ccb_->AddRange('\n', '\n');
    }
  }
  bool first = true;  // ] is okay as first char in class
  while (s->size() > 0 && ((*s)[0] != ']' || first)) {
    // - is only okay unescaped as first or last in class.
    // Except that Perl allows - anywhere.
    if ((*s)[0] == '-' && !first && !(flags_&PerlX) &&
        (s->size() == 1 || (*s)[1] != ']')) {
      StringPiece t = *s;
      t.remove_prefix(1);  // '-'
      Rune r;
      int n = StringPieceToRune(&r, &t, status);
      if (n < 0) {
        re->Decref();
        return false;
      }
      status->set_code(kRegexpBadCharRange);
      status->set_error_arg(StringPiece(s->data(), 1+n));
      re->Decref();
      return false;
    }
    first = false;

    // Look for [:alnum:] etc.
    if (s->size() > 2 && (*s)[0] == '[' && (*s)[1] == ':') {
      switch (ParseCCName(s, flags_, re->ccb_, status)) {
        case kParseOk:
          continue;
        case kParseError:
          re->Decref();
          return false;
        case kParseNothing:
          break;
      }
    }

    // Look for Unicode character group like \p{Han}
    if (s->size() > 2 &&
        (*s)[0] == '\\' &&
        ((*s)[1] == 'p' || (*s)[1] == 'P')) {
      switch (ParseUnicodeGroup(s, flags_, re->ccb_, status)) {
        case kParseOk:
          continue;
        case kParseError:
          re->Decref();
          return false;
        case kParseNothing:
          break;
      }
    }

    // Look for Perl character class symbols (extension).
    const UGroup *g = MaybeParsePerlCCEscape(s, flags_);
    if (g != NULL) {
      AddUGroup(re->ccb_, g, g->sign, flags_);
      continue;
    }

    // Otherwise assume single character or simple range.
    RuneRange rr;
    if (!ParseCCRange(s, &rr, whole_class, status)) {
      re->Decref();
      return false;
    }
    // AddRangeFlags is usually called in response to a class like
    // \p{Foo} or [[:foo:]]; for those, it filters \n out unless
    // Regexp::ClassNL is set.  In an explicit range or singleton
    // like we just parsed, we do not filter \n out, so set ClassNL
    // in the flags.
    re->ccb_->AddRangeFlags(rr.lo, rr.hi, flags_ | Regexp::ClassNL);
  }
  if (s->size() == 0) {
    status->set_code(kRegexpMissingBracket);
    status->set_error_arg(whole_class);
    re->Decref();
    return false;
  }
  s->remove_prefix(1);  // ']'

  if (negated)
    re->ccb_->Negate();
  re->ccb_->RemoveAbove(rune_max_);

  *out_re = re;
  return true;
}

// Is this a valid capture name?  [A-Za-z0-9_]+
// PCRE limits names to 32 bytes.
// Python rejects names starting with digits.
// We don't enforce either of those.
static bool IsValidCaptureName(const StringPiece& name) {
  if (name.size() == 0)
    return false;
  for (int i = 0; i < name.size(); i++) {
    int c = name[i];
    if (('0' <= c && c <= '9') ||
        ('a' <= c && c <= 'z') ||
        ('A' <= c && c <= 'Z') ||
        c == '_')
      continue;
    return false;
  }
  return true;
}

// Parses a Perl flag setting or non-capturing group or both,
// like (?i) or (?: or (?i:.  Removes from s, updates parse state.
// The caller must check that s begins with "(?".
// Returns true on success.  If the Perl flag is not
// well-formed or not supported, sets status_ and returns false.
bool Regexp::ParseState::ParsePerlFlags(StringPiece* s) {
  StringPiece t = *s;

  // Caller is supposed to check this.
  if (!(flags_ & PerlX) || t.size() < 2 || t[0] != '(' || t[1] != '?') {
    LOG(DFATAL) << "Bad call to ParseState::ParsePerlFlags";
    status_->set_code(kRegexpInternalError);
    return false;
  }

  t.remove_prefix(2);  // "(?"

  // Check for named captures, first introduced in Python's regexp library.
  // As usual, there are three slightly different syntaxes:
  //
  //   (?P<name>expr)   the original, introduced by Python
  //   (?<name>expr)    the .NET alteration, adopted by Perl 5.10
  //   (?'name'expr)    another .NET alteration, adopted by Perl 5.10
  //
  // Perl 5.10 gave in and implemented the Python version too,
  // but they claim that the last two are the preferred forms.
  // PCRE and languages based on it (specifically, PHP and Ruby)
  // support all three as well.  EcmaScript 4 uses only the Python form.
  //
  // In both the open source world (via Code Search) and the
  // Google source tree, (?P<expr>name) is the dominant form,
  // so that's the one we implement.  One is enough.
  if (t.size() > 2 && t[0] == 'P' && t[1] == '<') {
    // Pull out name.
    size_t end = t.find('>', 2);
    if (end == t.npos) {
      if (!IsValidUTF8(*s, status_))
        return false;
      status_->set_code(kRegexpBadNamedCapture);
      status_->set_error_arg(*s);
      return false;
    }

    // t is "P<name>...", t[end] == '>'
    StringPiece capture(t.begin()-2, end+3);  // "(?P<name>"
    StringPiece name(t.begin()+2, end-2);     // "name"
    if (!IsValidUTF8(name, status_))
      return false;
    if (!IsValidCaptureName(name)) {
      status_->set_code(kRegexpBadNamedCapture);
      status_->set_error_arg(capture);
      return false;
    }

    if (!DoLeftParen(name)) {
      // DoLeftParen's failure set status_.
      return false;
    }

    s->remove_prefix(capture.end() - s->begin());
    return true;
  }

  bool negated = false;
  bool sawflags = false;
  int nflags = flags_;
  Rune c;
  for (bool done = false; !done; ) {
    if (t.size() == 0)
      goto BadPerlOp;
    if (StringPieceToRune(&c, &t, status_) < 0)
      return false;
    switch (c) {
      default:
        goto BadPerlOp;

      // Parse flags.
      case 'i':
        sawflags = true;
        if (negated)
          nflags &= ~FoldCase;
        else
          nflags |= FoldCase;
        break;

      case 'm':  // opposite of our OneLine
        sawflags = true;
        if (negated)
          nflags |= OneLine;
        else
          nflags &= ~OneLine;
        break;

      case 's':
        sawflags = true;
        if (negated)
          nflags &= ~DotNL;
        else
          nflags |= DotNL;
        break;

      case 'U':
        sawflags = true;
        if (negated)
          nflags &= ~NonGreedy;
        else
          nflags |= NonGreedy;
        break;

      // Negation
      case '-':
        if (negated)
          goto BadPerlOp;
        negated = true;
        sawflags = false;
        break;

      // Open new group.
      case ':':
        if (!DoLeftParenNoCapture()) {
          // DoLeftParenNoCapture's failure set status_.
          return false;
        }
        done = true;
        break;

      // Finish flags.
      case ')':
        done = true;
        break;
    }
  }

  if (negated && !sawflags)
    goto BadPerlOp;

  flags_ = static_cast<Regexp::ParseFlags>(nflags);
  *s = t;
  return true;

BadPerlOp:
  status_->set_code(kRegexpBadPerlOp);
  status_->set_error_arg(StringPiece(s->begin(), t.begin() - s->begin()));
  return false;
}

// Converts latin1 (assumed to be encoded as Latin1 bytes)
// into UTF8 encoding in string.
// Can't use EncodingUtils::EncodeLatin1AsUTF8 because it is
// deprecated and because it rejects code points 0x80-0x9F.
void ConvertLatin1ToUTF8(const StringPiece& latin1, string* utf) {
  char buf[UTFmax];

  utf->clear();
  for (int i = 0; i < latin1.size(); i++) {
    Rune r = latin1[i] & 0xFF;
    int n = runetochar(buf, &r);
    utf->append(buf, n);
  }
}

// Parses the regular expression given by s,
// returning the corresponding Regexp tree.
// The caller must Decref the return value when done with it.
// Returns NULL on error.
Regexp* Regexp::Parse(const StringPiece& s, ParseFlags global_flags,
                      RegexpStatus* status) {
  // Make status non-NULL (easier on everyone else).
  RegexpStatus xstatus;
  if (status == NULL)
    status = &xstatus;

  ParseState ps(global_flags, s, status);
  StringPiece t = s;

  // Convert regexp to UTF-8 (easier on the rest of the parser).
  if (global_flags & Latin1) {
    string* tmp = new string;
    ConvertLatin1ToUTF8(t, tmp);
    status->set_tmp(tmp);
    t = *tmp;
  }

  if (global_flags & Literal) {
    // Special parse loop for literal string.
    while (t.size() > 0) {
      Rune r;
      if (StringPieceToRune(&r, &t, status) < 0)
        return NULL;
      if (!ps.PushLiteral(r))
        return NULL;
    }
    return ps.DoFinish();
  }

  StringPiece lastunary = NULL;
  while (t.size() > 0) {
    StringPiece isunary = NULL;
    switch (t[0]) {
      default: {
        Rune r;
        if (StringPieceToRune(&r, &t, status) < 0)
          return NULL;
        if (!ps.PushLiteral(r))
          return NULL;
        break;
      }

      case '(':
        // "(?" introduces Perl escape.
        if ((ps.flags() & PerlX) && (t.size() >= 2 && t[1] == '?')) {
          // Flag changes and non-capturing groups.
          if (!ps.ParsePerlFlags(&t))
            return NULL;
          break;
        }
        if (ps.flags() & NeverCapture) {
          if (!ps.DoLeftParenNoCapture())
            return NULL;
        } else {
          if (!ps.DoLeftParen(NULL))
            return NULL;
        }
        t.remove_prefix(1);  // '('
        break;

      case '|':
        if (!ps.DoVerticalBar())
          return NULL;
        t.remove_prefix(1);  // '|'
        break;

      case ')':
        if (!ps.DoRightParen())
          return NULL;
        t.remove_prefix(1);  // ')'
        break;

      case '^':  // Beginning of line.
        if (!ps.PushCarat())
          return NULL;
        t.remove_prefix(1);  // '^'
        break;

      case '$':  // End of line.
        if (!ps.PushDollar())
          return NULL;
        t.remove_prefix(1);  // '$'
        break;

      case '.':  // Any character (possibly except newline).
        if (!ps.PushDot())
          return NULL;
        t.remove_prefix(1);  // '.'
        break;

      case '[': {  // Character class.
        Regexp* re;
        if (!ps.ParseCharClass(&t, &re, status))
          return NULL;
        if (!ps.PushRegexp(re))
          return NULL;
        break;
      }

      case '*': {  // Zero or more.
        RegexpOp op;
        op = kRegexpStar;
        goto Rep;
      case '+':  // One or more.
        op = kRegexpPlus;
        goto Rep;
      case '?':  // Zero or one.
        op = kRegexpQuest;
        goto Rep;
      Rep:
        StringPiece opstr = t;
        bool nongreedy = false;
        t.remove_prefix(1);  // '*' or '+' or '?'
        if (ps.flags() & PerlX) {
          if (t.size() > 0 && t[0] == '?') {
            nongreedy = true;
            t.remove_prefix(1);  // '?'
          }
          if (lastunary.size() > 0) {
            // In Perl it is not allowed to stack repetition operators:
            //   a** is a syntax error, not a double-star.
            // (and a++ means something else entirely, which we don't support!)
            status->set_code(kRegexpRepeatOp);
            status->set_error_arg(StringPiece(lastunary.begin(),
                                              t.begin() - lastunary.begin()));
            return NULL;
          }
        }
        opstr.set(opstr.data(), t.data() - opstr.data());
        if (!ps.PushRepeatOp(op, opstr, nongreedy))
          return NULL;
        isunary = opstr;
        break;
      }

      case '{': {  // Counted repetition.
        int lo, hi;
        StringPiece opstr = t;
        if (!MaybeParseRepetition(&t, &lo, &hi)) {
          // Treat like a literal.
          if (!ps.PushLiteral('{'))
            return NULL;
          t.remove_prefix(1);  // '{'
          break;
        }
        bool nongreedy = false;
        if (ps.flags() & PerlX) {
          if (t.size() > 0 && t[0] == '?') {
            nongreedy = true;
            t.remove_prefix(1);  // '?'
          }
          if (lastunary.size() > 0) {
            // Not allowed to stack repetition operators.
            status->set_code(kRegexpRepeatOp);
            status->set_error_arg(StringPiece(lastunary.begin(),
                                              t.begin() - lastunary.begin()));
            return NULL;
          }
        }
        opstr.set(opstr.data(), t.data() - opstr.data());
        if (!ps.PushRepetition(lo, hi, opstr, nongreedy))
          return NULL;
        isunary = opstr;
        break;
      }

      case '\\': {  // Escaped character or Perl sequence.
        // \b and \B: word boundary or not
        if ((ps.flags() & Regexp::PerlB) &&
            t.size() >= 2 && (t[1] == 'b' || t[1] == 'B')) {
          if (!ps.PushWordBoundary(t[1] == 'b'))
            return NULL;
          t.remove_prefix(2);  // '\\', 'b'
          break;
        }

        if ((ps.flags() & Regexp::PerlX) && t.size() >= 2) {
          if (t[1] == 'A') {
            if (!ps.PushSimpleOp(kRegexpBeginText))
              return NULL;
            t.remove_prefix(2);  // '\\', 'A'
            break;
          }
          if (t[1] == 'z') {
            if (!ps.PushSimpleOp(kRegexpEndText))
              return NULL;
            t.remove_prefix(2);  // '\\', 'z'
            break;
          }
          // Do not recognize \Z, because this library can't
          // implement the exact Perl/PCRE semantics.
          // (This library treats "(?-m)$" as \z, even though
          // in Perl and PCRE it is equivalent to \Z.)

          if (t[1] == 'C') {  // \C: any byte [sic]
            if (!ps.PushSimpleOp(kRegexpAnyByte))
              return NULL;
            t.remove_prefix(2);  // '\\', 'C'
            break;
          }

          if (t[1] == 'Q') {  // \Q ... \E: the ... is always literals
            t.remove_prefix(2);  // '\\', 'Q'
            while (t.size() > 0) {
              if (t.size() >= 2 && t[0] == '\\' && t[1] == 'E') {
                t.remove_prefix(2);  // '\\', 'E'
                break;
              }
              Rune r;
              if (StringPieceToRune(&r, &t, status) < 0)
                return NULL;
              if (!ps.PushLiteral(r))
                return NULL;
            }
            break;
          }
        }

        if (t.size() >= 2 && (t[1] == 'p' || t[1] == 'P')) {
          Regexp* re = new Regexp(kRegexpCharClass, ps.flags() & ~FoldCase);
          re->ccb_ = new CharClassBuilder;
          switch (ParseUnicodeGroup(&t, ps.flags(), re->ccb_, status)) {
            case kParseOk:
              if (!ps.PushRegexp(re))
                return NULL;
              goto Break2;
            case kParseError:
              re->Decref();
              return NULL;
            case kParseNothing:
              re->Decref();
              break;
          }
        }

        const UGroup *g = MaybeParsePerlCCEscape(&t, ps.flags());
        if (g != NULL) {
          Regexp* re = new Regexp(kRegexpCharClass, ps.flags() & ~FoldCase);
          re->ccb_ = new CharClassBuilder;
          AddUGroup(re->ccb_, g, g->sign, ps.flags());
          if (!ps.PushRegexp(re))
            return NULL;
          break;
        }

        Rune r;
        if (!ParseEscape(&t, &r, status, ps.rune_max()))
          return NULL;
        if (!ps.PushLiteral(r))
          return NULL;
        break;
      }
    }
  Break2:
    lastunary = isunary;
  }
  return ps.DoFinish();
}

}  // namespace re2


text:
typedef void (^FBSDKURLSessionTaskBlock)(NSError *error,
                                         NSURLResponse *response,
                                         NSData *responseData)
NS_SWIFT_NAME(URLSessionTaskBlock);

NS_SWIFT_NAME(URLSessionTask)
@interface FBSDKURLSessionTask : NSObject

- (instancetype)init NS_UNAVAILABLE;
+ (instancetype)new NS_UNAVAILABLE;

- (instancetype)initWithRequest:(NSURLRequest *)request
                    fromSession:(NSURLSession *)session
              completionHandler:(FBSDKURLSessionTaskBlock)handler
NS_DESIGNATED_INITIALIZER;

- (void)cancel;
- (void)start;

@end


text:
from __future__ import absolute_import
import re
import copy
import xml.etree.ElementTree as ET

from svtplay_dl.utils.urllib import urlparse
from svtplay_dl.service import Service
from svtplay_dl.utils import is_py2_old
from svtplay_dl.log import log
from svtplay_dl.fetcher.rtmp import RTMP
from svtplay_dl.error import ServiceError

class Hbo(Service):
    supported_domains = ['hbo.com']

    def get(self):
        parse = urlparse(self.url)
        try:
            other = parse.fragment
        except KeyError:
            log.error("Something wrong with that url")
            return

        if self.exclude():
            yield ServiceError("Excluding video")
            return

        match = re.search("^/(.*).html", other)
        if not match:
            log.error("Cant find video file")
            return
        url = "http://www.hbo.com/data/content/%s.xml" % match.group(1)
        data = self.http.request("get", url).content
        xml = ET.XML(data)
        videoid = xml.find("content")[1].find("videoId").text
        url = "http://render.cdn.hbo.com/data/content/global/videos/data/%s.xml" % videoid
        data = self.http.request("get", url).content
        xml = ET.XML(data)
        ss = xml.find("videos")
        if is_py2_old:
            sa = list(ss.getiterator("size"))
        else:
            sa = list(ss.iter("size"))

        for i in sa:
            videourl = i.find("tv14").find("path").text
            match = re.search("/([a-z0-9]+:[a-z0-9]+)/", videourl)
            self.options.other = "-y %s" % videourl[videourl.index(match.group(1)):]
            yield RTMP(copy.copy(self.options), videourl[:videourl.index(match.group(1))], i.attrib["width"])