/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
 * Use is subject to license terms.
 *
 * Copyright 2019 RackTop Systems.
 */

/*
 *      implicit.c
 *
 *      Handle suffix and percent rules
 */

/*
 * Included files
 */
#include <mk/defs.h>
#include <mksh/macro.h>         /* expand_value() */
#include <mksh/misc.h>          /* retmem() */
#include <libintl.h>

/*
 * Defined macros
 */

/*
 * typedefs & structs
 */

/*
 * Static variables
 */
static  wchar_t         WIDE_NULL[1] = {(wchar_t) nul_char};

/*
 * File table of contents
 */
extern  Doname          find_suffix_rule(Name target, Name target_body, Name target_suffix, Property *command, Boolean rechecking);
extern  Doname          find_ar_suffix_rule(Name target, Name true_target, Property *command, Boolean rechecking);
extern  Doname          find_double_suffix_rule(Name target, Property *command, Boolean rechecking);
extern  void            build_suffix_list(Name target_suffix);
extern  Doname          find_percent_rule(Name target, Property *command, Boolean rechecking);
static  void            create_target_group_and_dependencies_list(Name target, Percent pat_rule, String percent);
static  Boolean         match_found_with_pattern(Name target, Percent pat_rule, String percent, wchar_t *percent_buf);
static  void            construct_string_from_pattern(Percent pat_rule, String percent, String result);
static  Boolean         dependency_exists(Name target, Property line);
extern  Property        maybe_append_prop(Name, Property_id);
extern  void            add_target_to_chain(Name target, Chain * query);

/*
 *      find_suffix_rule(target, target_body, target_suffix, command, rechecking)
 *
 *      Does the lookup for single and double suffix rules.
 *      It calls build_suffix_list() to build the list of possible suffixes
 *      for the given target.
 *      It then scans the list to find the first possible source file that
 *      exists. This is done by concatenating the body of the target name
 *      (target name less target suffix) and the source suffix and checking
 *      if the resulting file exists.
 *
 *      Return value:
 *                              Indicates if search failed or not
 *
 *      Parameters:
 *              target          The target we need a rule for
 *              target_body     The target name without the suffix
 *              target_suffix   The suffix of the target
 *              command         Pointer to slot to deposit cmd in if found
 *              rechecking      true if we are rechecking target which depends
 *                              on conditional macro and keep_state is set
 *
 *      Global variables used:
 *              debug_level     Indicates how much tracing to do
 *              recursion_level Used for tracing
 */

static Boolean actual_doname = false;

/* /tolik/
 * fix bug 1247448: Suffix Rules failed when combine with Pattern Matching Rules.
 * When make attemps to apply % rule it didn't look for a single suffix rule because
 * if "doname" is called from "find_percent_rule" argument "implicit" is set to true
 * and find_suffix_rule was not called. I've commented the checking of "implicit"
 * in "doname" and make got infinite recursion for SVR4 tilde rules.
 * Usage of "we_are_in_tilde" is intended to avoid this recursion.
 */

static Boolean we_are_in_tilde = false;

Doname
find_suffix_rule(Name target, Name target_body, Name target_suffix, Property *command, Boolean rechecking)
{
        static wchar_t          static_string_buf_3M [ 3 * MAXPATHLEN ];
        Name                    true_target = target;
        wchar_t                 *sourcename = (wchar_t*)static_string_buf_3M;
        wchar_t *put_suffix;
        Property        source_suffix;
        Name            source;
        Doname                  result;
        Property        line;
        extern Boolean          tilde_rule;
        Boolean                 name_found = true;
        Boolean                 posix_tilde_attempt = true;
        int                     src_len = MAXPATHLEN + strlen(target_body->string_mb);

        /*
         * To avoid infinite recursion
         */
        if(we_are_in_tilde) {
                we_are_in_tilde = false;
                return(build_dont_know);
        }

        /*
         * If the target is a constructed one for a "::" target,
         * we need to consider that.
         */
        if (target->has_target_prop) {
                true_target = get_prop(target->prop,
                                       target_prop)->body.target.target;
        }
        if (debug_level > 1) {
                (void) printf("%*sfind_suffix_rule(%s,%s,%s)\n",
                              recursion_level,
                              "",
                              true_target->string_mb,
                              target_body->string_mb,
                              target_suffix->string_mb);
        }
        if (command != NULL) {
                if ((true_target->suffix_scan_done == true) && (*command == NULL)) {
                        return build_ok;
                }
        }
        true_target->suffix_scan_done = true;
        /*
         * Enter all names from the directory where the target lives as
         * files that makes sense.
         * This will make finding the synthesized source possible.
         */
        read_directory_of_file(target_body);
        /* Cache the suffixes for this target suffix if not done. */
        if (!target_suffix->has_read_suffixes) {
                build_suffix_list(target_suffix);
        }
        /* Preload the sourcename vector with the head of the target name. */
        if (src_len >= sizeof(static_string_buf_3M)) {
                sourcename = ALLOC_WC(src_len);
        }
        (void) mbstowcs(sourcename,
                      target_body->string_mb,
                      (int) target_body->hash.length);
        put_suffix = sourcename + target_body->hash.length;
        /* Scan the suffix list for the target if one exists. */
        if (target_suffix->has_suffixes) {
posix_attempts:
                for (source_suffix = get_prop(target_suffix->prop,
                                              suffix_prop);
                     source_suffix != NULL;
                     source_suffix = get_prop(source_suffix->next,
                                              suffix_prop)) {
                        /* Build the synthesized source name. */
                        (void) mbstowcs(put_suffix,
                                      source_suffix->body.
                                      suffix.suffix->string_mb,
                                      (int) source_suffix->body.
                                      suffix.suffix->hash.length);
                        put_suffix[source_suffix->body.
                                   suffix.suffix->hash.length] =
                          (int) nul_char;
                        if (debug_level > 1) {
                                WCSTOMBS(mbs_buffer, sourcename);
                                (void) printf(gettext("%*sTrying %s\n"),
                                              recursion_level,
                                              "",
                                              mbs_buffer);
                        }
                        source = getname_fn(sourcename, FIND_LENGTH, false, &name_found);
                        /*
                         * If the source file is not registered as
                         * a file, this source suffix did not match.
                         */
                        if(vpath_defined && !posix && !svr4) {
                                (void) exists(source);
                        }
                        if (!source->stat.is_file) {
                           if(!(posix|svr4))
                           {
                                if(!name_found) {
                                        free_name(source);
                                }
                                continue;
                           }

                           /* following code will ensure that the corresponding
                           ** tilde rules are executed when corresponding s. file
                           ** exists in the current directory. Though the current
                           ** target ends with a ~ character, there wont be any
                           ** any file in the current directory with that suffix
                           ** as it's fictitious. Even if it exists, it'll
                           ** execute all the rules for the ~ target.
                           */

                           if(source->string_mb[source->hash.length - 1] == '~' &&
                              ( svr4 || posix_tilde_attempt ) )
                           {
                                char *p, *np;
                                char *tmpbuf;

                                tmpbuf = getmem(source->hash.length + 8);
                                /* + 8 to add "s." or "SCCS/s." */
                                memset(tmpbuf,0,source->hash.length + 8);
                                source->string_mb[source->hash.length - 1] = '\0';
                                if(p = (char *) memchr((char *)source->string_mb,'/',source->hash.length))
                                {
                                  while(1) {
                                    if(np = (char *) memchr((char *)p+1,'/',source->hash.length - (p - source->string_mb))) {
                                      p = np;
                                    } else {break;}
                                  }
                                  /* copy everything including '/' */
                                  strncpy(tmpbuf, source->string_mb, p - source->string_mb + 1);
                                  strcat(tmpbuf, "s.");
                                  strcat(tmpbuf, p+1);
                                  retmem((wchar_t *) source->string_mb);
                                  source->string_mb = tmpbuf;

                                } else {
                                  strcpy(tmpbuf, "s.");
                                  strcat(tmpbuf, source->string_mb);
                                  retmem((wchar_t *) source->string_mb);
                                  source->string_mb = tmpbuf;

                                }
                                source->hash.length = strlen(source->string_mb);
                                if(exists(source) == file_doesnt_exist)
                                  continue;
                                tilde_rule = true;
                                we_are_in_tilde = true;
                           } else {
                                if(!name_found) {
                                        free_name(source);
                                }
                                continue;
                           }
                        } else {
                           if(posix && posix_tilde_attempt) {
                                if(exists(source) == file_doesnt_exist) {
                                        if(!name_found) {
                                                free_name(source);
                                        }
                                        continue;
                                }
                           }
                        }

                        if (command != NULL) {
                                if(!name_found) {
                                        store_name(source);
                                }
                                /*
                                 * The source file is a file.
                                 * Make sure it is up to date.
                                 */
                                if (dependency_exists(source,
                                                      get_prop(target->prop,
                                                               line_prop))) {
                                        result = (Doname) source->state;
                                } else {
#if 0  /* with_squiggle sends false, which is buggy. : djay */
                                        result = doname(source,
                                                        (Boolean) source_suffix->body.
                                                        suffix.suffix->with_squiggle,
                                                        true);
#else
                                        result = doname(source,
                                                        true,
                                                        true);
#endif
                                }
                        } else {
                                result = target_can_be_built(source);

                                if (result == build_ok) {
                                        return result;
                                } else {
                                        if(!name_found) {
                                                free_name(source);
                                        }
                                        continue;
                                }
                        }

                        switch (result) {
                        case build_dont_know:
                                /*
                                 * If we still can't build the source,
                                 * this rule is not a match,
                                 * try the next one.
                                 */
                                if (source->stat.time == file_doesnt_exist) {
                                        if(!name_found) {
                                                free_name(source);
                                        }
                                        continue;
                                }
                                /* FALLTHROUGH */
                        case build_running:
                                if(!name_found) {
                                        store_name(source);
                                }
                                true_target->suffix_scan_done = false;
                                line = maybe_append_prop(target, line_prop);
                                enter_dependency(line, source, false);
                                line->body.line.target = true_target;
                                return build_running;
                        case build_ok:
                                if(!name_found) {
                                        store_name(source);
                                }
                                break;
                        case build_failed:
                                if(!name_found) {
                                        store_name(source);
                                }
                                if (sourcename != static_string_buf_3M) {
                                        retmem(sourcename);
                                }
                                return build_failed;
                        }

                        if (debug_level > 1) {
                                WCSTOMBS(mbs_buffer, sourcename);
                                (void) printf(gettext("%*sFound %s\n"),
                                              recursion_level,
                                              "",
                                              mbs_buffer);
                        }

                        if (source->depends_on_conditional) {
                                target->depends_on_conditional = true;
                        }
/*
 * Since it is possible that the same target is built several times during
 * the make run, we have to patch the target with all information we found
 * here. Thus, the target will have an explicit rule the next time around.
 */
                        line = maybe_append_prop(target, line_prop);
                        if (*command == NULL) {
                                *command = line;
                        }
                        if ((source->stat.time > (*command)->body.line.dependency_time) &&
                            (debug_level > 1)) {
                                (void) printf(gettext("%*sDate(%s)=%s Date-dependencies(%s)=%s\n"),
                                              recursion_level,
                                              "",
                                              source->string_mb,
                                              time_to_string(source->
                                                             stat.time),
                                              true_target->string_mb,
                                              time_to_string((*command)->
                                                             body.line.
                                                             dependency_time));
                        }
                        /*
                         * Determine if this new dependency made the
                         * target out of date.
                         */
                        (*command)->body.line.dependency_time =
                          MAX((*command)->body.line.dependency_time,
                              source->stat.time);
                        Boolean out_of_date;
                        if (target->is_member) {
                                out_of_date = (Boolean) OUT_OF_DATE_SEC(target->stat.time,
                                                                        (*command)->body.line.dependency_time);
                        } else {
                                out_of_date = (Boolean) OUT_OF_DATE(target->stat.time,
                                                                    (*command)->body.line.dependency_time);
                        }
                        if (build_unconditional || out_of_date) {
                                if(!rechecking) {
                                        line->body.line.is_out_of_date = true;
                                }
                                if (debug_level > 0) {
                                        (void) printf(gettext("%*sBuilding %s using suffix rule for %s%s because it is out of date relative to %s\n"),
                                                      recursion_level,
                                                      "",
                                                      true_target->string_mb,
                                                      source_suffix->body.suffix.suffix->string_mb,
                                                      target_suffix->string_mb,
                                                      source->string_mb);
                                }
                        }
                        /*
                         * Add the implicit rule as the target's explicit
                         * rule if none actually given, and register
                         * dependency.
                         * The time checking above really should be
                         * conditional on actual use of implicit rule
                         * as well.
                         */
                        line->body.line.sccs_command = false;
                        if (line->body.line.command_template == NULL) {
                                line->body.line.command_template =
                                  source_suffix->body.suffix.command_template;
                        }
                        enter_dependency(line, source, false);
                        line->body.line.target = true_target;
                        /*
                         * Also make sure the rule is built with
                         * $* and $< bound properly.
                         */
                        line->body.line.star = target_body;
                        if(svr4|posix) {
                          char * p;
                          char tstr[256];
                          extern Boolean dollarless_flag;
                          extern Name dollarless_value;

                          if(tilde_rule) {
                              MBSTOWCS(wcs_buffer, source->string_mb);
                              dollarless_value = GETNAME(wcs_buffer,FIND_LENGTH);
                          }
                          else {
                                   dollarless_flag = false;
                          }
                        }
                        line->body.line.less = source;
                        line->body.line.percent = NULL;
                        add_target_to_chain(source, &(line->body.line.query));
                        if (sourcename != static_string_buf_3M) {
                                retmem(sourcename);
                        }
                        return build_ok;
                }
                if(posix && posix_tilde_attempt) {
                        posix_tilde_attempt = false;
                        goto posix_attempts;
                }
                if ((command != NULL) &&
                    ((*command) != NULL) &&
                    ((*command)->body.line.star == NULL)) {
                        (*command)->body.line.star = target_body;
                }
        }
        if (sourcename != static_string_buf_3M) {
                retmem(sourcename);
        }
        /* Return here in case no rule matched the target */
        return build_dont_know;
}

/*
 *      find_ar_suffix_rule(target, true_target, command, rechecking)
 *
 *      Scans the .SUFFIXES list and tries
 *      to find a suffix on it that matches the tail of the target member name.
 *      If it finds a matching suffix it calls find_suffix_rule() to find
 *      a rule for the target using the suffix ".a".
 *
 *      Return value:
 *                              Indicates if search failed or not
 *
 *      Parameters:
 *              target          The target we need a rule for
 *              true_target     The proper name
 *              command         Pointer to slot where we stuff cmd, if found
 *              rechecking      true if we are rechecking target which depends
 *                              on conditional macro and keep_state is set
 *
 *      Global variables used:
 *              debug_level     Indicates how much tracing to do
 *              dot_a           The Name ".a", compared against
 *              recursion_level Used for tracing
 *              suffixes        List of suffixes used for scan (from .SUFFIXES)
 */
Doname
find_ar_suffix_rule(Name target, Name true_target, Property *command, Boolean rechecking)
{
        wchar_t                 *target_end;
        Dependency      suffix;
        int             suffix_length;
        Property                line;
        Name                    body;
        static Name             dot_a;

        Wstring                 targ_string(true_target);
        Wstring                 suf_string;

        if (dot_a == NULL) {
                MBSTOWCS(wcs_buffer, ".a");
                dot_a = GETNAME(wcs_buffer, FIND_LENGTH);
        }
        target_end = targ_string.get_string() + true_target->hash.length;

        /*
         * We compare the tail of the target name with the suffixes
         * from .SUFFIXES.
         */
        if (debug_level > 1) {
                (void) printf("%*sfind_ar_suffix_rule(%s)\n",
                              recursion_level,
                              "",
                              true_target->string_mb);
        }
        /*
         * Scan the .SUFFIXES list to see if the target matches any of
         * those suffixes.
         */
        for (suffix = suffixes; suffix != NULL; suffix = suffix->next) {
                /* Compare one suffix. */
                suffix_length = suffix->name->hash.length;
                suf_string.init(suffix->name);
                if (!IS_WEQUALN(suf_string.get_string(),
                                target_end - suffix_length,
                                suffix_length)) {
                        goto not_this_one;
                }
                /*
                 * The target tail matched a suffix from the .SUFFIXES list.
                 * Now check for a rule to match.
                 */
                target->suffix_scan_done = false;
                body = GETNAME(targ_string.get_string(),
                               (int)(true_target->hash.length -
                                     suffix_length));
                we_are_in_tilde = false;
                switch (find_suffix_rule(target,
                                         body,
                                         dot_a,
                                         command,
                                         rechecking)) {
                case build_ok:
                        line = get_prop(target->prop, line_prop);
                        line->body.line.star = body;
                        return build_ok;
                case build_running:
                        return build_running;
                }
                /*
                 * If no rule was found, we try the next suffix to see
                 * if it matches the target tail, and so on.
                 * Go here if the suffix did not match the target tail.
                 */
        not_this_one:;
        }
        return build_dont_know;
}

/*
 *      find_double_suffix_rule(target, command, rechecking)
 *
 *      Scans the .SUFFIXES list and tries
 *      to find a suffix on it that matches the tail of the target name.
 *      If it finds a matching suffix it calls find_suffix_rule() to find
 *      a rule for the target.
 *
 *      Return value:
 *                              Indicates if scan failed or not
 *
 *      Parameters:
 *              target          Target we need a rule for
 *              command         Pointer to slot where we stuff cmd, if found
 *              rechecking      true if we are rechecking target which depends
 *                              on conditional macro and keep_state is set
 *
 *      Global variables used:
 *              debug_level     Indicates how much tracing to do
 *              recursion_level Used for tracing
 *              suffixes        List of suffixes used for scan (from .SUFFIXES)
 */
Doname
find_double_suffix_rule(Name target, Property *command, Boolean rechecking)
{
        Name                    true_target = target;
        Name                    target_body;
        wchar_t *target_end;
        Dependency      suffix;
        int             suffix_length;
        Boolean                 scanned_once = false;
        Boolean                 name_found = true;

        Wstring                 targ_string;
        Wstring                 suf_string;

        /*
         * If the target is a constructed one for a "::" target,
         * we need to consider that.
         */
        if (target->has_target_prop) {
                true_target = get_prop(target->prop,
                                       target_prop)->body.target.target;
        }
        targ_string.init(true_target);

        /*
         * We compare the tail of the target name with the
         * suffixes from .SUFFIXES.
         */
        target_end = targ_string.get_string() + true_target->hash.length;
        if (debug_level > 1) {
                (void) printf("%*sfind_double_suffix_rule(%s)\n",
                              recursion_level,
                              "",
                              true_target->string_mb);
        }
        /*
         * Scan the .SUFFIXES list to see if the target matches
         * any of those suffixes.
         */
        for (suffix = suffixes; suffix != NULL; suffix = suffix->next) {
                target->suffix_scan_done = false;
                true_target->suffix_scan_done = false;
                /* Compare one suffix. */
                suffix_length = suffix->name->hash.length;
                suf_string.init(suffix->name);
                /* Check the lengths, or else RTC will report rua. */
                if (true_target->hash.length < suffix_length) {
                        goto not_this_one;
                } else if (!IS_WEQUALN(suf_string.get_string(),
                                (target_end - suffix_length),
                                suffix_length)) {
                        goto not_this_one;
                }
                /*
                 * The target tail matched a suffix from the .SUFFIXES list.
                 * Now check for a rule to match.
                 */
                we_are_in_tilde = false;
                target_body = GETNAME(
                        targ_string.get_string(),
                        (int)(true_target->hash.length - suffix_length)
                );
                switch (find_suffix_rule(target,
                                         target_body,
                                         suffix->name,
                                         command,
                                         rechecking)) {
                case build_ok:
                        return build_ok;
                case build_running:
                        return build_running;
                }
                if (true_target->suffix_scan_done == true) {
                        scanned_once = true;
                }
                /*
                 * If no rule was found, we try the next suffix to see
                 * if it matches the target tail. And so on.
                 * Go here if the suffix did not match the target tail.
                 */
        not_this_one:;
        }
        if (scanned_once)
                true_target->suffix_scan_done = true;
        return build_dont_know;
}

/*
 *      build_suffix_list(target_suffix)
 *
 *      Scans the .SUFFIXES list and figures out
 *      which suffixes this target can be derived from.
 *      The target itself is not know here, we just know the suffix of the
 *      target. For each suffix on the list the target can be derived iff
 *      a rule exists for the name "<suffix-on-list><target-suffix>".
 *      A list of all possible building suffixes is built, with the rule for
 *      each, and tacked to the target suffix nameblock.
 *
 *      Parameters:
 *              target_suffix   The suffix we build a match list for
 *
 *      Global variables used:
 *              debug_level     Indicates how much tracing to do
 *              recursion_level Used for tracing
 *              suffixes        List of suffixes used for scan (from .SUFFIXES)
 *              working_on_targets Indicates that this is a real target
 */
void
build_suffix_list(Name target_suffix)
{
        Dependency      source_suffix;
        wchar_t                 rule_name[MAXPATHLEN];
        Property        line;
        Property        suffix;
        Name                    rule;

        /* If this is before default.mk has been read we just return to try */
        /* again later */
        if ((suffixes == NULL) || !working_on_targets) {
                return;
        }
        if (debug_level > 1) {
                (void) printf("%*sbuild_suffix_list(%s) ",
                              recursion_level,
                              "",
                              target_suffix->string_mb);
        }
        /* Mark the target suffix saying we cashed its list */
        target_suffix->has_read_suffixes = true;
        /* Scan the .SUFFIXES list */
        for (source_suffix = suffixes;
             source_suffix != NULL;
             source_suffix = source_suffix->next) {
                /*
                 * Build the name "<suffix-on-list><target-suffix>".
                 * (a popular one would be ".c.o").
                 */
                (void) mbstowcs(rule_name,
                              source_suffix->name->string_mb,
                              (int) source_suffix->name->hash.length);
                (void) mbstowcs(rule_name + source_suffix->name->hash.length,
                              target_suffix->string_mb,
                              (int) target_suffix->hash.length);
                /*
                 * Check if that name has a rule. If not, it cannot match
                 * any implicit rule scan and is ignored.
                 * The GETNAME() call only checks for presence, it will not
                 * enter the name if it is not defined.
                 */
                if (((rule = getname_fn(rule_name,
                                        (int) (source_suffix->name->
                                               hash.length +
                                               target_suffix->hash.length),
                                        true)) != NULL) &&
                    ((line = get_prop(rule->prop, line_prop)) != NULL)) {
                        if (debug_level > 1) {
                                (void) printf("%s ", rule->string_mb);
                        }
                        /*
                         * This makes it possible to quickly determine if
                         * it will pay to look for a suffix property.
                         */
                        target_suffix->has_suffixes = true;
                        /*
                         * Add the suffix property to the target suffix
                         * and save the rule with it.
                         * All information the implicit rule scanner need
                         * is saved in the suffix property.
                         */
                        suffix = append_prop(target_suffix, suffix_prop);
                        suffix->body.suffix.suffix = source_suffix->name;
                        suffix->body.suffix.command_template =
                          line->body.line.command_template;
                }
        }
        if (debug_level > 1) {
                (void) printf("\n");
        }
}

/*
 *      find_percent_rule(target, command, rechecking)
 *
 *      Tries to find a rule from the list of wildcard matched rules.
 *      It scans the list attempting to match the target.
 *      For each target match it checks if the corresponding source exists.
 *      If it does the match is returned.
 *      The percent_list is built at makefile read time.
 *      Each percent rule get one entry on the list.
 *
 *      Return value:
 *                              Indicates if the scan failed or not
 *
 *      Parameters:
 *              target          The target we need a rule for
 *              command         Pointer to slot where we stuff cmd, if found
 *              rechecking      true if we are rechecking target which depends
 *                              on conditional macro and keep_state is set
 *
 *      Global variables used:
 *              debug_level     Indicates how much tracing to do
 *              percent_list    List of all percent rules
 *              recursion_level Used for tracing
 *              empty_name
 */
Doname
find_percent_rule(Name target, Property *command, Boolean rechecking)
{
        Percent pat_rule, pat_depe;
        Name            depe_to_check;
        Dependency      depe;
        Property        line;
        String_rec              string;
        wchar_t                 string_buf[STRING_BUFFER_LENGTH];
        String_rec              percent;
        wchar_t                 percent_buf[STRING_BUFFER_LENGTH];
        Name                    true_target = target;
        Name                    less;
        Boolean                 nonpattern_less;
        Boolean                 dep_name_found = false;
        Doname                  result = build_dont_know;
        Percent                 rule_candidate = NULL;
        Boolean                 rule_maybe_ok;
        Boolean                 is_pattern;

        /* If the target is constructed for a "::" target we consider that */
        if (target->has_target_prop) {
                true_target = get_prop(target->prop,
                                       target_prop)->body.target.target;
        }
        if (target->has_long_member_name) {
                true_target = get_prop(target->prop,
                                       long_member_name_prop)->body.long_member_name.member_name;
        }
        if (debug_level > 1) {
                (void) printf(gettext("%*sLooking for %% rule for %s\n"),
                              recursion_level,
                              "",
                              true_target->string_mb);
        }
        for (pat_rule = percent_list;
             pat_rule != NULL;
             pat_rule = pat_rule->next) {
                /* Avoid infinite recursion when expanding patterns */
                if (pat_rule->being_expanded == true) {
                        continue;
                }

                /* Mark this pat_rule as "maybe ok". If no % rule is found
                   make will use this rule. The following algorithm is used:
                   1) make scans all pattern rules in order to find the rule
                      where ALL dependencies, including nonpattern ones, exist or
                      can be built (GNU behaviour). If such rule is found make
                      will apply it.
                   2) During this check make also remembers the first pattern rule
                      where all PATTERN dependencies can be build (no matter what
                      happens with nonpattern dependencies).
                   3) If no rule satisfying 1) is found, make will apply the rule
                      remembered in 2) if there is one.
                */
                rule_maybe_ok = true;

                /* used to track first percent dependency */
                less = NULL;
                nonpattern_less = true;

                /* check whether pattern matches.
                   if it matches, percent string will contain matched percent part of pattern */
                if (!match_found_with_pattern(true_target, pat_rule, &percent, percent_buf)) {
                        continue;
                }
                if (pat_rule->dependencies != NULL) {
                        for (pat_depe = pat_rule->dependencies;
                             pat_depe != NULL;
                             pat_depe = pat_depe->next) {
                                /* checking result for dependency */
                                result = build_dont_know;

                                dep_name_found = true;
                                if (pat_depe->name->percent) {
                                        is_pattern = true;
                                        /* build dependency name */
                                        INIT_STRING_FROM_STACK(string, string_buf);
                                        construct_string_from_pattern(pat_depe, &percent, &string);
                                        depe_to_check = getname_fn(string.buffer.start,
                                                FIND_LENGTH,
                                                false,
                                                &dep_name_found
                                        );

                                        if ((less == NULL) || nonpattern_less) {
                                                less = depe_to_check;
                                                nonpattern_less = false;
                                        }
                                } else {
                                        /* nonpattern dependency */
                                        is_pattern = false;
                                        depe_to_check = pat_depe->name;
                                        if(depe_to_check->dollar) {
                                                INIT_STRING_FROM_STACK(string, string_buf);
                                                expand_value(depe_to_check, &string, false);
                                                depe_to_check = getname_fn(string.buffer.start,
                                                        FIND_LENGTH,
                                                        false,
                                                        &dep_name_found
                                                );
                                        }
                                        if (less == NULL) {
                                                less = depe_to_check;
                                        }
                                }

                                if (depe_to_check == empty_name) {
                                                result = build_ok;
                                } else {
                                        if (debug_level > 1) {
                                                (void) printf(gettext("%*sTrying %s\n"),
                                                              recursion_level,
                                                              "",
                                                              depe_to_check->string_mb);
                                        }

                                        pat_rule->being_expanded = true;

                                        /* suppress message output */
                                        int save_debug_level = debug_level;
                                        debug_level = 0;

                                        /* check whether dependency can be built */
                                        if (dependency_exists(depe_to_check,
                                              get_prop(target->prop,
                                                       line_prop)))
                                        {
                                                result = (Doname) depe_to_check->state;
                                        } else {
                                                if(actual_doname) {
                                                        result = doname(depe_to_check, true, true);
                                                } else {
                                                        result = target_can_be_built(depe_to_check);
                                                }
                                                if(!dep_name_found) {
                                                        if(result != build_ok && result != build_running) {
                                                                free_name(depe_to_check);
                                                        } else {
                                                                store_name(depe_to_check);
                                                        }
                                                }
                                        }
                                        if(result != build_ok && is_pattern) {
                                                rule_maybe_ok = false;
                                        }

                                        /* restore debug_level */
                                        debug_level = save_debug_level;
                                }

                                if (pat_depe->name->percent) {
                                        if (string.free_after_use) {
                                                retmem(string.buffer.start);
                                        }
                                }
                                /* make can't figure out how to make this dependency */
                                if (result != build_ok && result != build_running) {
                                        pat_rule->being_expanded = false;
                                        break;
                                }
                        }
                } else {
                        result = build_ok;
                }

                /* this pattern rule is the needed one since all dependencies could be built */
                if (result == build_ok || result == build_running) {
                        break;
                }

                /* Make does not know how to build some of dependencies from this rule.
                   But if all "pattern" dependencies can be built, we remember this rule
                   as a candidate for the case if no other pattern rule found.
                */
                if(rule_maybe_ok && rule_candidate == NULL) {
                        rule_candidate = pat_rule;
                }
        }

        /* if no pattern matching rule was found, use the remembered candidate
           or return build_dont_know if there is no candidate.
        */
        if (result != build_ok && result != build_running) {
                if(rule_candidate) {
                        pat_rule = rule_candidate;
                } else {
                        return build_dont_know;
                }
        }

        /* if we are performing only check whether dependency could be built with existing rules,
           return success */
        if (command == NULL) {
                if(pat_rule != NULL) {
                        pat_rule->being_expanded = false;
                }
                return result;
        }

        if (debug_level > 1) {
                (void) printf(gettext("%*sMatched %s:"),
                                      recursion_level,
                                      "",
                                      target->string_mb);

                for (pat_depe = pat_rule->dependencies;
                     pat_depe != NULL;
                     pat_depe = pat_depe->next) {
                        if (pat_depe->name->percent) {
                                INIT_STRING_FROM_STACK(string, string_buf);
                                construct_string_from_pattern(pat_depe, &percent, &string);
                                depe_to_check = GETNAME(string.buffer.start, FIND_LENGTH);
                        } else {
                                depe_to_check = pat_depe->name;
                                if(depe_to_check->dollar) {
                                        INIT_STRING_FROM_STACK(string, string_buf);
                                        expand_value(depe_to_check, &string, false);
                                        depe_to_check = GETNAME(string.buffer.start, FIND_LENGTH);
                                }
                        }

                        if (depe_to_check != empty_name) {
                                (void) printf(" %s", depe_to_check->string_mb);
                        }
                }

                (void) printf(gettext(" from: %s:"),
                              pat_rule->name->string_mb);

                for (pat_depe = pat_rule->dependencies;
                     pat_depe != NULL;
                     pat_depe = pat_depe->next) {
                        (void) printf(" %s", pat_depe->name->string_mb);
                }

                (void) printf("\n");
        }

        if (true_target->colons == no_colon) {
                true_target->colons = one_colon;
        }

        /* create deppendency list and target group from matched pattern rule */
        create_target_group_and_dependencies_list(target, pat_rule, &percent);

        /* save command */
        line = get_prop(target->prop, line_prop);
        *command = line;

        /* free query chain if one exist */
        while(line->body.line.query != NULL) {
                Chain to_free = line->body.line.query;
                line->body.line.query = line->body.line.query->next;
                retmem_mb((char *) to_free);
        }

        if (line->body.line.dependencies != NULL) {
                /* build all collected dependencies */
                for (depe = line->body.line.dependencies;
                     depe != NULL;
                     depe = depe->next) {
                        actual_doname = true;
                        result = doname_check(depe->name, true, true, depe->automatic);

                        actual_doname = false;
                        if (result == build_failed) {
                                pat_rule->being_expanded = false;
                                return build_failed;
                        }
                        if (result == build_running) {
                                pat_rule->being_expanded = false;
                                return build_running;
                        }

                        if ((depe->name->stat.time > line->body.line.dependency_time) &&
                            (debug_level > 1)) {
                                (void) printf(gettext("%*sDate(%s)=%s Date-dependencies(%s)=%s\n"),
                                              recursion_level,
                                              "",
                                              depe->name->string_mb,
                                              time_to_string(depe->name->stat.time),
                                              true_target->string_mb,
                                              time_to_string(line->body.line.dependency_time));
                        }

                        line->body.line.dependency_time =
                          MAX(line->body.line.dependency_time, depe->name->stat.time);

                        /* determine whether this dependency made target out of date */
                        Boolean out_of_date;
                        if (target->is_member || depe->name->is_member) {
                                out_of_date = (Boolean) OUT_OF_DATE_SEC(target->stat.time, depe->name->stat.time);
                        } else {
                                out_of_date = (Boolean) OUT_OF_DATE(target->stat.time, depe->name->stat.time);
                        }
                        if (build_unconditional || out_of_date) {
                                if(!rechecking) {
                                        line->body.line.is_out_of_date = true;
                                }
                                add_target_to_chain(depe->name, &(line->body.line.query));

                                if (debug_level > 0) {
                                        (void) printf(gettext("%*sBuilding %s using pattern rule %s:"),
                                                      recursion_level,
                                                      "",
                                                      true_target->string_mb,
                                                      pat_rule->name->string_mb);

                                        for (pat_depe = pat_rule->dependencies;
                                             pat_depe != NULL;
                                             pat_depe = pat_depe->next) {
                                                (void) printf(" %s", pat_depe->name->string_mb);
                                        }

                                        (void) printf(gettext(" because it is out of date relative to %s\n"),
                                                      depe->name->string_mb);
                                }
                        }
                }
        } else {
                if ((true_target->stat.time <= file_doesnt_exist) ||
                    (true_target->stat.time < line->body.line.dependency_time)) {
                        if(!rechecking) {
                                line->body.line.is_out_of_date = true;
                        }
                        if (debug_level > 0) {
                                (void) printf(gettext("%*sBuilding %s using pattern rule %s: "),
                                              recursion_level,
                                              "",
                                              true_target->string_mb,
                                              pat_rule->name->string_mb,
                                              (target->stat.time > file_doesnt_exist) ?
                                              gettext("because it is out of date") :
                                              gettext("because it does not exist"));
                        }
                }
        }

        /* enter explicit rule from percent rule */
        Name lmn_target = true_target;
        if (true_target->has_long_member_name) {
                lmn_target = get_prop(true_target->prop, long_member_name_prop)->body.long_member_name.member_name;
        }
        line->body.line.sccs_command = false;
        line->body.line.target = true_target;
        line->body.line.command_template = pat_rule->command_template;
        line->body.line.star = GETNAME(percent.buffer.start, FIND_LENGTH);
        line->body.line.less = less;

        if (lmn_target->parenleft) {
                Wstring lmn_string(lmn_target);

                wchar_t *left = (wchar_t *) wcschr(lmn_string.get_string(), (int) parenleft_char);
                wchar_t *right = (wchar_t *) wcschr(lmn_string.get_string(), (int) parenright_char);

                if ((left == NULL) || (right == NULL)) {
                        line->body.line.percent = NULL;
                } else {
                        line->body.line.percent = GETNAME(left + 1, right - left - 1);
                }
        } else {
                line->body.line.percent = NULL;
        }
        pat_rule->being_expanded = false;

        return result;
}

/*
 *      match_found_with_pattern
 *           ( target, pat_rule, percent, percent_buf)
 *
 *      matches "target->string" with a % pattern.
 *      If pattern contains a MACRO definition, it's expanded first.
 *
 *      Return value:
 *                              true if a match was found
 *
 *      Parameters:
 *              target          The target we're trying to match
 *              pattern
 *              percent         record that contains "percent_buf" below
 *              percent_buf     This is where the patched % part of pattern is stored
 *
 */

static Boolean
match_found_with_pattern(Name target, Percent pat_rule, String percent, wchar_t *percent_buf) {
        String_rec              string;
        wchar_t                 string_buf[STRING_BUFFER_LENGTH];

        /* construct prefix string and check whether prefix matches */
        Name prefix = pat_rule->patterns[0];
        int prefix_length;

        Wstring targ_string(target);
        Wstring pref_string(prefix);
        Wstring suf_string;

        if (prefix->dollar) {
                INIT_STRING_FROM_STACK(string, string_buf);
                expand_value(prefix, &string, false);
                prefix_length = string.text.p - string.buffer.start;
                if ((string.buffer.start[0] == (int) period_char) &&
                    (string.buffer.start[1] == (int) slash_char)) {
                        string.buffer.start += 2;
                        prefix_length -= 2;
                }
                if (!targ_string.equaln(string.buffer.start, prefix_length)) {
                        return false;
                }
        } else {
                prefix_length = prefix->hash.length;
                if (!targ_string.equaln(&pref_string, prefix_length)) {
                        return false;
                }
        }

        /* do the same with pattern suffix */
        Name suffix = pat_rule->patterns[pat_rule->patterns_total - 1];
        suf_string.init(suffix);

        int suffix_length;
        if (suffix->dollar) {
                INIT_STRING_FROM_STACK(string, string_buf);
                expand_value(suffix, &string, false);
                suffix_length = string.text.p - string.buffer.start;
                if(suffix_length > target->hash.length) {
                        return false;
                }
                if (!targ_string.equal(string.buffer.start, target->hash.length - suffix_length)) {
                        return false;
                }
        } else {
                suffix_length = (int) suffix->hash.length;
                if(suffix_length > target->hash.length) {
                        return false;
                }
                if (!targ_string.equal(&suf_string, target->hash.length - suffix_length)) {
                        return false;
                }
        }

        Boolean match_found = false;
        int percent_length = target->hash.length - prefix_length - suffix_length;

        while (!match_found && (percent_length >= 0)) {
                /* init result string */
                INIT_STRING_FROM_STACK(string, string_buf);

                /* init percent string */
                percent->buffer.start = percent_buf;
                percent->text.p = percent_buf;
                percent->text.end = NULL;
                percent->free_after_use = false;
                percent->buffer.end = percent_buf + STRING_BUFFER_LENGTH;

                /* construct percent and result strings */
                targ_string.append_to_str(percent, prefix_length, percent_length);
                construct_string_from_pattern(pat_rule, percent, &string);

                /* check for match */
                if (targ_string.equal(string.buffer.start, 0)) {
                        match_found = true;
                } else {
                        percent_length--;
                }
        }

        /* result */
        return match_found;
}


/*
 *      create_target_group_and_dependencies_list
 *           (target, pat_rule, percent)
 *
 *      constructs dependency list and a target group from pattern.
 *
 *      If we have the lines
 *              %/%.a + %/%.b + C%/CC%.c: yyy %.d bb%/BB%.e
 *                      commands
 *
 *      and we have matched the pattern xx/xx.a with %/%.a, then we
 *      construct a target group that looks like this:
 *              xx/xx.a + xx/xx.b + Cxx/CCxx.c: dependencies
 *
 *      and construct dependency list that looks like this:
 *      yyy xx.d bbxx/BBxx.e + already existed dependencies
 *
 *      Return value:
 *                              none
 *
 *      Parameters:
 *              target          The target we are building, in the previous
 *                              example, this is xx/xx.a
 *              pat_rule        the % pattern that matched "target", here %/%.a
 *              percent         string containing matched % part. In the example=xx.
 *
 *      Global variables used:
 *              empty_name
 */

static void
create_target_group_and_dependencies_list(Name target, Percent pat_rule, String percent) {
        String_rec      string;
        wchar_t         string_buf[STRING_BUFFER_LENGTH];
        Percent         pat_depe;
        Name            depe;
        Property        line = maybe_append_prop(target, line_prop);
        Chain           new_target_group = NULL;
        Chain           *new_target_group_tail = &new_target_group;
        Chain           group_member;

        /* create and append dependencies from rule */
        for (pat_depe = pat_rule->dependencies; pat_depe != NULL; pat_depe = pat_depe->next) {
                if (pat_depe->name->percent) {
                        INIT_STRING_FROM_STACK(string, string_buf);
                        construct_string_from_pattern(pat_depe, percent, &string);
                        depe = GETNAME(string.buffer.start, FIND_LENGTH);
                        if (depe != empty_name) {
                                enter_dependency(line, depe, false);
                        }
                } else {
                        depe = pat_depe->name;
                        if(depe->dollar) {
                                INIT_STRING_FROM_STACK(string, string_buf);
                                expand_value(depe, &string, false);
                                depe = GETNAME(string.buffer.start, FIND_LENGTH);
                        }
                        enter_dependency(line, depe, false);
                }
        }

        /* if matched pattern is a group member, create new target group */
        for (group_member = pat_rule->target_group; group_member != NULL; group_member = group_member->next) {
                Name new_target = group_member->name;
                if (group_member->name->percent) {
                        INIT_STRING_FROM_STACK(string, string_buf);
                        construct_string_from_pattern(group_member->percent_member, percent, &string);
                        new_target = GETNAME(string.buffer.start, FIND_LENGTH);
                        if (new_target == empty_name) {
                                continue;
                        }
                }

                /* check for duplicates */
                Chain   tgm;
                for (tgm = new_target_group; tgm != NULL; tgm = tgm->next) {
                        if (new_target == tgm->name) {
                                break;
                        }
                }
                if (tgm != NULL) {
                        continue;
                }

                /* insert it into the targets list */
                (*new_target_group_tail) = ALLOC(Chain);
                (*new_target_group_tail)->name = new_target;
                (*new_target_group_tail)->next = NULL;
                new_target_group_tail = &(*new_target_group_tail)->next;
        }

        /* now we gathered all dependencies and created target group */
        line->body.line.target_group = new_target_group;

        /* update properties for group members */
        for (group_member = new_target_group; group_member != NULL; group_member = group_member->next) {
                if (group_member->name != target) {
                        group_member->name->prop = target->prop;
                        group_member->name->conditional_cnt = target->conditional_cnt;
                }
        }
}

/*
 *      construct_string_from_pattern
 *              (pat_rule, percent, result)
 *
 *      after pattern matched a target this routine is called to construct targets and dependencies
 *      strings from this matched pattern rule and a string (percent) with substitutes % sign in pattern.
 *
 *      Return value:
 *                              none
 *
 *      Parameters:
 *              pat_rule        matched pattern rule
 *              percent         string containing matched % sign part.
 *              result          holds the result of string construction.
 *
 */
static void
construct_string_from_pattern(Percent pat_rule, String percent, String result) {
        for (int i = 0; i < pat_rule->patterns_total; i++) {
                if (pat_rule->patterns[i]->dollar) {
                        expand_value(pat_rule->patterns[i],
                                     result,
                                     false);

                } else {
                        append_string(pat_rule->patterns[i]->string_mb,
                                      result,
                                      pat_rule->patterns[i]->hash.length);
                }

                if (i < pat_rule->patterns_total - 1) {
                        append_string(percent->buffer.start,
                                      result,
                                      percent->text.p - percent->buffer.start);
                }
        }

        if ((result->buffer.start[0] == (int) period_char) &&
            (result->buffer.start[1] == (int) slash_char)) {
                result->buffer.start += 2;
        }
}

/*
 *      dependency_exists(target, line)
 *
 *      Returns true if the target exists in the
 *      dependency list of the line.
 *
 *      Return value:
 *                              True if target is on dependency list
 *
 *      Parameters:
 *              target          Target we scan for
 *              line            We get the dependency list from here
 *
 *      Global variables used:
 */
static Boolean
dependency_exists(Name target, Property line)
{
        Dependency      dp;

        if (line == NULL) {
                return false;
        }
        for (dp = line->body.line.dependencies; dp != NULL; dp = dp->next) {
                if (dp->name == target) {
                        return true;
                }
        }
        return false;
}

void
add_target_to_chain(Name target, Chain * query)
{
        if (target->is_member && (get_prop(target->prop, member_prop) != NULL)) {
                target = get_prop(target->prop, member_prop)->body.member.member;
        }
        Chain   *query_tail;
        for (query_tail = query; *query_tail != NULL; query_tail = &(*query_tail)->next) {
                if ((*query_tail)->name == target) {
                        return;
                }
        }
        *query_tail = ALLOC(Chain);
        (*query_tail)->name = target;
        (*query_tail)->next = NULL;
}