# ------------------------------------------------------
# output.c

import os

MINSHORT = -32768
MAXTABLE = 32767

class OutputBase:
    def __init__(self, bison):
        # By copying the dictionary we ensure no mixing to data
        # between different output methods
        self.__dict__.update(vars(bison).copy())
        return

    def fatal(self, msg):
        banner = self.options.get('input', self.program_name)
        raise SystemExit('%s: fatal error: %s\n' % (banner, msg))

    def output(self, outfile):
        self.output_token_defines(outfile.write)
        self.output_token_translations(outfile.write)
        self.output_gram(outfile.write)
        self.output_rule_data(outfile.write)
        self.output_actions(outfile.write)
        self.output_defines(outfile.write)
        return

    def output_token_defines(self, write):
        raise NotImplementedError('must override')

    def output_token_translations(self, write):
        raise NotImplementedError('must override')
    
    def output_gram(self, write):
        raise NotImplementedError('must override')

    def output_rule_data(self, write):
        raise NotImplementedError('must override')

    def output_actions(self, write):
        """
        compute and output yydefact, yydefgoto, yypact, yypgoto, yytable and yycheck.
        """
        self.nvectors = self.nstates + self.nvars
        self.froms = [None]*self.nvectors  # list of lists
        self.tos = [None]*self.nvectors    # list of lists
        self.tally = [0]*self.nvectors
        self.width = [0]*self.nvectors
    
        self.token_actions(write)
        
        self.goto_actions(write)
        
        self.sort_actions()
        self.pack_table()
        self.output_base(write)
        self.output_table(write)
        self.output_check(write)
        return
    
    # Helper function for token_actions()
    def action_row(self, state):
        """
        Decide what to do for each type of token if seen as the lookahead token in
        specified state. The value returned is used as the default action (yydefact)
        for the state. In addition, actrow is filled with what to do for each kind of
        token, index by symbol number, with zero meaning do the default action.
        The value MINSHORT, a very negative number, means this situation
        is an error.  The parser recognizes this value specially.

        This is where conflicts are resolved.  The loop over lookahead rules
        considered lower-numbered rules last, and the last rule considered that likes
        a token gets to handle it.
        """
        actrow = [0]*self.ntokens
        default_rule = 0
        nodefault = 0

        reduction = self.reduction_table[state]
        if reduction and reduction.rules:
            # loop over all the rules available here which require lookahead
            m = self.lookaheads[state]
            n = self.lookaheads[state + 1]
            for i in range(n-1, m-1, -1):
                rule = -self.LAruleno[i]
                # and find each token which the rule finds acceptable to come next
                for j in range(self.ntokens):
                    # and record this rule as the rule to use if that token follows
                    if self.LA[i][j]:
                        actrow[j] = rule

        # now see which tokens are allowed for shifts in this state.
        # For them, record the shift as the thing to do. So shift is preferred to reduce.
        shift = self.shift_table[state]
        if shift:
            for shift_state in shift.shifts:
                if not shift_state: continue

                symbol = self.accessing_symbol[shift_state]
                if symbol >= self.ntokens: break        # ISVAR(symbol)

                actrow[symbol] = shift_state
                # do not user any default reduction if there is a shift for error
                if symbol == self.error_token_number:
                    nodefault = 1
                    
        # See which tokens are an explicit error in this state (due to nonassoc).
        # For them, record MINSHORT as the action.
        errors = self.err_table[state]
        if errors:
            for symbol in errors:
                actrow[symbol] = MINSHORT
                
        # now find the most common reduction and make it the default action for this state.
        if reduction and reduction.rules and not nodefault:
            if self.consistent[state]:
                default_rule = reduction.rules[0]
            else:
                max = 0
                for i in range(m, n):
                    rule = -self.LAruleno[i]
                    count = reduce(lambda a, b, r=rule: a + (b == r), actrow, 0)
                    if count > max:
                        max = count
                        default_rule = rule

                # actions which match the default are replaced with zero,
                # which means "use the default"
                if max:
                    for j in range(self.ntokens):
                        if actrow[j] == default_rule:
                            actrow[j] = 0
                    default_rule = -default_rule
                    
        # If have no default rule, the default is an error.
        # So replace any action which says "error" with "use default".
        if not default_rule:
            for j in range(self.ntokens):
                if actrow[j] == MINSHORT:
                    actrow[j] = 0

        # save_row(state)
        froms = []
        tos = []
        for i in range(self.ntokens):
            if actrow[i]:
                froms.append(i)
                tos.append(actrow[i])

        self.froms[state] = froms
        self.tos[state] = tos
        if froms:
            self.tally[state] = len(froms)
            self.width[state] = froms[-1] - froms[0] + 1

        return default_rule
        
    # Helper function for goto_actions()
    def default_goto(self, symbol):
        m = self.goto_map[symbol]
        n = self.goto_map[symbol + 1]
        
        state_count = [0]*self.nstates

        default_state = -1

        if m != n:
            for i in range(m, n):
                state = self.to_state[i]
                state_count[state] = state_count[state] + 1
            
            max = 0
            for i in range(self.nstates):
                if state_count[i] > max:
                    max = state_count[i]
                    default_state = i
                    
        # save_column(symbol, default_state)
        froms = []
        tos = []
        for i in range(m, n):
            if (self.to_state[i] != default_state):
                froms.append(self.from_state[i])
                tos.append(self.to_state[i])
                
        symno = symbol - self.ntokens + self.nstates
        count = len(froms)
        self.tally[symno] = count
        self.width[symno] = count and (froms[-1] - froms[0] + 1)
        self.froms[symno] = froms
        self.tos[symno] = tos

        return default_state
    
    # The next few functions decide how to pack and the
    # actions and gotos information into yytable

    def sort_actions(self):
        self.order = [0]*self.nvectors
        self.nentries = 0
        
        for i in range(self.nvectors):
            if self.tally[i]:
                t = self.tally[i]
                w = self.width[i]
                j = self.nentries - 1
                
                while (j >= 0 and self.width[self.order[j]] < w):
                    j = j - 1
                    
                while (j >= 0
                       and self.width[self.order[j]] < w
                       and self.tally[self.order[j]] < t):
                    j = j - 1
                    
                for k in range(self.nentries - 1, j, -1):
                    self.order[k + 1] = self.order[k]
                    
                self.order[j + 1] = i
                self.nentries = self.nentries + 1
                
        return
    
    def pack_table(self):
        self.base = [MINSHORT]*self.nvectors
        self.pos = [0]*self.nentries
        self.table = [0]*MAXTABLE
        self.check = [-1]*MAXTABLE
        
        self.lowzero = 0
        self.high = 0
        
        for i in range(self.nentries):
            state = self.matching_state(i)
            
            if state < 0:
                place = self.pack_vector(i)
            else:
                place = self.base[state]
                
            self.pos[i] = place
            self.base[self.order[i]] = place
            
        del self.froms
        del self.tos
        del self.pos
        
    def matching_state(self, vector):
        i = self.order[vector]
        if i >= self.nstates:
            return -1
        
        t = self.tally[i]
        w = self.width[i]
        
        for prev in range(vector - 1, -1, -1):
            j = self.order[prev]
            if self.width[j] != w or self.tally[j] != t:
                return -1

            for k in range(t):
                if (self.tos[j][k] != self.tos[i][k]
                    or self.froms[j][k] != self.froms[i][k]):
                    break
            else:
                return j
        return -1

    def pack_vector(self, vector):
        i = self.order[vector]
        t = self.tally[i]
        
        if t == 0:
            self.fatal('pack_vector')
        
        froms = self.froms[i]
        tos = self.tos[i]
        
        for j in range(self.lowzero - froms[0], MAXTABLE):
            ok = 1
            for k in range(t):
                loc = j + froms[k]
                if loc > MAXTABLE:
                    self.fatal("maximum table size (%d) exceeded" % MAXTABLE)
                if self.table[loc] != 0:
                    ok = 0
                    break
            else:
                for k in range(vector):
                    if self.pos[k] == j:
                        ok = 0
                        break
                    
            if ok:
                for k in range(t):
                    loc = j + froms[k]
                    self.table[loc] = tos[k]
                    self.check[loc] = froms[k]

                while self.table[self.lowzero] != 0:
                    self.lowzero = self.lowzero + 1
                    
                if loc > self.high:
                    self.high = loc
                    
                return j
            
        self.fatal('pack_vector')
        return