Semantic Analysis

At this step we want to check if our configuration does not contain any logical errors.

What we will check? I propose to perform these tests:

1. Every class MUST have a «rate» value defined.
2. Every class MUST have a «parent» pointed to an existing class.

Here we will create a subclass of spark.GenericASTTraversal, which traverses tree and calls methods by node name — it will call n_classdef for node «classdef» and so on.

A code:

#!/usr/bin/env python
 
import spark
from helper import getValue
 
defined_classes = []
requested_parents = []
 
 
class HTBCheckTree(spark.GenericASTTraversal):
    def __init__(self, ast):
        spark.GenericASTTraversal.__init__(self, ast)
        self.postorder()
 
    def n_root(self, node):
        defined_classes.append(node.classid)
 
    def n_classdef(self, node):
        if not getValue(node, 'rate'):
            print "Error: `rate' for class MUST be set.\n"
            raise RuntimeError
 
        defined_classes.append(node.classid)
        requested_parents.append(node.parent)
 
    def n_classes(self, node):
        for p in requested_parents:
            if p.attr not in [ d.attr for d in defined_classes ]:
                print "Error: class %s does not exist.\n" % p.attr
                raise RuntimeError

Everything is simple :-)

We need methods to process some of node types only. Every «classdef» node checks if «rate» is set, and appends «classid» and «parent» parameters to corresponding lists. «Root» node appends «classid» to list also. And since SPARK processes AST in bottom–up direction (from «leaf» nodes to «root» node — from «classdef» to «classes» in our tree), «classes» node will be processed the last when all «classid«‘s are collected already.

helper.getValue is a function which returns a value of a parameter by its name (we will use it later):

def getValue(node, param):
    for p in node.params:
        if p.type == param:
            return p.value
    else:
        return None

And at this step we can check if «ceil» is set and set it equal to «rate» if missed (but, probably, it is better to do it at code generation step?).

Still making errors

It is easy to prove that this module will catch errors mentioned above :-)

Now we have an Abstract Syntax Tree for our configuration, which is correct lexically, syntatically and semantically. Go forward for Code Generation.