RoutePolicy.py

import argparse
import collections
import copy
import json
import os
import pprint
import re
from operator import itemgetter
from warnings import warn

import pandas as pd
import plotly
import plotly.graph_objs as go
from docopt import docopt
from matplotlib import cm
from matplotlib.colors import rgb2hex
from munkres import Munkres

import commonFunctions

LINENUM = "lineNum"
STMT_PENALTY = 5


class Block:
    """ Class to represent information about a route-policy term/clause.
    
    :ivar lineNum: The line number in the sequence of terms.
    :ivar termJson: The representation of a parsed term  in JSON. 
    """

    def __init__(self, lineNum, guard, trueStatements):
        self.guardCmds = list()
        self.trueCmds = list()
        self.action = {}
        # Default actions is taken as permit (then next term)
        self.action["type"] = " permit "
        self.action[LINENUM] = lineNum[0]
        lineNum[0] += 1

        if guard:
            if "Conjunction" in guard["class"] and "conjuncts" in guard:
                for cmd in guard["conjuncts"]:
                    innerConjuncts = False
                    if "Disjunction" in cmd["class"]:
                        copyCmd = self.checkGuardCmdSyntax(self.flattenDisjuncts(cmd["disjuncts"]))
                    elif "Conjunction" in cmd["class"] and "conjuncts" in cmd:
                        innerConjuncts = True
                        # TODO: Remove duplicate guard cmds generated by conjuncts
                        for cmd2 in cmd["conjuncts"]:
                            copyCmd = self.checkGuardCmdSyntax((cmd2))
                            copyCmd[LINENUM] = lineNum[0]
                            lineNum[0] += 1
                            self.guardCmds.append(copyCmd)
                    else:
                        copyCmd = self.checkGuardCmdSyntax((cmd))
                    if not innerConjuncts:
                        copyCmd[LINENUM] = lineNum[0]
                        lineNum[0] += 1
                        self.guardCmds.append(copyCmd)
            elif "Disjunction" in guard["class"]:
                copyCmd = self.checkGuardCmdSyntax(self.flattenDisjuncts(guard["disjuncts"]))
                copyCmd[LINENUM] = lineNum[0]
                lineNum[0] += 1
                self.guardCmds.append(copyCmd)
            else:
                copyCmd = self.checkGuardCmdSyntax(guard)
                copyCmd[LINENUM] = lineNum[0]
                lineNum[0] += 1
                self.guardCmds.append(copyCmd)

        if trueStatements:
            for stmt in trueStatements:
                # Cisco/Juniper Last Sentence
                # Buffered Statement found in CISCO_IOS_XR
                if "BufferedStatement" in stmt["class"]:
                    stmt = stmt["statement"]
                if "Statements$StaticStatement" in stmt["class"]:
                    if "True" in stmt["type"] or "Accept" in stmt["type"]:
                        self.action["type"] = " permit "
                    elif "False" in stmt["type"] or "Reject" in stmt["type"]:
                        self.action["type"] = " deny "
                    else:
                        warn("unKNOWN Static Statement")
                        #Fall through is taken as Permit
                        self.action["type"] = " permit "
                # Juniper Last Sentence
                elif "If" in stmt["class"]:
                    if "Statements$StaticStatement" in stmt["trueStatements"][0]["class"]:
                        if "True" in stmt["trueStatements"][0]["type"] or "Accept" in stmt["trueStatements"][0]["type"]:
                            self.action["type"] = " permit "
                        elif "False" in stmt["trueStatements"][0]["type"] or "Reject" in stmt["trueStatements"][0]["type"]:
                            self.action["type"] = " deny "
                        else:
                            warn("unhandled Static Statement in Juniper")
                            #Fall through is taken as Permit for noe
                            self.action["type"] = " permit "
                    else:
                        warn("unhandled Static Statement in Juniper")
                # "Juniper will not commit this configuration: 'then community add ANCHOR' is not valid because ANCHOR does not contain any literal communities"
                elif "Comment" in stmt["class"]:
                    pass
                elif "PrependAsPath" in stmt["class"] and "LiteralAsList" in stmt["expr"]["class"]:
                    copyCmd = copy.deepcopy(stmt)
                    copyCmd[LINENUM] = lineNum[0]
                    lineNum[0] += 1
                    aslist = []
                    for asN in copyCmd["expr"]["list"]:
                        aslist.append(asN["as"])
                    copyCmd["expr"]["list"] = aslist
                    self.trueCmds.append(copyCmd)
                elif "SetCommunities" in stmt["class"]:
                    # Juniper Communities
                    copyCmd = copy.deepcopy(stmt)
                    copyCmd[LINENUM] = lineNum[0]
                    lineNum[0] += 1
                    if "exprs" in copyCmd["communitySetExpr"]:
                        names = list()
                        for n in  copyCmd["communitySetExpr"]["exprs"]:
                            if "name" in n:
                                names.append(n["name"])
                        del copyCmd["communitySetExpr"]["exprs"]
                        copyCmd["communitySetExpr"]["name"] = names
                    if "removalCriterion" in copyCmd["communitySetExpr"]:
                        copyCmd["communitySetExpr"]["name"] = copyCmd["communitySetExpr"]["removalCriterion"]["name"]
                        del copyCmd["communitySetExpr"]["removalCriterion"]
                    self.trueCmds.append(copyCmd)
                else:
                    copyCmd = copy.deepcopy(stmt)
                    copyCmd[LINENUM] = lineNum[0]
                    lineNum[0] += 1
                    self.trueCmds.append(copyCmd)

    def checkGuardCmdSyntax(self, cmd):
        if "ConjunctionChain" in cmd["class"]:
                # Juniper Other policy calls
                if "subroutines" in cmd:
                    called = []
                    for sub in cmd["subroutines"]:
                        if "calledPolicyName" in sub:
                            called.append(sub["calledPolicyName"])
                    if called:
                        copyCmd = copy.deepcopy(cmd)
                        copyCmd["subroutines"] = called
                        return copyCmd
        elif "MatchAsPath" in cmd["class"] and "ExplicitAsPathSet" in cmd["expr"]["class"]:
                    # Juniper AS-PATH
                    copyCmd = copy.deepcopy(cmd)
                    newElem = list()
                    for ele in copyCmd["expr"]["elems"]:
                        if "regex" in ele:
                            newElem.append(ele["regex"])
                        else:
                            warn("Unknown ExplicitAsPathSet class")
                    del copyCmd["expr"]["elems"]
                    copyCmd["expr"]["elems"] = newElem
                    return copyCmd              
        return copy.deepcopy(cmd)


    def flattenDisjuncts(self, disjuncts):
        """
        Assumption : In  a disjunct List, there can be disjuncts or the entity.
        In the entity, there is only one more layer of depth
        """
        flatcmd = {}
        for cmd in disjuncts:
            if "Disjunction" in cmd["class"] or "Conjunction" in cmd["class"]:
                warn(
                    "Unhandled flatten Disjuncts - Disjunction/Conjunction in a Disjunction encountered")
            else:
                for key in cmd:
                    if key not in flatcmd:
                        flatcmd[key] = cmd[key]
                    else:
                        if flatcmd[key] != cmd[key]:
                            if isinstance(flatcmd[key], dict):
                                for k in cmd[key]:
                                    if k not in flatcmd[key]:
                                        flatcmd[key][k] = cmd[key][k]
                                    elif flatcmd[key][k] != cmd[key][k]:
                                        mergedValues = list()
                                        if isinstance(flatcmd[key][k], list):
                                            mergedValues.extend(
                                                flatcmd[key][k])
                                        else:
                                            mergedValues.append(
                                                flatcmd[key][k])
                                        mergedValues.append(cmd[key][k])
                                        flatcmd[key][k] = mergedValues
                            elif isinstance(flatcmd[key], list):
                                mergedValues = list()
                                mergedValues.extend(flatcmd[key])
                                mergedValues.extend(cmd[key])
                                flatcmd[key] = mergedValues
                            else:
                                warn("Flatten Disjuncts - non-dict/list encountered")
        return flatcmd


class RoutePolicy:
    """ Class to represent information about a route policy.

    :ivar format: Configuration format of the router
    :ivar name: Name of the route policy
    :ivar router: Router in which the route policy is defined
    :ivar routePolicyJson: The representation of the parsed route policy  in JSON format. 
    """

    def __init__(self, name, router, routePolicyJson, format_):
        self.format = format_
        self.deviceName = router
        self.name = name
        self.blocks = list()
        self.generateClauses(routePolicyJson, [0])

    def generateClauses(self, routePolicyJson, lineNum):

        if ("CISCO" in self.format.upper() or "ARISTA" in self.format.upper()) and len(routePolicyJson) > 0:
                # If there is a IF clause
                if "If" in routePolicyJson[0]["class"]:
                    self.blocks.append(
                        Block(lineNum, routePolicyJson[0]["guard"], routePolicyJson[0]["trueStatements"]))
                    if "falseStatements" in routePolicyJson[0]:
                        self.generateClauses(
                            routePolicyJson[0]["falseStatements"], lineNum)
                # If it is the ending clause, it is ignored in syntatic version.
                elif "Statements$StaticStatement" in routePolicyJson[0]["class"] and "ReturnLocalDefaultAction" in routePolicyJson[0]["type"]:
                    pass
                # Else all are just true statements without guardCmds
                else:
                    self.blocks.append(Block(lineNum, None, routePolicyJson))

        if "JUNIPER" in self.format.upper():
            soFarstmts = list()
            for stmt in routePolicyJson:
                if "If" in stmt["class"]:
                    # The last IF which doesn't have True Statement is a filler for now and is ignored in syntatic version.
                    if "trueStatements" not in stmt or len(stmt["trueStatements"]) == 0:
                        if len(soFarstmts) > 0:
                            self.blocks.append(
                                Block(lineNum, None, soFarstmts))
                            soFarstmts = list()
                    # The last rule might actually have no guard in which case all the set commands are without IF statements.
                    elif "Statements$StaticStatement" in stmt["trueStatements"][0]["class"]:
                        if 'BooleanExprs$StaticBooleanExpr' in stmt["guard"]["class"]:
                            soFarstmts.extend(stmt["trueStatements"])
                            self.blocks.append(
                                Block(lineNum, None, soFarstmts))
                            soFarstmts = list()
                        else:
                            if len(soFarstmts) > 0:
                                self.blocks.append(
                                    Block(lineNum, None, soFarstmts))
                                soFarstmts = list()
                            self.blocks.append(
                                Block(lineNum, stmt["guard"], None))
                    else:
                        #In Juniper there are terms without any action to apply the fall through semantics, but we take them as one clause with permit.
                        if len(soFarstmts) > 0:
                            self.blocks.append(
                                Block(lineNum, None, soFarstmts))
                            soFarstmts = list()
                        self.blocks.append(
                            Block(lineNum, stmt["guard"], stmt["trueStatements"]))
                else:
                    if "type" not in stmt or 'SetDefaultActionReject' not in stmt["type"]:
                        soFarstmts.append(stmt)


def GetBlockSequence(device, deviceInfo, pattern, foundDevices, emptyDefDevices, exactDefMatchMap):
    """ Generates block sequence for route policy from the parsed JSON object.
    
    :ivar device: The name of the device.
    :ivar deviceInfo: The JSON model of the configuration. 
    :ivar pattern: The routepolicy pattern that is templated.
    :ivar foundDevices: The set of devices which have at least one routepolicy matching the pattern.
    :ivar emptyDefDevices: The set of devices that have an empty definition for the routepolicy.
    :ivar exactDefMatchMap: The bookkeeping used for exact equality optimization. 
    """
    patternMatchPolicies = []
    patternMatchPoliciesLineCounts = []
    if deviceInfo.get("routingPolicies"):
        routePolicies = deviceInfo.get("routingPolicies")
        for policyName in routePolicies:
            if pattern.match(policyName):
                if device in foundDevices:
                    rname = device + "#" + policyName
                else:
                    rname = device
                routePolicy = RoutePolicy(
                    policyName, rname, routePolicies[policyName]["statements"], deviceInfo['configurationFormat'])
                if len(routePolicy.blocks) > 0:
                    foundDevices.add(rname)
                    if not commonFunctions.checkJSONEquality(exactDefMatchMap, routePolicies[policyName], rname):
                        if len(routePolicy.blocks[-1].trueCmds) > 0:
                            totalLines = routePolicy.blocks[-1].trueCmds[-1][LINENUM]
                        elif len(routePolicy.blocks[-1].guardCmds) > 0:
                            totalLines = routePolicy.blocks[-1].guardCmds[-1][LINENUM]
                        else:
                            totalLines = routePolicy.blocks[-1].action[LINENUM]
                        patternMatchPolicies.append(routePolicy)
                        patternMatchPoliciesLineCounts.append(totalLines)
                else:
                    emptyDefDevices.add(rname)
    return patternMatchPolicies, patternMatchPoliciesLineCounts


def GapPenalty(block):
    """Returns the score for matching the input block with a gap."""
    return len(block.guardCmds)*STMT_PENALTY + \
        len(block.trueCmds) * STMT_PENALTY


def LineSequence(block):
    """Returns the line sequences for a block - returns guard and true cmds as a list of lists."""
    combinedCmds = []
    combinedCmds.append(block.guardCmds)
    combinedCmds.append(block.trueCmds)
    return combinedCmds


def ConvertToString(value):
    if isinstance(value, str):
        return [value]
    elif isinstance(value, int):
        return [str(value)]
    elif isinstance(value, list):
        newlist = []
        for v in value:
            newlist.append(str(v))
        return newlist
    else:
        raise TypeError("Value other than int, list and string found!!")


def LineScoreHelper(value1, value2, paramValueMap):
    score = abs(len(value1)-len(value2))*STMT_PENALTY
    templateValues = copy.deepcopy(value1)
    for v in value2:
        if v in templateValues:
            templateValues.remove(v)
        else:
            found = False
            for p in templateValues:
                if p in paramValueMap:
                    if v not in paramValueMap[p]:
                        score += (STMT_PENALTY/2)
                    templateValues.remove(p)
                    found = True
                    break
            if not found:
                score += STMT_PENALTY
    return score


def LineScore(cmd, stmt, paramValueMap):
    """
    Given two cmds, this functions returns their penalty score
    """
    score = 0
    if cmd["class"] != stmt["class"]:
        return commonFunctions.INFINITY
    else:
        for key in cmd:
            if key != LINENUM:
                if isinstance(cmd[key], dict):
                    # Assuming only depth of 1.
                    if "class" in cmd[key] and cmd[key]["class"] != stmt[key]["class"]:
                        return commonFunctions.INFINITY
                    for k in cmd[key]:
                        if cmd[key][k] != stmt[key][k]:
                            cmd[key][k] = ConvertToString(cmd[key][k])
                            stmt[key][k] = ConvertToString(stmt[key][k])
                            score += LineScoreHelper(cmd[key]
                                                     [k], stmt[key][k], paramValueMap)
                else:
                    if cmd[key] != stmt[key]:
                        cmd[key] = ConvertToString(cmd[key])
                        stmt[key] = ConvertToString(stmt[key])
                        score += LineScoreHelper(cmd[key]
                                                 , stmt[key], paramValueMap)
    return score


def HungarianMatching(cmds1, cmds2, paramValueMap):
    """Returns the score and matching for matching the cmds from the metatemplate with the cmds from the device using Hungarian matching algorithm."""
    similarityMatrix = []
    for cmd1 in cmds1:
        row = []
        for cmd2 in cmds2:
            row.append(LineScore(cmd1, cmd2, paramValueMap))
        similarityMatrix.append(row)
    indicies = []
    matched = []
    matchScore = 0
    # Probably have to include extra score for unmatched lines
    if len(similarityMatrix) > 0:
        m = Munkres()
        indicies = m.compute(similarityMatrix)
        for x, y in indicies:
            if similarityMatrix[x][y] != commonFunctions.INFINITY:
                matched.append((x, y))
                matchScore += similarityMatrix[x][y]
    return matchScore, matched


def BipartiteMatching(LS1, LS2, paramValueMap, empty):
    """ Score and matching calculator for matching LineSequence1 with LineSequence2."""
    score, matchedPairs = 0, []
    guardScore, guardMatches = HungarianMatching(LS1[0], LS2[0], paramValueMap)
    setScore, setMatches = HungarianMatching(LS1[1], LS2[1], paramValueMap)
    score = guardScore + setScore
    matchedPairs.append(guardMatches)
    matchedPairs.append(setMatches)
    return score, matchedPairs


def CombineValueLists(templateValues, deviceValues, parametersLines, paramValueMap, device):
    tv = copy.deepcopy(templateValues)
    unMatchedDeviceValues = []
    matchedTemplateValues = []
    for v in deviceValues:
        if v in tv:
            tv.remove(v)
            matchedTemplateValues.append(v)
        else:
            found = False
            for p in tv:
                if p in paramValueMap:
                    tv.remove(p)
                    matchedTemplateValues.append(p)
                    found = True
                    parametersLines.parameters[device][p] = v
                    break
            if not found:
                unMatchedDeviceValues.append(v)
    for left in unMatchedDeviceValues:
        if tv:
            v = tv.pop()
            param = "P" + str(parametersLines.counter)
            matchedTemplateValues.append(param)
            parametersLines.counter += 1
            parametersLines.parameters[device][param] = left
            parametersLines.addParameter(param, v, device)
        else:
            param = "P" + str(parametersLines.counter)
            matchedTemplateValues.append(param)
            parametersLines.counter += 1
            parametersLines.parameters[device][param] = left
            parametersLines.addParameter(param, "", device)
    if tv:
        for v in tv:
            if v not in paramValueMap:
                param = "P" + str(parametersLines.counter)
                matchedTemplateValues.append(param)
                parametersLines.counter += 1
                parametersLines.parameters[device][param] = ""
                parametersLines.addParameter(param, v, device)
            else:
                parametersLines.parameters[device][v] = ""
                matchedTemplateValues.append(v)
    return matchedTemplateValues


def MergeCmds(templateCmds, deviceCmds, lineNum, parametersLines, matching, oldtoNewLineMap, newDeviceLines, device):
    """ Combines the templateCmds with the deviceCmds and returns the merged cmds.
    
    :ivar templateCmds: The cmds from the template.
    :ivar deviceCmds: The cmds from the device.
    :ivar lineNum: The ending lineNum of the previous term.
    :ivar parameterLines: The bookkeeping info about parameters and line mappings for each device.
    :ivar matching: The map from lines in template to lines in device which are to be merged/combined into a single line.
    """
    combinedCmds = []
    paramValueMap = parametersLines.parameterDistribution()
    templateLeftout = []
    deviceLeftout = []
    tmp = [x for x, y in matching]
    [templateLeftout.append(i)
     for i in range(len(templateCmds)) if i not in tmp]
    tmp = [y for x, y in matching]
    [deviceLeftout.append(i) for i in range(len(deviceCmds)) if i not in tmp]

    for i, cmd in enumerate(templateCmds):
        if i in templateLeftout:
            line = copy.deepcopy(cmd)
            oldtoNewLineMap[line[LINENUM]] = lineNum
            line[LINENUM] = lineNum
            lineNum += 1
            combinedCmds.append(line)

    for i, cmd in enumerate(deviceCmds):
        if i in deviceLeftout:
            line = copy.deepcopy(cmd)
            line[LINENUM] = lineNum
            newDeviceLines.append(lineNum)
            lineNum += 1
            combinedCmds.append(line)

    for i, j in matching:
        tCmd = templateCmds[i]
        dCmd = deviceCmds[j]
        if tCmd["class"] == dCmd["class"]:
            #If they are from same class then they would have same keys
            for key in tCmd:
                if key != LINENUM:
                    if isinstance(tCmd[key], dict):
                        for k in tCmd[key]:
                            if tCmd[key][k] != dCmd[key][k]:
                                tCmd[key][k] = ConvertToString(tCmd[key][k])
                                dCmd[key][k] = ConvertToString(dCmd[key][k])
                                tCmd[key][k] = CombineValueLists(
                                    tCmd[key][k], dCmd[key][k], parametersLines, paramValueMap, device)
                    else:
                        if tCmd[key] != dCmd[key]:
                            tCmd[key] = ConvertToString(tCmd[key])
                            dCmd[key] = ConvertToString(dCmd[key])
                            tCmd[key] = CombineValueLists(
                                tCmd[key], dCmd[key], parametersLines, paramValueMap, device)
            oldtoNewLineMap[tCmd[LINENUM]] = lineNum
            tCmd[LINENUM] = lineNum
            newDeviceLines.append(lineNum)
            lineNum += 1
            combinedCmds.append(tCmd)
        else:
            raise TypeError("Error in combining statements for route policies")
    return combinedCmds, lineNum


def TemplateGenerator(block1Alignment, block2Alignment, lineMatchings, parametersLines, device, empty):
    """ Given the alignment and line matchings the function returns the merged terms."""

    oldtoNewLineMap = {}
    newDeviceLines = list()
    mergedTerms = list()
    lineNum = 0
    j = 0
    if len(block1Alignment) != len(block2Alignment):
        raise ValueError("Something is wrong in alignment!!!")
    else:
        for i, v in enumerate(block1Alignment):
            if v == []:
                if block2Alignment[i] != []:
                    term = copy.deepcopy(block2Alignment[i])
                    term.action[LINENUM] = lineNum
                    newDeviceLines.append(lineNum)
                    lineNum += 1
                    for cmd in term.guardCmds:
                        cmd[LINENUM] = lineNum
                        newDeviceLines.append(lineNum)
                        lineNum += 1
                    for cmd in term.trueCmds:
                        cmd[LINENUM] = lineNum
                        newDeviceLines.append(lineNum)
                        lineNum += 1
                    mergedTerms.append(term)
            else:
                if block2Alignment[i] == []:
                    term = copy.deepcopy(v)
                    oldtoNewLineMap[term.action[LINENUM]] = lineNum
                    term.action[LINENUM] = lineNum
                    lineNum += 1
                    for cmd in term.guardCmds:
                        oldtoNewLineMap[cmd[LINENUM]] = lineNum
                        cmd[LINENUM] = lineNum
                        lineNum += 1
                    for cmd in term.trueCmds:
                        oldtoNewLineMap[cmd[LINENUM]] = lineNum
                        cmd[LINENUM] = lineNum
                        lineNum += 1
                    mergedTerms.append(term)
                else:
                    term = copy.deepcopy(v)
                    oldtoNewLineMap[term.action[LINENUM]] = lineNum
                    term.action[LINENUM] = lineNum
                    newDeviceLines.append(lineNum)
                    lineNum += 1
                    term.guardCmds, lineNum = MergeCmds(
                        term.guardCmds, block2Alignment[i].guardCmds, lineNum, parametersLines, lineMatchings[j][0], oldtoNewLineMap, newDeviceLines, device)
                    term.trueCmds, lineNum = MergeCmds(
                        term.trueCmds, block2Alignment[i].trueCmds, lineNum, parametersLines, lineMatchings[j][1], oldtoNewLineMap, newDeviceLines, device)
                    j += 1
                    mergedTerms.append(term)
    parametersLines.remapLineNumbers(oldtoNewLineMap)
    parametersLines.lineMapping[device] = newDeviceLines
    return mergedTerms


def ModifyEraseHelper(cmd, replaceWith, eraseList):
    for key in cmd:
        if isinstance(cmd[key], dict):
            # Assuming only depth of 1.
            for k in cmd[key]:
                if isinstance(cmd[key][k], list):
                    newList = []
                    for v in cmd[key][k]:
                        if v in eraseList:
                            newList.append(replaceWith)
                        else:
                            newList.append(v)
                    cmd[key][k] = newList
        elif isinstance(cmd[key], list):
            newList = []
            for v in cmd[key]:
                if v in eraseList:
                    newList.append(replaceWith)
                else:
                    newList.append(v)
            cmd[key] = newList
    return cmd


def ModifyErase(metaTemplate, parametersLines, replaceWith, eraseList):
    """ Replaces all the parameters in the eraselist with replacewith in the metatemplate."""
    for block in metaTemplate.blocks:
        newGuard = []
        for cmd in block.guardCmds:
            newGuard.append(ModifyEraseHelper(cmd, replaceWith, eraseList))
        block.guardCmds = newGuard
        newTrue = []
        for cmd in block.trueCmds:
            newTrue.append(ModifyEraseHelper(cmd, replaceWith, eraseList))
        block.trueCmds = newTrue

    for device in parametersLines.parameters:
        value = None
        found = False
        for removals in eraseList:
            if removals in parametersLines.parameters[device]:
                found = True
                value = parametersLines.parameters[device][removals]
                parametersLines.parameters[device].pop(removals)
        if found or replaceWith in parametersLines.parameters[device]:
            parametersLines.parameters[device][replaceWith] = parametersLines.parameters[device].get(
                replaceWith, value)


def RemapParametersHelper(cmd, paramValueMap, oldtoNewParamMap, count):
    for key in cmd:
        if isinstance(cmd[key], dict):
            # Assuming only depth of 1.
            for k in cmd[key]:
                if isinstance(cmd[key][k], list):
                    newList = []
                    for v in cmd[key][k]:
                        if v in paramValueMap:
                            if v in oldtoNewParamMap:
                                newList.append(oldtoNewParamMap[v])
                            else:
                                oldtoNewParamMap[v] = "P"+str(count)
                                newList.append("P"+str(count))
                                count += 1
                        else:
                            newList.append(v)
                    cmd[key][k] = newList
        elif isinstance(cmd[key], list):
            newList = []
            for v in cmd[key]:
                if v in paramValueMap:
                    if v in oldtoNewParamMap:
                        newList.append(oldtoNewParamMap[v])
                    else:
                        oldtoNewParamMap[v] = "P"+str(count)
                        newList.append("P"+str(count))
                        count += 1
                else:
                    newList.append(v)
            cmd[key] = newList
    return cmd, count


def RemapParameters(metaTemplate, parametersLines):
    """Makes a pass over the metatemplate to re-number the parameters from the first line."""
    paramValueMap = parametersLines.parameterDistribution()
    oldtoNewParamMap = {}
    count = 0
    for block in metaTemplate.blocks:
        newGuard = []
        for cmd in block.guardCmds:
            newcmd, count = RemapParametersHelper(
                cmd, paramValueMap, oldtoNewParamMap, count)
            newGuard.append(newcmd)
        block.guardCmds = newGuard
        newTrue = []
        for cmd in block.trueCmds:
            newcmd, count = RemapParametersHelper(
                cmd, paramValueMap, oldtoNewParamMap, count)
            newTrue.append(newcmd)
        block.trueCmds = newTrue
    parametersLines.counter = count
    for device in parametersLines.parameters:
        newMap = {}
        for key, value in parametersLines.parameters[device].items():
            if key in oldtoNewParamMap:
                newMap[oldtoNewParamMap[key]] = value
            else:
                newMap[key] = value
        parametersLines.parameters[device] = newMap
    for device in parametersLines.lineMapping:
        parametersLines.lineMapping[device].sort()


def MinimizeParametersHelper(cmd, lineParamMap, paramValueMap):
    for key in cmd:
        if isinstance(cmd[key], dict):
            # Assuming only depth of 1.
            for k in cmd[key]:
                if isinstance(cmd[key][k], list):
                    for v in cmd[key][k]:
                        if v in paramValueMap:
                            lineParamMap.setdefault(cmd[LINENUM], set()).add(v)
        elif isinstance(cmd[key], list):
            for v in cmd[key]:
                if v in paramValueMap:
                    lineParamMap.setdefault(cmd[LINENUM], set()).add(v)


def MinimizeParameters(metaTemplate, parametersLines, empty):
    """ Reduces the number of parameters required by replacing different parameters with a single parameter if they agree on all devices."""
    paramValueMap = parametersLines.parameterDistribution()
    lineParamMap = {}
    for block in metaTemplate.blocks:
        for cmd in block.guardCmds:
            MinimizeParametersHelper(cmd, lineParamMap, paramValueMap)
        for cmd in block.trueCmds:
            MinimizeParametersHelper(cmd, lineParamMap, paramValueMap)
    for device in parametersLines.lineMapping:
        myParam = set()
        for lineNumber in parametersLines.lineMapping[device]:
            if lineNumber in lineParamMap:
                myParam.update(lineParamMap.get(lineNumber))
        extraParams = set(parametersLines.parameters[device].keys()) - myParam
        [parametersLines.parameters[device].pop(
            extra, None) for extra in extraParams]

    common = parametersLines.commonValueParams()
    for x in common:
        ModifyErase(metaTemplate, parametersLines, x[0], x[1:])
    if len(metaTemplate.blocks[-1].trueCmds) > 0:
        totalLines = metaTemplate.blocks[-1].trueCmds[-1][LINENUM]
    elif len(metaTemplate.blocks[-1].guardCmds) > 0:
        totalLines = metaTemplate.blocks[-1].guardCmds[-1][LINENUM]
    else:
        totalLines = metaTemplate.blocks[-1].action[LINENUM]
    parametersLines.predicateGenerator(totalLines)
    # groupAndSortPredicates(metaTemplate)
    RemapParameters(metaTemplate, parametersLines)


def FormatGuardCmds(guard, linePredicateMap):
    """
    Outputs the metatemplate in the CISCO IOS Format from the Batfish vendor independent model.
    """
    output = ""
    htmlCmds = list()
    for cmd in guard:
        tmp = {}
        tmp[0] = linePredicateMap.get(cmd[LINENUM])
        tmp[1] = ""
        tmp[2] = "match"
        if "MatchPrefixSet" in cmd["class"] or "MatchPrefix6Set" in cmd["class"]:
            #TODO: Handle case ExplicitPrefixSet
            if "NamedPrefixSet" in cmd["prefixSet"]["class"] or "NamedPrefix6Set" in cmd["prefixSet"]["class"]:
                ip = "ip" if "NamedPrefixSet" in cmd["prefixSet"]["class"] else "ipv6"
                output += "{:<3}: {:<3}: \tmatch {} address prefix-list {}\n".format(str(
                    cmd[LINENUM]), linePredicateMap.get(cmd[LINENUM]), ip, str(cmd["prefixSet"]["name"]))
                tmp[3] = ip + " address prefix-list"
                tmp[4] = str(cmd["prefixSet"]["name"])
                tmp[5] = ""
            else:
                output += "{:<3}: {:<3}: \tmatch UNKNOWN_PrefixSet\n".format(
                    str(cmd[LINENUM]), linePredicateMap.get(cmd[LINENUM]))
        elif "MatchIpAccessList" in cmd["class"]:
            if "List" in cmd:
                output += "{:<3}: {:<3}: \tmatch ip address {}\n".format(
                    str(cmd[LINENUM]), linePredicateMap.get(cmd[LINENUM]), str(cmd["list"]))
                tmp[3] = "ip address"
                tmp[5] = ""
                tmp[4] = str(cmd["list"])
            else:
                output += "{:<3}: {:<3}: \tmatch UNKNOWN_IPACL\n".format(
                    str(cmd[LINENUM]), linePredicateMap.get(cmd[LINENUM]))
        elif "MatchCommunitySet" in cmd["class"] or "MatchCommunities" in cmd["class"]:
            if "expr" in cmd and "NamedCommunitySet" in cmd["expr"]["class"]:
                output += "{:<3}: {:<3}: \tmatch community {}\n".format(
                    str(cmd[LINENUM]), linePredicateMap.get(cmd[LINENUM]), str(cmd["expr"]["name"]))
                tmp[3] = "community"
                tmp[5] = ""
                tmp[4] = str(cmd["expr"]["name"])
            # Juniper version but printed in Cisco format    
            elif "communitySetMatchExpr" in cmd:
                output += "{:<3}: {:<3}: \tmatch community {}\n".format(
                    str(cmd[LINENUM]), linePredicateMap.get(cmd[LINENUM]), str(cmd["communitySetMatchExpr"]["name"]))
                tmp[3] = "community"
                tmp[5] = ""
                tmp[4] = str(cmd["communitySetMatchExpr"]["name"])
            else:
                output += "{:<3}: {:<3}: \tmatch UNKNOWN_Community\n".format(
                    str(cmd[LINENUM]), linePredicateMap.get(cmd[LINENUM]))
        elif "MatchAsPath" in cmd["class"]:
            if "NamedAsPathSet" in cmd["expr"]["class"]:
                output += "{:<3}: {:<3}: \tmatch as-path {}\n".format(
                    str(cmd[LINENUM]), linePredicateMap.get(cmd[LINENUM]), str(cmd["expr"]["name"]))
                tmp[3] = "as-path"
                tmp[5] = ""
                tmp[4] = str(cmd["expr"]["name"])
            else:
                output += "{:<3}: {:<3}: \tmatch UNKNOWN_ASPath\n".format(
                    str(cmd[LINENUM]), linePredicateMap.get(cmd[LINENUM]))
        elif "MatchColor" in cmd['class']:
            output += "{:<3}: {:<3}: \tmatch color {}\n".format(
                str(cmd[LINENUM]), linePredicateMap.get(cmd[LINENUM]), str(cmd["color"]))
            tmp[3] = "color"
            tmp[4] = str(cmd['color'])
            tmp[5] = ""
        elif "MatchProtocol" in cmd['class']:
            output += "{:<3}: {:<3}: \tmatch protocol {}\n".format(
                str(cmd[LINENUM]), linePredicateMap.get(cmd[LINENUM]), str(cmd["protocols"]))
            tmp[3] = "protocol"
            tmp[4] = str(cmd['protocols'])
            tmp[5] = ""
        else:
            output += "{:<3}: {:<3}: \tmatch UNKNOWN\n".format(
                str(cmd[LINENUM]), linePredicateMap.get(cmd[LINENUM]))
        if 3 not in tmp:
            tmp[3] = "UNKNOWN"
            tmp[4] = ""
            tmp[5] = ""
        htmlCmds.append(tmp)
    return output, htmlCmds


def FormatTrueCmds(trueCmds, linePredicateMap):
    """
    Outputs the metatemplate in the CISCO IOS Format from the Batfish vendor independent model.
    """
    output = ""
    htmlCmds = list()
    for setStmt in trueCmds:
        tmp = {}
        tmp[0] = linePredicateMap.get(setStmt[LINENUM])
        tmp[1] = ""
        tmp[2] = "set"
        if "SetWeight" in setStmt["class"]:
            if "value" in setStmt["weight"] and "LiteralInt" in setStmt["weight"]["class"]:
                output += "{:<3}: {:<3}: \tset weight {}\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), str(setStmt["weight"]["value"]))
                tmp[3] = "weight"
                tmp[5] = ""
                tmp[4] = str(setStmt["weight"]["value"])
            else:
                output += "{:<3}: {:<3}: \tset weight UNKNOWN\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]))
        elif "PrependAsPath" in setStmt["class"]:
            if "list" in setStmt["expr"]:
                output += "{:<3}: {:<3}: \tset as-path prepend {}\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), str(setStmt["expr"]["list"]))
                tmp[3] = "as-path prepemd"
                tmp[5] = ""
                tmp[4] = str(setStmt["expr"]["list"])
            else:
                output += "{:<3}: {:<3}: \tset as-path prepend UNKNOWN\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]))
        elif "DeleteCommunity" in setStmt["class"]:
            if "NamedCommunitySet" in setStmt["expr"]["class"]:
                output += "{:<3}: {:<3}: \tset comm-list {} delete\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), str(setStmt["expr"]["name"]))
                tmp[3] = "comm-list"
                tmp[4] = str(setStmt["expr"]["name"])
                tmp[5] = "delete"
            else:
                output += "{:<3}: {:<3}: \tset comm-list UNKNOWN\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]))
        elif "SetCommunity" in setStmt["class"]:
            if "LiteralCommunitySet" in setStmt["expr"]["class"]:
                output += "{:<3}: {:<3}: \tset community {}\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), str(setStmt["expr"]["communities"]))
                tmp[3] = "community"
                tmp[5] = ""
                tmp[4] = str(setStmt["expr"]["communities"])
            else:
                output += "{:<3}: {:<3}: \tset community UNKNOWN(Cisco)\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]))
        elif "SetCommunities" in setStmt["class"]:
            #Juniper version of communities but printed in Cisco style.
            if "CommunitySetReference" in setStmt["communitySetExpr"]["class"]:
                tmp[3] = "community"
                tmp[5] = ""
                tmp[4] = str(setStmt["communitySetExpr"]["name"])
                output += "{:<3}: {:<3}: \tset community {}\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), tmp[4])
            elif "CommunitySetUnion" in setStmt["communitySetExpr"]["class"]:
                tmp[3] = "community"
                tmp[4] = str(setStmt["communitySetExpr"]["name"])
                tmp[5] = "additive" 
                output += "{:<3}: {:<3}: \tset community {} additive\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), tmp[4])
            elif "CommunitySetDifference" in setStmt["communitySetExpr"]["class"]:
                tmp[3] = "comm-list"
                tmp[4] = str(setStmt["communitySetExpr"]["name"])
                tmp[5] = "delete" 
                output += "{:<3}: {:<3}: \tset comm-list {} delete\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), tmp[4])
            else:
                output += "{:<3}: {:<3}: \tset community UNKNOWN (Juniper)\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]))
        elif "SetLocalPreference" in setStmt["class"]:
            if "LiteralLong" in setStmt["localPreference"]["class"]:
                output += "{:<3}: {:<3}: \tset local-preference {}\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), str(setStmt["localPreference"]["value"]))
                tmp[3] = "local-preference"
                tmp[5] = ""
                tmp[4] = str(setStmt["localPreference"]["value"])
            else:
                output += "{:<3}: {:<3}: \tset local-preference UNKNOWN\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]))
        elif "SetOrigin" in setStmt["class"]:
            if "LiteralOrigin" in setStmt["originType"]["class"]:
                output += "{:<3}: {:<3}: \tset origin {}\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), str(setStmt["originType"]["originType"]))
                tmp[3] = "origin"
                tmp[5] = ""
                tmp[4] = str(setStmt["originType"]["originType"])
            else:
                output += "{:<3}: {:<3}: \tset origin UNKNOWN\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]))
        elif "SetNextHop" in setStmt["class"]:
            if "IpNextHop" in setStmt["expr"]["class"]:
                output += "{:<3}: {:<3}: \tset ip next-hop {}\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), str(setStmt["expr"]["ips"]))
                tmp[3] = "ip next-hop"
                tmp[5] = ""
                tmp[4] = str(setStmt["expr"]["ips"])
            elif "PeerAddressNextHop" in setStmt["expr"]["class"]:
                output += "{:<3}: {:<3}: \tset ip next-hop peer-address\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]))
                tmp[3] = "ip next-hop"
                tmp[5] = ""
                tmp[4] = "peer-address"
            elif "SelfNextHop" in setStmt["expr"]["class"]:
                output += "{:<3}: {:<3}: \tset ip next-hop peer-address\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]))
                tmp[3] = "ip next-hop"
                tmp[5] = ""
                tmp[4] = "self"
            else:
                output += "{:<3}: {:<3}: \tset ip next-hop UNKNOWN\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]))
        elif "AddCommunity" in setStmt["class"]:
            if "LiteralCommunitySet" in setStmt["expr"]["class"]:
                output += "{:<3}: {:<3}: \tset community {} additive\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), str(setStmt["expr"]["communities"]))
                tmp[3] = "community"
                tmp[4] = str(setStmt["expr"]["communities"])
                tmp[5] = "additive"
            else:
                output += "{:<3}: {:<3}: \tset community UNKNOWN additive\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]))
        elif "SetMetric" in setStmt["class"]:
            if "IncrementMetric" in setStmt["metric"]["class"]:
                output += "{:<3}: {:<3}: \tset metric +{}\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), str(setStmt["metric"]["addend"]))
                tmp[3] = "metric"
                tmp[4] = "+"
                tmp[5] = str(setStmt["metric"]["addend"])
            elif "DecrementMetric" in setStmt["metric"]["class"]:
                output += "{:<3}: {:<3}: \tset metric -{}\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), str(setStmt["metric"]["subtrahend"]))
                tmp[3] = "metric"
                tmp[4] = "-"
                tmp[5] = str(setStmt["metric"]["subtrahend"])
            elif "LiteralLong" in setStmt["metric"]["class"]:
                output += "{:<3}: {:<3}: \tset metric {}\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]), str(setStmt["metric"]["value"]))
                tmp[3] = "metric"
                tmp[5] = ""
                tmp[4] = str(setStmt["metric"]["value"])
            else:
                output += "{:<3}: {:<3}: \tset metric UNKNOWN\n".format(str(
                    setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]))
        else:
            output += "{:<3}: {:<3}: \tset UNKNOWN\n".format(str(
                setStmt[LINENUM]), linePredicateMap.get(setStmt[LINENUM]))
        if 3 not in tmp:
            tmp[3] = "UNKNOWN"
            tmp[4] = ""
            tmp[5] = ""
        htmlCmds.append(tmp)
    return output, htmlCmds


def PrintTemplate(metaTemplate, parametersLines, outputDirectory, patternString, empty):
    """Produces the output meta template in Cisco IOS for the Route policies."""

    linePredicateMap = {}
    for predicate in parametersLines.predicates:
        for line in parametersLines.predicates[predicate]:
            linePredicateMap[line] = predicate
    outputMetaTemplate = ""
    htmlLines = list()
    seq = 10
    for block in metaTemplate.blocks:
        tmp = {}
        tmp[0] = linePredicateMap.get(block.action[LINENUM])
        tmp[1] = "route-map"
        tmp[2] = patternString
        tmp[3] = block.action["type"]
        tmp[4] = str(seq)
        tmp[5] = ""
        seq += 10
        htmlLines.append(tmp)
        outputMetaTemplate += "{:<3}: {:<3}: route-map {} {} {}\n".format(str(
            block.action[LINENUM]), tmp[0], tmp[2], tmp[3], tmp[4])
        output, htmlCmds = FormatGuardCmds(block.guardCmds, linePredicateMap)
        outputMetaTemplate += output
        htmlLines.extend(htmlCmds)
        output, htmlCmds = FormatTrueCmds(block.trueCmds, linePredicateMap)
        outputMetaTemplate += output
        htmlLines.extend(htmlCmds)
    outputMetaTemplate, parameterTable = parametersLines.formatGroups(
        outputMetaTemplate)
    singleParamDifferences = parametersLines.singleParamQuestions()
    spuriousParamDifferences = parametersLines.spuriousParamQuestions()

    finalPath = outputDirectory + os.path.sep + patternString
    if parametersLines.counter > 0:
        commonFunctions.createFolder(finalPath)
        # with open(finalPath + os.path.sep + "parameters.json", "w") as write_param:
        #     json.dump(parameterTable, write_param, sort_keys=True, indent=2)
        df = pd.DataFrame(parameterTable)
        df.to_csv(finalPath + os.path.sep + "parameters.csv")

    if len(parametersLines.groupsList) > 1 or singleParamDifferences != "" or spuriousParamDifferences != "":
        commonFunctions.createFolder(finalPath)
        outputMetaTemplate = "\n\nWe have found the following differences in this PrefixList\n" + \
            singleParamDifferences + "\n" + spuriousParamDifferences + outputMetaTemplate + "\n"
        commonFunctions.generateHTML(htmlLines, parametersLines, finalPath)
        return outputMetaTemplate, singleParamDifferences, spuriousParamDifferences
    else:
        if parametersLines.counter > 0:
            commonFunctions.createFolder(finalPath)
            with open(finalPath + os.path.sep + "output.txt", "w") as write_file:
                write_file.write(outputMetaTemplate)
            commonFunctions.generateHTML(htmlLines, parametersLines, finalPath)
        return None, None, None