import random
import re  # Used to build a content unit's tree expression
import json  # Used to parse JSON grammar file generated by Reductionist
import pickle  # Used to serialize the repetition-penalties dictionary, for persistence across generation instances
import marisa_trie  # Used to load a trie data structure efficiently storing all the paths through the grammar


class Productionist(object):
    """A system that generates text outputs at runtime, on the fly.

    Objects of this class operate over an tagged grammar to satisfy targeted content requests originating
    from a game engine. As such, it can be thought of as an interface between the game engine and an
    authored Expressionist grammar.
    """

    def __init__(self, content_bundle_name, content_bundle_directory, probabilistic_mode=False,
                 repetition_penalty_mode=True, terse_mode=False, verbosity=1, seed=None):
        """Initialize a Productionist object."""
        # Set the random seed, if one was specified
        if seed is not None:
            random.seed(seed)
        self.content_bundle = content_bundle_name
        # If verbosity is 0, no information will be printed out during processing; if 1, information
        # about how far along Productionist is in its general processing will be printed out; if 2,
        # information about the paths taken through the grammar to generate content will also be printed
        self.verbosity = verbosity
        # Grab the path to the directory with the content bundle
        if content_bundle_directory[-1] == '/':  # Strip off trailing slash, if applicable
            content_bundle_directory = content_bundle_directory[:-1]
        # Hold onto that path, for reference
        self._grammar_file_location = content_bundle_directory
        # Build the grammar in memory, as an object of the Grammar class, which is defined below
        self.grammar = self._load_grammar(
            grammar_file_location='{path}/{bundle_name}.grammar'.format(
                path=content_bundle_directory, bundle_name=content_bundle_name
            )
        )
        # If applicable, load the trie file at the specified location; this file contains a data structure
        # (a 'trie') that efficiently stores all the semantically meaningful paths through the
        # grammar; this file will have been generated by Reductionist
        try:
            self.trie = self._load_trie(
                trie_file_location='{path}/{bundle_name}.marisa'.format(
                    path=content_bundle_directory, bundle_name=content_bundle_name
                )
            )
        except IOError:
            self.trie = None
        # Also load a set of expressible meanings -- these pertain to each of the possible tagsets that
        # generated content may come packaged with, and each expressible meaning bundles its associated
        # tagset with recipes for producing that content (in the form of paths through the grammar)
        self.expressible_meanings = self._load_expressible_meanings(
            expressible_meanings_file_location='{path}/{bundle_name}.meanings'.format(
                path=content_bundle_directory, bundle_name=content_bundle_name
            )
        )
        # In probabilistic mode, Productionist will select which expressible meanings to target
        # probabilistically, by fitting a probability distribution to the candidates using the scores
        # given to them; otherwise, Productionist will simply pick the highest scoring one
        self.probabilistic_mode = probabilistic_mode
        # In repetition-penalty mode, semantically meaningless rules ("wildcard rules") that have been
        # used to produce recently generated content are less likely to be selected again (with a decay
        # rate on the penalty for selecting them); we do this by maintaining a current penalty for each
        # rule that increases each time the rule is used and decays as the rule is not used
        self.repetition_penalty_mode = repetition_penalty_mode
        if repetition_penalty_mode:
            self.repetition_penalties = {
                str(symbol): 1.0 for symbol in self.grammar.nonterminal_symbols+self.grammar.terminal_symbols
            }
            if self.verbosity > 0:
                print "Initializing new repetitions dictionary..."
        else:
            self.repetition_penalties = {}
        # In terse mode, the system will favor production rules that may produce terser dialogue
        self.terse_mode = terse_mode
        # The remaining path holds all the semantically meaningful production rules that the system
        # is to execute as soon as they are encountered (between encountering these rules, the
        # system is free to select between wildcard production rules since that only result in
        # lexical/syntactic variation, i.e., not variation in the tags that are accumulated); this
        # attribute gets set by self._follow_recipe()
        self.remaining_path = []
        # The explicit path holds all the production rules that the system ended up executing
        # during generation (including ones that were selected as wildcard rules, which would thus not
        # be included in the remaining path); this is saved a record of the generation process that
        # produced a line, and is critically utilized to produce the bracketed expression for a line
        self.explicit_path_taken = []
        # Whether Productionist is currently targeting a particular expressible meaning, which means
        # that it cannot go down paths that would accumulate tags outside that meaning, or whether
        # it is generating example terminal results of expanding nonterminal symbols or executing
        # production rules, in which case every production rule becomes a wildcard rule
        self.targeting_meaning = True

    @property
    def scoring_modes_engaged(self):
        """Return whether any mode is engaged such that candidate production rules need to be scored."""
        return self.repetition_penalty_mode or self.terse_mode or self.grammar.unequal_rule_frequencies

    def _load_grammar(self, grammar_file_location):
        """Load the grammar specification from file and build and return a Grammar object for it."""
        if self.verbosity > 0:
            print "Loading grammar..."
        grammar_object = Grammar(grammar_file_location=grammar_file_location)
        return grammar_object

    def _load_trie(self, trie_file_location):
        """Load a trie from file (one containing the semantically meaningful paths through this grammar)."""
        if self.verbosity > 0:
            print "Loading trie..."
        trie = marisa_trie.Trie()
        trie.load(trie_file_location)
        return trie

    def _load_expressible_meanings(self, expressible_meanings_file_location):
        """Load a set of constructed expressible meanings from file."""
        if self.verbosity > 0:
            print "Loading expressible meanings..."
        expressible_meanings = []
        try:
            f = open(expressible_meanings_file_location, 'r')
        except IOError:
            raise Exception(
                "Cannot load expressible meanings -- there is no file located at '{filepath}'".format(
                    filepath=expressible_meanings_file_location
                )
            )
        id_to_tag = self.grammar.id_to_tag
        for line in f.readlines():
            meaning_id, all_paths_str, all_tags_str = line.strip('\n').split('\t')
            if self.trie:
                path_trie_keys = [int(path_trie_key) for path_trie_key in all_paths_str.split('|')]
                recipes = [self.trie.restore_key(path_trie_key) for path_trie_key in path_trie_keys]
            else:
                recipes = []
                for path_str in all_paths_str.split('|'):
                    recipes.append([int(rule_id) for rule_id in path_str.split(',')])
            tags = {id_to_tag[tag_id] for tag_id in all_tags_str.split(',')} if all_tags_str else set()
            expressible_meanings.append(
                ExpressibleMeaning(meaning_id=int(meaning_id), tags=tags, recipes=recipes)
            )
        expressible_meanings.sort(key=lambda em: em.id)
        return expressible_meanings

    def save_repetition_penalties_file(self):
        """Save a serialized version of the repetition-penalties dictionary, for use in any subsequent
        generation instances.
        """
        path_to_repetitions_file = '{content_bundle}.repetitions'.format(content_bundle=self.content_bundle)
        repetitions_file = open(path_to_repetitions_file, 'wb')
        pickle.dump(self.repetition_penalties, repetitions_file)
        repetitions_file.close()

    def furnish_example_terminal_expansion_of_nonterminal_symbol(self, nonterminal_symbol_name):
        """Furnish example text generated by terminally expanding the nonterminal symbol with the given name."""
        assert any(s for s in self.grammar.nonterminal_symbols if s.name == nonterminal_symbol_name), (
            "Error: There is no nonterminal symbol in {bundle}.grammar with the name {symbol_name}".format(
                bundle=self.content_bundle, symbol_name=nonterminal_symbol_name
            )
        )
        self.targeting_meaning = False  # All rules we encounter will be treated as wildcard rules
        targeted_symbol = next(s for s in self.grammar.nonterminal_symbols if s.name == nonterminal_symbol_name)
        # Terminally expand the symbol to generate text
        generated_text = self._terminally_expand_nonterminal_symbol(
            nonterminal_symbol=targeted_symbol, n_tabs_for_debug=0
        )
        # Package that up with all the associated metadata
        output = self._build_content_package(targeted_symbol=targeted_symbol, generated_text=generated_text)
        # Reset the targeting_meaning attribute
        self.targeting_meaning = True
        # Return the content package
        return output

    def furnish_example_terminal_result_of_executing_production_rule(self, production_rule_definition):
        """Furnish example text generated as the terminal result of executing the production rule with
        the given definition.
        """
        assert any(r for r in self.grammar.production_rules if str(r) == production_rule_definition), (
            "Error: There is no production rule in {bundle}.grammar with the definition {rule_def}".format(
                bundle=self.content_bundle, rule_def=production_rule_definition
            )
        )
        self.targeting_meaning = False  # All rules we encounter will be treated as wildcard rules
        targeted_rule = next(r for r in self.grammar.production_rules if str(r) == production_rule_definition)
        # Collect the terminal results of executing this rule
        generated_text = self._execute_production_rule(rule=targeted_rule, n_tabs_for_debug=0)
        # Package that up with all the associated metadata
        output = self._build_content_package(targeted_symbol=targeted_rule.head, generated_text=generated_text)
        # Reset the targeting_meaning attribute
        self.targeting_meaning = True
        # Return the content package
        return output

    def fulfill_content_request(self, content_request):
        """Satisfy the given content request."""
        # Find all of the expressible meanings that are satisficing, given the content request
        satisficing_expressible_meanings = self._compile_satisficing_expressible_meanings(
            content_request=content_request
        )
        # If there's no satisficing content requests, return None
        if not satisficing_expressible_meanings:
            return None
        # Select one of these to target for generation, either randomly or by using the scoring metric
        # given in the content request
        selected_expressible_meaning = self._select_expressible_meaning(
            candidates=satisficing_expressible_meanings, scoring_metric=content_request.scoring_metric
        )
        # Select one of the grammar paths associated with this expressible meaning
        selected_recipe = self._select_recipe_for_expressible_meaning(
            expressible_meaning=selected_expressible_meaning
        )
        # Execute that grammar path to produce the generated content satisfying the content request
        generated_text = self._follow_recipe(recipe=selected_recipe)
        # Package that up with all the associated metadata
        output = self._build_content_package(generated_text=generated_text, content_request=content_request)
        # Return the package
        return output

    def _build_content_package(self, generated_text, targeted_symbol=None, selected_recipe=None, content_request=None):
        """Furnish an object that packaged the generated text with its accumulated tags and other metadata."""
        # Collect all the tags attached to the symbols along the path we took -- these are the
        # tags that will come bundled with the generated content
        tags = set()
        for production_rule in self.explicit_path_taken:
            tags |= set(production_rule.tags)
        # Produce a bracketed expression specifying the specific path through the grammar that
        # produced this generated content (useful for debugging/authoring purposes); first, we'll
        # need to save a copy of the explicit path that we took through the grammar, since this
        # will be consumed as we build the bracketed expression
        explicit_path_taken = list(self.explicit_path_taken)
        if targeted_symbol:
            bracketed_expression = self._produce_bracketed_expression(symbol_to_start_from=targeted_symbol)
        else:
            bracketed_expression = self._produce_bracketed_expression()
        # Instantiate an Output object
        output = Output(
            text=generated_text,
            tags=tags,
            recipe=selected_recipe,
            explicit_grammar_path_taken=explicit_path_taken,
            bracketed_expression=bracketed_expression
        )
        # If repetition-penalty mode is engaged, penalize all the rules that we executed to produce
        # that content (so that they will be less likely to be used again) and decay the penalties
        # for all the other production rules in the grammar that we didn't execute this time around
        # if self.repetition_penalty_mode:
        #     self._update_repetition_penalties(explicit_path_taken=explicit_path_taken)
        # Lastly, if this content is meant to fulfill a content request, check to make sure that it does so
        if content_request:
            content_fulfills_the_request = (
                not (output.tags & content_request.must_not_have) and
                output.tags.issuperset(content_request.must_have)
            )
            assert content_fulfills_the_request, "The generated content unit does not satisfy the content request."
        return output

    def _compile_satisficing_expressible_meanings(self, content_request):
        """Compile all satisficing expressible meanings that are satisficing.

        In this case, 'satisficing' means that an expressible meaning has none of the
        'must not have' tags and all of the 'must have' tags that are specified in the
        content request.
        """
        satisficing_expressible_meanings = [
            em for em in self.expressible_meanings if
            not (em.tags & content_request.must_not_have) and em.tags.issuperset(content_request.must_have)
        ]
        # Make sure none of these have condition tags that are currently violated
        return satisficing_expressible_meanings

    def _select_expressible_meaning(self, candidates, scoring_metric):
        """Select an expressible meaning to target for generation."""
        if self.verbosity > 0:
            print "Selecting expressible meaning..."
        # If there's only one option, we can just select that right off and move on
        if len(candidates) == 1:
            selected_expressible_meaning = candidates[0]
        # If no scoring metric was provided, we can just randomly select a satisficing intermediate
        # representation as the one that we will target
        elif not scoring_metric:
            selected_expressible_meaning = random.choice(candidates)
        else:
            if self.verbosity > 0:
                print "Scoring expressible meanings..."
            # If a scoring metric *was* provided in the content request, use it to rank the satisficing
            # expressible meaning; first, we need to score each of the candidate intermediate
            # representations using the scoring metric
            # provided in the content request
            scores = {}
            for candidate in candidates:
                scores[candidate] = self._score_expressible_meaning(
                    expressible_meaning=candidate, scoring_metric=scoring_metric
                )
            # Check if any candidate even earned any points; if not, we can just pick randomly
            if not any(scores.values()):
                selected_expressible_meaning = random.choice(candidates)
            else:
                # Fit a probability distribution to the candidates
                probability_ranges = self._fit_probability_distribution_to_decision_candidates(scores=scores)
                # Pick a specific expressible meaning to target
                selected_expressible_meaning = self._select_candidate_given_probability_distribution(
                    probability_ranges=probability_ranges
                )
            if self.verbosity > 1:
                print "Derived the following scores for expressible meanings:"
                for candidate in scores:
                    print "\tEM{em_id}\t{score}".format(em_id=candidate.id, score=scores[candidate])
        return selected_expressible_meaning

    @staticmethod
    def _score_expressible_meaning(expressible_meaning, scoring_metric):
        """Score a candidate expressible meaning using the scoring metric provided in a content request."""
        score = 0
        for tag, weight in scoring_metric:
            if tag in expressible_meaning.tags:
                score += weight
        return score

    def _select_recipe_for_expressible_meaning(self, expressible_meaning):
        """Select one of the grammar paths associated with the given expressible meaning."""
        if self.verbosity > 0:
            if len(expressible_meaning.recipes) == 1:
                print "Selecting EM{em_id}'s sole recipe...".format(
                    em_id=self.expressible_meanings.index(expressible_meaning)
                )
            else:
                print "Selecting one of EM{em_id}'s {n} recipes...".format(
                    em_id=self.expressible_meanings.index(expressible_meaning),
                    n=len(expressible_meaning.recipes)
                )
        candidates = expressible_meaning.recipes
        # If there's only one option, we can just select that right off and move on
        if len(candidates) == 1:
            selected_recipe = candidates[0]
        # If no scoring mode is engaged, we can just select a path randomly
        elif not self.scoring_modes_engaged:
            selected_recipe = random.choice(candidates)
        else:
            # If it is engaged, we'll want to select a path that won't generate a lot of repetition; to
            # prevent repetition, we can score candidate paths according to the current repetition
            # penalties attached to the symbols in the production rules on the paths; first let's
            # compute a utility distribution over the candidate paths
            scores = {}
            for recipe in candidates:
                scores[recipe] = self._score_candidate_recipe(recipe=recipe)
            # Check if any candidate even earned any points; if not, we can just pick randomly
            if not any(scores.values()):
                selected_recipe = random.choice(candidates)
            else:
                # Next, fit a probability distribution to the utility distribution
                probability_ranges = self._fit_probability_distribution_to_decision_candidates(scores=scores)
                # Finally, select a path (using the probability distribution, if probabilistic mode is engaged)
                selected_recipe = self._select_candidate_given_probability_distribution(
                    probability_ranges=probability_ranges
                )
        return selected_recipe

    def _score_candidate_recipe(self, recipe):
        """Return a score for the given recipe according to the scores for the production rules on its path."""
        # Ground out the rule references in the recipe to form a list of actual ProductionRule
        # objects; note: if there's no path string, that means that the selected path is one that
        # doesn't pass through any symbols with tags; in this case, Productionist can just select
        # between production rules that are not semantically meaningful until it's ground out into
        # a terminal expansion
        path = [self.grammar.production_rules[int(rule_id)] for rule_id in recipe.path.split(',')]
        score = sum(self._score_candidate_production_rule(rule) for rule in path)
        return score

    def _score_candidate_production_rule(self, production_rule):
        """Return a score for the given production rule.

        The score for this rule will be calculated according to its expansion-control tags (application
        frequency and usage constraint) and, if applicable, the current repetition penalties of the symbols
        symbols in its body (if repetition-penalty mode is engaged) and the number and length of symbols in
        its body (if terse mode is engaged).
        """
        score = 1.0
        # If applicable, adjust score according to repetition penalties and terseness
        for symbol in production_rule.body:
            if self.repetition_penalty_mode:
                score *= self.repetition_penalties[str(symbol)]
            if self.terse_mode:
                if type(symbol) == unicode:
                    score /= len(symbol)
                else:
                    # Need more testing here, and the divisor should be a config constant -- idea is to penalize
                    # longer sentence templates so as to avoid a local-optimum situation; it does this by dividing
                    # the score in half for every nonterminal symbol on the rule's right-hand side
                    score /= 2
        # Finally, adjust score according to the application frequency associated with this rule; specifically,
        # multiply the score by the rule's frequency score multiplier (which will be 1.0 or less)
        score *= production_rule.frequency_score_multiplier
        return score

    def _follow_recipe(self, recipe):
        """Follow the given recipe to generate the desired text content."""
        # Ground out the rule references in the recipe to form a list of actual ProductionRule
        # objects; note: if this is an empty list, that means that the selected path is one that
        # doesn't pass through any symbols with tags; in this case, Productionist can just randomly
        # select production rules that are not semantically meaningful until it's ground out into
        # a terminal expansion
        path = [self.grammar.production_rules[int(rule_id)] for rule_id in recipe.path.split(',')]
        # Keep this list handy as the list of remaining rules to execute -- we'll
        # be consuming this as we proceed
        self.remaining_path = list(path)
        # Keep track of all the rules we ended up firing for this path, including our choices
        # for wildcards -- we'll use this later to generate a bracketed expression specifying
        # how exactly the content unit was generated (for debugging/authoring purposes)
        self.explicit_path_taken = []
        # Execute the rules on the selected path in order to produce content expressing the
        # desired semantics, which are specifically the tags associated with the targeted
        # expressible meaning; this can be done by simply targeting the grammar's
        # start symbol and then only using rules on the targeted path for expansion (with
        # randomly chosen rules executed in each case of a wild card on the path)
        text = self._terminally_expand_nonterminal_symbol(
            nonterminal_symbol=self.grammar.start_symbol, n_tabs_for_debug=0
        )
        return text

    def _terminally_expand_nonterminal_symbol(self, nonterminal_symbol, n_tabs_for_debug):
        """Terminally expand the given symbol."""
        if self.verbosity > 1:
            print "{whitespace}Expanding nonterminal symbol [[{symbol_name}]]...".format(
                whitespace='  ' * n_tabs_for_debug,
                symbol_name=nonterminal_symbol.name
            )
        # Select a production rule
        if self.remaining_path and self.remaining_path[0] in nonterminal_symbol.production_rules:
            next_rule = self.remaining_path.pop(0)
        else:
            if self.verbosity > 1:
                print "{whitespace}Selecting wildcard rule...".format(whitespace='  ' * n_tabs_for_debug)
            next_rule = self._select_wildcard_production_rule(nonterminal_symbol=nonterminal_symbol)
        return self._execute_production_rule(rule=next_rule, n_tabs_for_debug=n_tabs_for_debug+1)

    def _select_wildcard_production_rule(self, nonterminal_symbol):
        """Select a wildcard production rule that will be used to expand the given nonterminal symbol.

        A "wildcard rule" is one that is not marked as being semantically meaningful, and is thus not
        included on the targeted path (stored as the 'remaining_path' attribute).
        """
        if self.targeting_meaning:
            candidate_wildcard_rules = [r for r in nonterminal_symbol.production_rules if not r.semantically_meaningful]
        else:
            candidate_wildcard_rules = list(nonterminal_symbol.production_rules)
        # If there's only choice, we can just select that and move on
        if len(candidate_wildcard_rules) == 1:
            selected_wildcard_rule = candidate_wildcard_rules[0]
        elif not self.scoring_modes_engaged:
            # If no scoring mode is engaged, we can simply randomly select a wildcard rule
            try:
                selected_wildcard_rule = random.choice(candidate_wildcard_rules)
            except IndexError:
                # There are no available production rules associated with this nonterminal symbol; this is an
                # authoring error, so let's report back accordingly
                raise Exception(
                    "AuthoringError: The nonterminal symbol {symbol_name}".format(symbol_name=nonterminal_symbol.name) +
                    " has no available wildcard rules, which means it cannot be expanded."
                )
        else:
            # Otherwise, we need to compute a utility distribution over the candidate wildcard rules
            scores = {}
            for rule in candidate_wildcard_rules:
                scores[rule] = self._score_candidate_production_rule(production_rule=rule)
            # Check if any candidate even earned any points; if not, we can just pick randomly
            if not any(scores.values()):
                selected_wildcard_rule = random.choice(candidate_wildcard_rules)
            else:
                # Next, fit a probability distribution to the utility distribution
                probability_ranges = self._fit_probability_distribution_to_decision_candidates(scores=scores)
                # Finally, select a wildcard rule (using the probability distribution, if probabilistic mode is engaged)
                selected_wildcard_rule = self._select_candidate_given_probability_distribution(
                    probability_ranges=probability_ranges
                )
        return selected_wildcard_rule

    def _execute_production_rule(self, rule, n_tabs_for_debug):
        """Execute the given production rule."""
        if self.verbosity > 1:
            print "{whitespace}Using production rule #{rule_id}: '{rule_spec}'".format(
                whitespace='  '*n_tabs_for_debug,
                rule_id=rule.id,
                rule_spec=str(rule)
            )
        # Add to our record of the explicit path we took the grammar to produce the
        # content we'll be sending back
        self.explicit_path_taken.append(rule)
        # Terminally expand this symbol
        terminally_expanded_symbols_in_this_rule_body = []
        for symbol in rule.body:
            if type(symbol) == unicode:  # Terminal symbol (no need to expand)
                terminally_expanded_symbols_in_this_rule_body.append(symbol)
            else:  # Nonterminal symbol, which means we have to expand it
                terminal_expansion_of_that_symbol = self._terminally_expand_nonterminal_symbol(
                    nonterminal_symbol=symbol, n_tabs_for_debug=n_tabs_for_debug + 1
                )
                terminally_expanded_symbols_in_this_rule_body.append(terminal_expansion_of_that_symbol)
        # Concatenate the results and return that string
        expansion_yielded_by_this_rule = ''.join(terminally_expanded_symbols_in_this_rule_body)
        return expansion_yielded_by_this_rule

    def _produce_bracketed_expression(self, symbol_to_start_from=None):
        """Produce a bracketed expression for a given grammar path.

        Bracketed expressions can be useful for debugging purposes, since they provide an explicit
        account of how a content unit was generated.
        """
        # Unless this content was produced by explicitly targeting a nonterminal symbol or
        # production rule (to support live authoring feedback), we'll want to start at the
        # grammar's start symbol
        if not symbol_to_start_from:
            symbol_to_start_from = self.grammar.start_symbol
        bracketed_expression = self._expand_nonterminal_symbol_to_produce_bracketed_expression_fragment(
            nonterminal_symbol=symbol_to_start_from
        )
        return bracketed_expression

    def _expand_nonterminal_symbol_to_produce_bracketed_expression_fragment(self, nonterminal_symbol):
        """Expand the given symbol to produce the next fragment of the bracketed expression being produced."""
        try:
            # Retrieve the next production rule
            next_rule = self.explicit_path_taken.pop(0)
            # Make sure that the next production rule on the path is one of this symbol's
            # rules; if it's not, throw an error
            assert next_rule in nonterminal_symbol.production_rules, (
                "Error: Expected rule #{rule_id} to be a production rule of the symbol {symbol_name}".format(
                    rule_id=next_rule.id,
                    symbol_name=nonterminal_symbol.name
                )
            )
            # Use the next production rule on the path to produce the next fragment of the bracketed expression
            return self._execute_production_rule_to_produce_bracketed_expression_fragment(rule=next_rule)
        except IndexError:
            # This nonterminal symbol currently has no production rules, so we'll just return the bracketed
            # expression
            bracketed_expression_fragment = "{head}{head_tags}[{results}]".format(
                head=nonterminal_symbol.name,
                head_tags=' <{tags}>'.format(tags=', '.join(t for t in nonterminal_symbol.tags)),
                results='[[{symbol}]]'.format(symbol=nonterminal_symbol.name)
            )
            return bracketed_expression_fragment

    def _execute_production_rule_to_produce_bracketed_expression_fragment(self, rule):
        """Execute the given production rule to produce the next fragment of the bracketed expression being produced."""
        # Terminally expand this symbol
        terminally_expanded_symbols_in_this_rule_body = []
        for symbol in rule.body:
            if type(symbol) == unicode:  # Terminal symbol (no need to expand)
                terminally_expanded_symbols_in_this_rule_body.append(
                    '"{terminal_symbol}"'.format(terminal_symbol=symbol)
                )
            else:  # Nonterminal symbol, which means we have to expand it
                terminal_expansion_of_that_symbol = (
                    self._expand_nonterminal_symbol_to_produce_bracketed_expression_fragment(nonterminal_symbol=symbol)
                )
                terminally_expanded_symbols_in_this_rule_body.append(terminal_expansion_of_that_symbol)
        # Concatenate the results and return that string
        bracketed_expression_fragment = "{head}{head_tags}[{results}]".format(
            head=rule.head.name,
            head_tags=' <{tags}>'.format(tags=', '.join(t for t in rule.head.tags)) if rule.head.tags else '',
            results=' + '.join(terminally_expanded_symbols_in_this_rule_body)
        )
        return bracketed_expression_fragment

    # def _update_repetition_penalties(self, explicit_path_taken):
    #     """Update repetition penalties to increase the penalties for symbols we just used and decay the penalty
    #     for all the symbols we did not use this time around.
    #     """
    #     symbols_used_this_time = set()
    #     for rule in explicit_path_taken:
    #         for symbol in rule.body:
    #             symbols_used_this_time.add(symbol)
    #     for symbol in self.grammar.nonterminal_symbols+self.grammar.terminal_symbols:
    #         if symbol in symbols_used_this_time:
    #             self.repetition_penalties[str(symbol)] *= REPETITION_PENALTY_MULTIPLIER
    #         else:
    #             self.repetition_penalties[str(symbol)] *= REPETITION_PENALTY_RECOVERY_RATE
    #         self.repetition_penalties[str(symbol)] = min(1.0, self.repetition_penalties[str(symbol)])

    @staticmethod
    def _fit_probability_distribution_to_decision_candidates(scores):
        """Return a dictionary mapping each of the decision candidates to a probability range."""
        candidates = scores.keys()
        # Determine the individual probabilities of each candidate
        individual_probabilities = {}
        sum_of_all_scores = float(sum(scores.values()))
        for candidate in candidates:
            probability = scores[candidate] / sum_of_all_scores
            individual_probabilities[candidate] = probability
        # Use those individual probabilities to associate each candidate with a specific
        # probability range, such that generating a random value between 0.0 and 1.0 will fall
        # into one and only one candidate's probability range
        probability_ranges = {}
        current_bound = 0.0
        for candidate in candidates:
            probability = individual_probabilities[candidate]
            probability_range_for_this_candidate = (current_bound, current_bound + probability)
            probability_ranges[candidate] = probability_range_for_this_candidate
            current_bound += probability
        # Make sure the last bound indeed extends to 1.0 (necessary because of float rounding issues)
        last_candidate_to_have_a_range_attributed = candidates[-1]
        probability_ranges[last_candidate_to_have_a_range_attributed] = (
            probability_ranges[last_candidate_to_have_a_range_attributed][0], 1.0
        )
        return probability_ranges

    def _select_candidate_given_probability_distribution(self, probability_ranges):
        """Return a selected decision candidate.

        If probabilistic mode is engaged, the system will probabilistically select; otherwise, it
        will simply return the highest scoring candidate.
        """
        if self.probabilistic_mode:
            x = random.random()
            selection = next(
                candidate for candidate in probability_ranges if
                probability_ranges[candidate][0] <= x <= probability_ranges[candidate][1]
            )
        else:  # Pick the highest-scoring one, i.e., the most probable one
            selection = max(
                probability_ranges,
                key=lambda candidate: probability_ranges[candidate][1]-probability_ranges[candidate][0]
            )
        return selection


class ExpressibleMeaning(object):
    """An 'expressible meaning' is a particular meaning (i.e., collection of tags), bundled with
    recipes (i.e., collection of compressed grammar paths) for generating content that will come
    with those tags.

    The recipes for generating the desired content are specified as compressed paths through the grammar,
    and they are reified as objects of the class Recipe, defined below.
    """

    def __init__(self, meaning_id, tags, recipes):
        """Initialize an ExpressibleMeaning object."""
        self.id = meaning_id
        # A set including all the tags associated with this expressible meaning; these can be thought
        # of as the semantics that are associated with all the paths through the grammar that this
        # expressible meaning indexes
        self.tags = tags
        # A list of the recipes for generating content that expresses the associated meaning; each is
        # represented as a compressed grammar path (i.e., one that, if its rules are executed in order,
        # will produce the exact set of tags associated with this expressible meaning)
        self.recipes = self._init_build_recipes(recipes=recipes)

    def __str__(self):
        """Return string representation."""
        return "An expressible meaning associated with the following tags: {}".format(
            ', '.join(self.tags)
        )

    def _init_build_recipes(self, recipes):
        """Return a list of Recipe objects, each corresponding to one of the grammar paths associated with
        this expressible meaning.
        """
        recipe_objects = []
        for i in xrange(len(recipes)):
            grammar_path = recipes[i]
            recipe_objects.append(Recipe(recipe_id=i, expressible_meaning=self, grammar_path=grammar_path))
        recipe_objects.sort(key=lambda r: r.id)
        return recipe_objects


class Recipe(object):
    """A recipe, in the form of a compressed grammar path, for generating content associated with a specific
    expressible meaning.

    By 'compressed grammar path', I mean a chain of semantically meaningful production rules that,
    when executed in the given order, will produce the desired content. Production rules that are not
    semantically meaningful are not included in these compressed paths (this is the source of compression),
    which means Productionist is free to choose randomly when its candidate production rules for the symbol
    it is currently expanding does not include the next symbol on its target path. This works just fine,
    because production rules that are not semantically meaningful cannot cause unwanted tags (or any
    tags, for that matter) to be accumulated, which means the random choices only produce lexical variation
    and not semantic variation. More precisely, the rules won't be chosen randomly, but according to all
    the concerns that are used to score rules that are not semantically meaningful ('wildcard rules'):
    repetition penalties, author assigned application frequencies and usage constraints, etc.
    """

    def __init__(self, recipe_id, expressible_meaning, grammar_path):
        """Initialize a Recipe object."""
        self.id = recipe_id
        self.expressible_meaning = expressible_meaning
        self.name = '{meaning_id}-{recipe_id}'.format(meaning_id=expressible_meaning.id, recipe_id=self.id)
        self.path = grammar_path

    def __str__(self):
        """Return string representation."""
        return "Recipe {name}".format(name=self.name)


class ContentRequest(object):
    """A content request submitted to a Productionist module."""

    def __init__(self, must_have=None, must_not_have=None, scoring_metric=None):
        """Initialize a ContentRequest object."""
        # Tags that must be associated with generated content
        self.must_have = must_have if must_have else set()
        # Tags that must *not* be associated generated content
        self.must_not_have = must_not_have if must_not_have else set()
        # A list of (tag, weight) tuples specifying the desirability of optional tags
        self.scoring_metric = scoring_metric

    def __str__(self):
        """Return string representation."""
        return (
            "\n\tRequired tags: {}".format(', '.join(self.must_have) if self.must_have else 'N/A') +
            "\n\tProhibited tags: {}".format(', '.join(self.must_not_have) if self.must_not_have else 'N/A') +
            "\n\tScoring metric: {}".format(
                ', '.join(str(t) for t in self.scoring_metric) if self.scoring_metric else 'N/A'
            )
        )


class Output(object):
    """A generated text output, comprising both the textual content itself and its associated tags."""

    def __init__(self, text, tags, recipe, explicit_grammar_path_taken, bracketed_expression):
        """Initialize an Output object."""
        # The generated textual content, itself
        self.text = text
        # The set of tags inherited from the nonterminal symbols expanded to generate this content
        self.tags = tags
        # The recipe that was followed to produce this output; this associates the generated content
        # with the expressible meaning and the specific recipe that were targeted to produce it, which
        # could be useful for debugging/authoring reasons
        self.recipe = recipe
        # The path that was taken through the grammar to produce this content, represented as the
        # ordered sequence of production rules that were executed
        self.explicit_grammar_path_taken = explicit_grammar_path_taken
        # A bracketed expression capturing the particular symbols that were expanded to
        # produce this content
        self.bracketed_expression = bracketed_expression
        # A prettier-printed expression presenting the bracketed expression as a tree
        self.tree_expression = self._construct_tree_expression(exclude_tags=True)
        # A more cluttered, but potentially more useful, tree expression that displays the tags
        # inherited from each expanded symbol
        self.tree_expression_with_tags = self._construct_tree_expression(exclude_tags=False)

    def __str__(self):
        """Return string representation."""
        return self.text

    def _construct_tree_expression(self, exclude_tags):
        """Construct a more understandable version of the bracketed expression, presented as a tree."""
        bracketed_expression = self.bracketed_expression
        if exclude_tags:  # Strip out the tags, which are enclosed in angle brackets
            bracketed_expression = re.sub(r' <.+?>', '', bracketed_expression)
        tree_expression = ''
        indent = 0
        for character in bracketed_expression:
            if character in '[]+':
                indent += 4 if character == '[' else -4 if character == ']' else 0
            if character in '[+':
                tree_expression += '\n{whitespace}'.format(whitespace=' '*indent)
            elif character == ']':
                pass
            else:
                tree_expression += character
        return tree_expression

    @property
    def payload(self):
        """Return a dictionary containing data associated with this output, for use by the authoring interface."""
        return {"text": self.text, "tags": list(self.tags)}


class Grammar(object):
    """An annotated context-free grammar, loaded from a file generated by Reductionist."""

    def __init__(self, grammar_file_location):
        """Initialize a Grammar object."""
        # These get set by self._init_parse_content_file()
        self.nonterminal_symbols = None
        self.id_to_tag = None
        # Parse the
        self._init_parse_json_grammar_specification(path_to_json_grammar_specification=grammar_file_location)
        self.start_symbol = next(s for s in self.nonterminal_symbols if s.start_symbol)
        # Sort the symbol list -- this needs to happen before rule grounding, since we rely on
        # a symbol's ID being the same as its index in self.nonterminal_symbols
        self.nonterminal_symbols.sort(key=lambda s: s.id)
        self._init_ground_symbol_references_in_all_production_rule_bodies()
        # Collect all production rules
        self.production_rules = []
        for symbol in self.nonterminal_symbols:
            self.production_rules += symbol.production_rules
        self.production_rules.sort(key=lambda r: r.id)
        # Collect all terminal symbols
        self.terminal_symbols = []
        for rule in self.production_rules:
            for symbol in rule.body:
                if type(symbol) == unicode and symbol not in self.terminal_symbols:
                    self.terminal_symbols.append(symbol)
        # Have all production rules compile all the tags on the symbols in their rule bodies
        for rule in self.production_rules:
            rule.compile_tags()
        # Compile all tags attached to all symbols in this grammar
        self.tags = set()
        for symbol in self.nonterminal_symbols:
            self.tags |= set(symbol.tags)
        # Check whether any symbols have rules with unequal application frequencies; if none do, then
        # Productionist may be able to choose rules randomly (this attribute is used to determine whether
        # a 'scoring mode' is engaged, in Productionist.scoring_modes_engaged())
        self.unequal_rule_frequencies = len({r.application_frequency for r in self.production_rules}) > 1
        # Lastly, run some validation checks on the grammar before proceeding any further (this
        # is particularly needed in the case that an author has manually deformed any of the content
        # files generated by Reductionist)
        self._init_validate_grammar()

    def _init_parse_json_grammar_specification(self, path_to_json_grammar_specification):
        """Parse a JSON grammar specification exported by Expressionist to instantiate symbols and rules."""
        # Load in the JSON spec
        try:
            grammar_dictionary = json.loads(open(path_to_json_grammar_specification).read())
        except IOError:
            raise Exception(
                "Cannot load grammar -- there is no grammar file located at '{filepath}'".format(
                    filepath=path_to_json_grammar_specification
                )
            )
        # Grab out the dictionaries mapping tag IDs to the tags themselves, which we need to execute
        # expressible meanings
        self.id_to_tag = grammar_dictionary['id_to_tag']
        # Build objects for the nonterminal symbols defined in the spec
        symbol_objects = []
        nonterminal_symbol_specifications = grammar_dictionary['nonterminal_symbols']
        for symbol_id, nonterminal_symbol_specification in nonterminal_symbol_specifications.iteritems():
            symbol_name = nonterminal_symbol_specification['name']
            tags = nonterminal_symbol_specification['tags']
            production_rules_specification = nonterminal_symbol_specification['production_rules']
            expansions_are_complete_outputs = (
                nonterminal_symbol_specification['expansions_are_complete_outputs']
            )
            symbol_is_start_symbol = nonterminal_symbol_specification['is_start_symbol']
            symbol_is_semantically_meaningful = nonterminal_symbol_specification['is_semantically_meaningful']
            symbol_object = NonterminalSymbol(
                symbol_id=int(symbol_id), name=symbol_name, tags=tags,
                production_rules_specification=production_rules_specification,
                expansions_are_complete_outputs=expansions_are_complete_outputs,
                start_symbol=symbol_is_start_symbol, semantically_meaningful=symbol_is_semantically_meaningful,
            )
            symbol_objects.append(symbol_object)
        self.nonterminal_symbols = symbol_objects

    def _init_ground_symbol_references_in_all_production_rule_bodies(self):
        """Ground all symbol references in production rule bodies to actual NonterminalSymbol objects."""
        for symbol in self.nonterminal_symbols:
            for rule in symbol.production_rules:
                self._init_ground_symbol_references_in_a_rule_body(production_rule=rule)

    def _init_ground_symbol_references_in_a_rule_body(self, production_rule):
        """Ground all symbol references in the body of this rule to actual NonterminalSymbol objects."""
        rule_body_specification = list(production_rule.body_specification)
        rule_body_with_resolved_symbol_references = []
        for symbol_reference in rule_body_specification:
            if type(symbol_reference) is int:  # The symbol's ID, which is also its index in self.nonterminal_symbols
                # We've encountered a reference to a nonterminal symbol, so we need to resolve this
                # reference and append the nonterminal symbol itself to the list that we're building
                symbol_object = self.nonterminal_symbols[symbol_reference]
                rule_body_with_resolved_symbol_references.append(symbol_object)
            else:
                # We've encountered a terminal symbol, so we can just append this string itself
                # to the list that we're building
                rule_body_with_resolved_symbol_references.append(symbol_reference)
            production_rule.body = rule_body_with_resolved_symbol_references

    def _init_validate_grammar(self):
        """Run validation checks to ensure the well-formedness of this grammar."""
        # Make sure there is one and only one start symbol in the grammar
        assert len([s for s in self.nonterminal_symbols if s.start_symbol]) > 0, (
            "This grammar has no start symbols; there must be exactly one."
        )
        assert len([s for s in self.nonterminal_symbols if s.start_symbol]) == 1, (
            "This grammar has multiple start symbols; there must be exactly one."
        )
        # TODO TAKE ALL CHECKS FROM REDUCTIONIST -- IDEA IS MAKE SURE IT WASN'T TAMPERED WITH MANUALLY
        # TODO CHECK FOR CYCLES HERE (SIGNALED BY A SYMBOL APPEARING IN ITS OWN DESCENDANTS LIST;
        # SUCH A LIST CAN BE COMPUTED USING SOME OF THE FUNCTIONALITY USED ABOVE TO DETERMINE
        # IF A SYMBOL IS SEMANTICALLY MEANINGFUL) -- also, it appears that the json module
        # may have a built-in check for this (keyword for looking into this is 'check_circular')


class NonterminalSymbol(object):
    """A nonterminal symbol in an annotated context-free grammar authored using an Expressionist-like tool."""

    def __init__(self, symbol_id, name, tags, production_rules_specification, expansions_are_complete_outputs,
                 start_symbol, semantically_meaningful):
        """Initialize a NonterminalSymbol object."""
        self.id = symbol_id
        self.name = name
        # Set the tags attached to this symbol (defined as a list of strings of the form 'tagset:tag')
        self.tags = tags
        # Reify production rules for expanding this symbol
        self.production_rules = self._init_reify_production_rules(production_rules_specification)
        self._init_set_rule_frequency_score_multipliers()
        # Whether an author marked this as a symbol whose terminal expansions are complete outputs
        self.expansions_are_complete_outputs = expansions_are_complete_outputs
        # Whether this is the start symbol in the grammar
        self.start_symbol = start_symbol
        # Whether this symbol and/or any of its descendants have tags
        self.semantically_meaningful = semantically_meaningful

    def __str__(self):
        """Return string representation."""
        return '[[{name}]]'.format(name=self.name)

    def _init_reify_production_rules(self, production_rules_specification):
        """Instantiate ProductionRule objects for the rules specified in production_rules_specification."""
        production_rule_objects = []
        if production_rules_specification:
            for rule_specification in production_rules_specification:
                rule_id = rule_specification['id']
                body_specification = rule_specification['body']
                application_frequency = rule_specification['application_frequency']
                rule_is_semantically_meaningful = rule_specification['is_semantically_meaningful']
                production_rule_objects.append(
                    ProductionRule(
                        rule_id=rule_id, head=self, body_specification=body_specification,
                        application_frequency=application_frequency,
                        semantically_meaningful=rule_is_semantically_meaningful
                    )
                )
        return production_rule_objects

    def _init_set_rule_frequency_score_multipliers(self):
        """Set frequency score multipliers for each of this symbol's production rules."""
        if self.production_rules:
            # Determine the maximum application frequency across this symbol's production rules
            maximum_application_frequency = (
                float(max(self.production_rules, key=lambda rule: rule.application_frequency).application_frequency)
            )
            for rule in self.production_rules:
                rule.frequency_score_multiplier = rule.application_frequency/maximum_application_frequency


class ProductionRule(object):
    """A production rule in an annotated context-free grammar authored using an Expressionist-like tool."""

    def __init__(self, rule_id, head, body_specification, application_frequency, semantically_meaningful):
        """Initialize a ProductionRule object.

        'head' is a nonterminal symbol constituting the left-hand side of this rule, while
        'body' is a sequence of symbols that this rule may be used to expand the head into.
        """
        self.id = rule_id
        self.head = head
        self.body = None  # Gets set by Productionist._init_ground_symbol_references_in_a_rule_body()
        self.body_specification = body_specification
        # The rate at which this rule will be used relative to sibling rules, i.e., other rules with
        # the same head
        self.application_frequency = application_frequency
        # How this rule's application frequency will alter scores that Productionist computes for it; this
        # is determined by NonterminalSymbol._init_set_rule_frequency_score_multipliers() by diving the
        # rule's application frequency by the maximum frequency applied to one of its sibling rules
        self.frequency_score_multiplier = None
        self.semantically_meaningful = semantically_meaningful
        self.tags = []  # Gets set by self.compile_tags()

    def __str__(self):
        """Return string representation."""
        return '{head} --> {body}'.format(
            head=self.head,
            body=''.join(symbol if type(symbol) is unicode else '[[{}]]'.format(symbol.name) for symbol in self.body)
        )

    def compile_tags(self):
        """Compile all tags that are accessible from this production rule, meaning all the tags on all the symbols
        in the body of this rule.
        """
        for symbol in self.body:
            if type(symbol) != unicode:  # i.e., if the symbol is nonterminal
                for tag in symbol.tags:
                    if tag not in self.tags:
                        self.tags.append(tag)
