build specification - Hiroshi123/bin_tools GitHub Wiki

Build command

build command is intended for parsing Makefile with minimum amount of codes.

Makefile consists of set of variables & rules.

Variables are referred by rules.

a := b

target1 : deps
      command $(a)
  1. Parse every variables & rules, you have the set of both.
  2. Resolve variables or any referenced characters on each rule.
    • this resolving step should actually replace string and entire target, deps & command is put on newly-allocated space.
    • if a variable refers another variable, then you need to resolve until the point you no longer needs to resolve.
    • if you allocate new string on this step, member of struct rule should point newly allocated string.
    • It seems that this step can be omitted considering not all of rules are executed. However, when a given target tries to find one of rules, every target name needs to be resolved until then, which means at least all target names needs to be resolved before the selection.
    • primary version had less memory architecture of which the idea is to get the index of variable table not string itself, such as ${1} meaning 1 is index on a variable table. This sounds more cool but, has some limitation. For instance, if a variable is defined by two other variables, then multiple indexes must be referred, and the number is not unpredictable. Another thing is if it is abbreviation of target or deps, the expression of index will be complex and not obvious.
  1. Construct a tree for execution.
    • A Given target or a default target will be picked up as root of the execution tree.
    • If it is dependent with another rule, then construct the tree letting it a node or a leaf on the tree.
    • Each leaf and node should contain if it is needed to be executed checking its modification timestamp. Without need to say, if deps needs to be resolved, the node which makes use of the result needs to be executed.

Variables

immediate expansion variable recursive expansion variable
:= = ?=

Immediate expansion variable will be replaced immediately at parse time. Recursive expansion variable will replace an existing value defined on variable table at parse time.

3. Rule Scheduling

Core Algorithm which

  1. Resolve Dependencies (inspect children nodes)

1.1. Edge

if this is file, it means this is an edge of the dependency tree. -> check modification timestamp with stat.

1.2. Node

If this is not a file, it must be a target name, otherwise error.

All target should be searched on a hash table by its hash index.

Current implementation is not on a hash table unlike variable management.

The hash table should be seperated from the hash table for variable as its member string can be overrapped.

If the hash index is matched with

  • There are 3 different types of representation for target.

    • perfectly-matched target

    • partially-matched target (use implicit rule) e.g. %abc, a%bc, abc%

      Num of % must be single, and it can be put anywhere.

      in this case, you should compute hash value omitting % in advance.

      For instance, if a%bc, you should compute hash value of abc. Note that you must pick up a hash function on which the value computed from the member is independent from previous or next string and its index.

      The first M string and the last N string should be recorded and kept tracked for finding its member. For instance, given a%bc, [M,N] = [1,2] should be recorded. Then, assume you find another target ; abc%de. Then, [M,N] = [3,2] will be recorded on somewhere else.

      When you find a string, given abcfghde, you should start from [M,N] = [3,2]. This means you compute hash of first 3 which is abc, then compute the last 2 which is de. If the hash value is matched with something on a hash table, validate it with strcmp but only the part without %. If none of them matched, short M to 1, now [M,N] = [1,2]. you do not need to recompute simply negate the difference.