MixFix.cxx

Go to the documentation of this file.

/**************************************************************************
 *
 * Copyright (C) 2010, Jonathan S. Shapiro
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following
 * conditions are met:
 *
 *   - Redistributions of source code must contain the above 
 *     copyright notice, this list of conditions, and the following
 *     disclaimer. 
 *
 *   - Redistributions in binary form must reproduce the above
 *     copyright notice, this list of conditions, and the following
 *     disclaimer in the documentation and/or other materials 
 *     provided with the distribution.
 *
 *   - Neither the names of the copyright holders nor the names of any
 *     of any contributors may be used to endorse or promote products
 *     derived from this software without specific prior written
 *     permission. 
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 **************************************************************************/

#include <limits.h>
#include <iostream>
#include "shared_ptr.hxx"

#include "Options.hxx"
#include "AST.hxx"
#include "MixFix.hxx"
#include "UocInfo.hxx"
#include "libsherpa/INOstream.hxx"

#include "BUILD/TransitionParser.hxx"

// Debug levels:
// 5 = show non-candidate rules
// 4 = rule matching
// 3 = shifting
// 2 = reduce actions
// 1 = Summary input and result
#define MIXDEBUG(n) if (Options::mixfixDebug >= (n))

using namespace std;
using namespace boost;
using namespace sherpa;

typedef shared_ptr<AST> ASTPtr;
typedef std::vector<ASTPtr> ASTVec;
typedef std::vector<std::string> StringVec;

// We are going to use a vector as a stack here, because the
// std::stack implementation does not provide indexed access, and we
// are going to need that.

template<class T>
static inline
const T& top(const std::vector<T>& vec)
{
  assert(vec.size() >= 1);
  return vec[vec.size()-1];
}

template<class T>
static inline
T& top(std::vector<T>& vec)
{
  assert(vec.size() >= 1);
  return vec[vec.size()-1];
}

template<class T>
static inline
const T& topNext(const std::vector<T>& vec)
{
  assert(vec.size() >= 2);
  return vec[vec.size()-2];
}

template<class T>
static inline
void push(std::vector<T>& vec, const T& elem)
{
  vec.push_back(elem);
}

template<class T>
static inline
T pop(std::vector<T>& vec)
{
  T elem = top(vec);
  vec.pop_back();
  return elem;
}


struct QuasiKeyword {
  int nOccur;

  int nFirst;

  int nPre;

  int nPost;

  QuasiKeyword()
  {
    nOccur = nPre = nPost = nFirst = 0;
  }
};

struct QuasiKeywordMap {
  std::map<std::string, QuasiKeyword> theMap;

  QuasiKeywordMap()
  {
  }

  void add(std::string qkwd);
  void remove(std::string qkwd);

  QuasiKeyword& operator[](std::string theKey)
  {
    return theMap[theKey];
  }

  bool contains(std::string theKey)
  {
    return (theMap.find(theKey) != theMap.end());
  }

  size_t erase(std::string theKey)
  {
    return theMap.erase(theKey);
  }
};

enum MixElemModifierValues {
  MEMV_NONE,

  MEMV_THUNK                    // Hole expression should be thunked.
};
typedef sherpa::EnumSet<MixElemModifierValues> MixElemModifiers;

struct MixRuleElement {
  SyntacticCategory sc;
  MixElemModifiers mods;
  std::string name;

  MixRuleElement(SyntacticCategory _sc)
  {
    sc = _sc;
    mods = MEMV_NONE;
  }
  MixRuleElement(std::string _name)
  {
    sc = msc_keyword;
    name = _name;
  }

  bool isHole() { return sc != msc_keyword; };
};
typedef std::vector<MixRuleElement> MixElemVec;

struct MixRule : public boost::enable_shared_from_this<MixRule> {
  std::string name;

  MixElemVec rhs;

  int fixity;

  SyntacticCategory sc;

  int prec;

  Associativity assoc;

  bool isInfix()   const { return fixity == infix; }
  bool isPrefix()  const { return fixity == prefix; }
  bool isClosed()  const { return fixity == closed; }
  bool isPostfix() const { return fixity == postfix; }

  bool isHole(size_t pos) {
    return (rhs[pos].sc != msc_keyword);
  }

  bool isKwd(size_t pos) {
    return (rhs[pos].sc == msc_keyword);
  }

  bool isInitialHole(size_t pos) {
    return (pos == 0) && isHole(pos);
  }

  bool isFinalHole(size_t pos) {
    return ((pos == rhs.size() - 1) && isHole(pos));
  }

  bool hasLeadingHole() 
  {
    return (fixity == infix) || (fixity == postfix);
  }
  bool hasTrailingHole() 
  {
    return (fixity == infix) || (fixity == prefix);
  }

private:
  void extract();

public:
  MixRule(SyntacticCategory _sc, const std::string& _nm, int _prec, 
          Associativity _assoc = assoc_none)
  {
    sc = _sc;
    name = _nm;
    prec = _prec;
    assoc = _assoc;
    extract();
  }

  static shared_ptr<MixRule> 
  make(SyntacticCategory _sc, const std::string& _nm, int _prec, 
       Associativity _assoc = assoc_none)
  {
    MixRule *tmp = new MixRule(_sc, _nm, _prec, _assoc);
    return boost::shared_ptr<MixRule>(tmp);
  }

  void PrettyPrint(INOstream& out) const;
};
typedef shared_ptr<MixRule> MixRulePtr;

INOstream& operator<<(INOstream& out, MixRule& rule)
{
  rule.PrettyPrint(out);
  return out;
}


struct MixFixNode {
  ASTPtr ast;

  MixRulePtr rule;

  MixFixNode(ASTPtr _ast, MixRulePtr _rule)
  {
    ast = _ast;
    rule = _rule;
  }

  bool matchesKwd(const MixRuleElement& elem) const {
    assert(ast);
    return (elem.sc == msc_keyword && ast->s == elem.name);
  }

  void PrettyPrint(sherpa::INOstream& out, PrettyPrintFlags flags)
  {
    if (ast->astType != at_ident)
      out << '{';

    ast->PrettyPrint(out, flags & ~pp_FinalNewline);

    if (ast->astType != at_ident)
      out << '}';

    if (flags & pp_FinalNewline)
      out << endl;
  }

  bool isKwd() const
  { return (!rule); }

  bool isExpr() const 
  { return rule && rule->sc == msc_expr; }

  bool isType() const 
  { return rule && rule->sc == msc_type; }
};

typedef std::vector<MixFixNode> MixInput;

struct MixContext {
  typedef std::set<MixRulePtr> RuleSet;
  RuleSet rules;
  QuasiKeywordMap kwMap;

  void add(MixRulePtr rule);
  void remove(MixRulePtr rule);

  MixRulePtr
  ParseOneMixFix(sherpa::INOstream& errStream, MixInput& origInput, 
                 MixRulePtr parentRule);
                  
  MixRulePtr
  ParseMixFix(sherpa::INOstream& errStream, MixInput& origInput, 
              MixRulePtr parentRule);
                  
  bool isKwd(const MixFixNode& mixNode);

  bool cannotPossiblyMatch(sherpa::INOstream& errStream,
                           MixRulePtr rule,
                           const MixInput& mixExpr);

} TheMixContext;

void
MixRule::PrettyPrint(INOstream& out) const
{
  switch(fixity) {
  case infix:
    out << "infix";

    switch(assoc) {
    case assoc_left:   out << 'l'; break;
    case assoc_right:  out << 'r'; break;
    case assoc_none:   out << 'n'; break;
    }

    break;
  case prefix:
    out << "prefix";
    break;
  case postfix:
    out << "postfix";
    break;
  case closed:
    out << "closed";
    break;
  }

  out << " "
      << name
      << "("
      << prec
      << ")";
}

void
MixRule::extract()
{
  std::string rule = name;
  
  while(rule.size()) {
    if (rule[0] == '_') {
      rhs.push_back(MixRuleElement(sc));
      rule = rule.substr(1);
    }
    else if (rule[0] == '#') {  // need to parse it
      SyntacticCategory sc;

      switch (rule[1]) {
      case 'e':
        sc = msc_expr;
        break;
      case 't':
        sc = msc_type;
        break;
      case 'k':
        sc = msc_kind;
        break;
      default:
        assert(false);
      }

      MixRuleElement elem(sc);

      rule = rule.substr(2);
      while (rule[0] != '_') {
        switch(rule[0]) {
        case 'T':
          elem.mods |= MEMV_THUNK;
          break;
        default:
          assert(false);
        }

        rule = rule.substr(1);
      }
      
      rhs.push_back(elem);
      rule = rule.substr(1);
    }
    else {
      if (rule[0] == '@')       // keyword separator
        rule = rule.substr(1);

      // Find the end of this quasi-keyword, or end-of-rule:
      size_t nxt = rule.find_first_of("#_@");

      if (nxt == string::npos) {
        rhs.push_back(MixRuleElement(rule));
        rule.clear();
      }
      else {
        rhs.push_back(MixRuleElement(rule.substr(0, nxt)));
        rule = rule.substr(nxt);
      }
    }
  }

  if (isHole(0) && isHole(rhs.size()-1))
    fixity = infix;
  else if (isHole(0))
    fixity = postfix;
  else if (isHole(rhs.size()-1))
    fixity = prefix;
  else
    fixity = closed;
}

bool
MixContext::isKwd(const MixFixNode& node)
{
  if (node.ast->astType != at_ident)
    return false;

  return kwMap.contains(node.ast->s);
}

bool 
MixContext::cannotPossiblyMatch(sherpa::INOstream& errStream,
                                MixRulePtr rule, 
                                const MixInput& input)
{
  MixElemVec& rhs = rule->rhs;

  // Are enough components left?
  if (input.size() < rhs.size())
    return true;

  // If this rule has a leading hole, the first thing must be a hole
  // and the next thing must match:
  if (rule->hasLeadingHole()) {
    bool might = (top(input).isExpr()
                  && ((rule->rhs.size() == 1)
                      || topNext(input).matchesKwd(rule->rhs[1])));

    MIXDEBUG(might ? 4 : 5)
      errStream << (*rule)
                << (might ? " might" : " cannot") << " match."
                << endl;
    
    if (might)
      return false;

    return true;
  }
  
  // For closed and prefix expressions, the initial keyword must
  // match, but if the next position is a keyword it may ultimately
  // reduce to an expression, so we can't conclude anything from that.
  bool might = top(input).matchesKwd(rule->rhs[0]);
  if (might)
    return false;

  MIXDEBUG(might ? 4 : 5)
    errStream << (*rule)
              << (might ? " might" : " cannot") << " match."
              << endl;

  return true;
}

void
QuasiKeywordMap::add(std::string qkwd)
{
  if (!contains(qkwd)) {
    QuasiKeyword qks;
    theMap.insert(std::pair<std::string, QuasiKeyword>(qkwd,qks));
  }

  theMap[qkwd].nOccur++;
}

void
QuasiKeywordMap::remove(std::string qkwd)
{
  if (!contains(qkwd))
    return;

  theMap[qkwd].nOccur--;

  if (theMap[qkwd].nOccur == 0)
    theMap.erase(qkwd);
}

void 
MixContext::add(MixRulePtr rule)
{
  MixElemVec& rhs = rule->rhs;
  
  for (size_t i = 0; i < rhs.size(); i++)
    if (rule->isKwd(i))
      kwMap.add(rhs[i].name);

  // Closed and prefix rules start with a token:
  if (!rule->hasLeadingHole())
    kwMap[rhs[0].name].nFirst++;

  // Prefix and infix rules end with a hole:
  if (rule->hasTrailingHole())
    kwMap[rhs[rhs.size()-2].name].nPre++;

  // Postfix and infix rules start with a hole:
  if (rule->hasLeadingHole())
    kwMap[rhs[1].name].nPost++;

  rules.insert(rule);
}

void
MixContext::remove(MixRulePtr rule)
{
  MixElemVec& rhs = rule->rhs;

  // Closed and prefix rules start with a token:
  if (!rule->hasLeadingHole())
    kwMap[rhs[0].name].nFirst--;

  // Prefix and infix rules end with a hole:
  if (rule->hasTrailingHole())
    kwMap[rhs[rhs.size()-2].name].nPre--;

  // Postfix and infix rules start with a hole:
  if (rule->hasLeadingHole())
    kwMap[rhs[1].name].nPost--;

  for (size_t i = 0; i < rhs.size(); i++)
    if (rule->isKwd(i))
      kwMap.remove(rhs[i].name);

  rules.erase(rule);
}

static ASTPtr
CleanMixFix(INOstream& errStream, ASTPtr ast)
{
  // This used to be an else-less IF designed to allow fall-through
  // intentionally. That led to a number of bugs, because the value of
  // 'fn' could become stale. I've therefore switched to a loop
  // structure.

  if (ast->astType == at_apply) {
    std::string fn = ast->child(0)->s;

    // This is the start rule - take all of these out.
    if (fn == "_") {
      return CleanMixFix(errStream, ast->child(1));
    }
    else if (fn == "_._") {
      ast = AST::make(at_select, ast->loc, ast->child(1), ast->child(2));
    }
    else if (fn == "_,_") {
      LToken pair(tk_BlkIdent, ast->child(0)->loc, ast->child(0)->endLoc(), "pair");
      ast->children[0] = AST::make(at_ident, pair);
    }
    else if (fn == "(_)") {
      return CleanMixFix(errStream, ast->child(1));
    }
    else if (fn == "_(_)") {
      shared_ptr<AST> argAst = ast->child(2);

      // Rotate the applied function into the proper position
      ast->children[0] = ast->children[1];
      ast->children.erase(ast->children.begin()+1, ast->children.end());

      while((argAst->astType == at_apply) && (argAst->child(0)->s == "_,_")) {
        ast->addChild(argAst->child(1));
        argAst = argAst->child(2);
      }
      ast->addChild(argAst);
    }
    else if (fn == "_(@)") {
      // Rotate the applied function into the proper position
      ast->children[0] = ast->children[1];
      ast->children.erase(ast->children.begin()+1, ast->children.end());
    }
    else if (fn == "(@)") {
      ast->astType = at_unit;
      ast->children.clear();
      return ast;
    }
    else if (fn == "_[_]") {    // Array indexing:
      ast = AST::make(at_nth, ast->loc, ast->child(1), ast->child(2));
    }

#if 0
    // Check for ([a, b, c]) convenience syntax. Otherwise eliminate
    // "(_)" nodes.
    else if (fn == "(_)") {
      if ((ast->child(1)->astType == at_apply) &&
          (ast->child(1)->child(0)->s == "[_]")) {
        
        ast = argListToConsList(ast->child(1)->child(1));

        // Re-write the argument chain into a chain of CONS applications:
        shared_ptr<AST> argAst = inAST->child(1)->child(1);
        while((argAst->astType == at_apply) && (argAst->child(0)->s == "_,_")) {
          argAst->children[0] = 
            argAst = argAst->child(2);
        }
        ast->addChild(argAst);
      }
      else {
        return CleanMixFix(ast->child(1));
      }
    }
#endif
    else if (fn == "[_]") {
      ast = AST::make(at_nth, ast->loc, ast->child(1), ast->child(2));
    }
    if (fn == "_and_" || fn == "_&&_") {
      ast->astType = at_and;
      ast->children.erase(ast->children.begin());
    }
    if (fn == "_or_" || fn == "_||_") {
      ast->astType = at_or;
      ast->children.erase(ast->children.begin());
    }
  }

  for (size_t c = 0; c < ast->children.size(); c++)
    ast->children[c] = CleanMixFix(errStream, ast->children[c]);

  return ast;
}

static ASTPtr
CheckMixFix(INOstream& errStream, ASTPtr ast)
{
  return ast;
}

static MixRulePtr MixNoRuleFound = MixRule::make(msc_expr, "_", INT_MIN, assoc_none);
static MixRulePtr MixStartRule = MixRule::make(msc_expr, "_", INT_MIN, assoc_none);
static MixRulePtr MixInputRule = MixRule::make(msc_expr, "(_)", INT_MIN, assoc_none);

shared_ptr<AST>
ProcessMixFix(std::ostream& err, shared_ptr<AST> mixAST)
{
  INOstream errStream(err);

  if (TheMixContext.rules.empty())
    errStream << "Error! No Rules!" << endl;

  ASTVec& children = mixAST->children;

  MixInput input;
  for(ASTVec::reverse_iterator itr = children.rbegin();
      itr != children.rend();
      itr++) {
    push(input, MixFixNode(*itr, MixStartRule));

    // Input quasi-keywords should not be marked by a rule.
    if (TheMixContext.isKwd(top(input)))
      top(input).rule = GC_NULL;
  }

  MIXDEBUG(1) {
    errStream << "Processing mixfix expression at "
              << mixAST->loc << endl;
    errStream.more();
    for(MixInput::reverse_iterator itr = input.rbegin();
        itr != input.rend();
        itr++) {
      if (itr != input.rbegin()) errStream << " ";
      (*itr).PrettyPrint(errStream, pp_NONE);
    }
    errStream << endl;
    errStream.less();
  }


  while( input.size() > 1 
         && TheMixContext.ParseMixFix(errStream, input, MixStartRule))
    ;

  if (input.size() != 1) {
    MIXDEBUG(1)
      errStream << "Yields Incomplete Parse" << endl;
    return GC_NULL;
  }

  MIXDEBUG(2) {
    errStream << "Produced: ";
    input[0].PrettyPrint(errStream, pp_FinalNewline);
  }

  shared_ptr<AST> result = CleanMixFix(errStream, input[0].ast);
  result = CheckMixFix(errStream, result);

  MIXDEBUG(1) {
    errStream << "Giving: ";
    result->PrettyPrint(errStream, pp_FinalNewline);
  }

  return result;
}

static MixFixNode
reduce(INOstream& errStream, MixInput& shunt, MixRulePtr rule)
{
  // Children under shunt are now what we want. Build an apply node
  // for them, and push them back onto the front of the input vector.
  // Don't build unnecessary apply nodes for the catch-all expression
  // rule.

  shared_ptr<AST> result = shunt[0].ast; // until proven otherwise

  shared_ptr<AST> fnName = 
    AST::make(at_ident, LToken(tk_BlkIdent, rule->name));

  if (rule->sc == msc_expr) {
    result = AST::make(at_apply, shunt[0].ast->loc, fnName);
  }
  else if (rule->sc == msc_type) {
    result = AST::make(at_typeapp, shunt[0].ast->loc, fnName);
  }

  assert(rule->rhs.size() == shunt.size());

  for(size_t i = 0; i < shunt.size(); i++) {
    if (rule->rhs[i].isHole()) {
      assert(!shunt[i].isKwd());
      
      shared_ptr<AST> tree = shunt[i].ast;

      if (rule->rhs[i].mods & MEMV_THUNK) {
        shared_ptr<AST> iRetBody = 
          AST::make(at_labeledBlock, tree->loc,
                    AST::make(at_ident, LToken(tk_BlkIdent, "__return")),
                    tree);

        tree = 
          AST::make(at_lambda, tree->loc,
                    AST::make(at_argVec, tree->loc), // empty
                    iRetBody);
      }

      result->addChild(tree);
    }
  }

  MIXDEBUG(2) {
    errStream << "Reduced " <<  rule->name << " giving ";
    result->PrettyPrint(errStream, pp_FinalNewline);
  }

  return MixFixNode(result, rule);
}

MixRulePtr
MixContext::ParseOneMixFix(INOstream& errStream, MixInput& origInput, 
                           MixRulePtr parentRule)
{
  errStream.more();

  MixInput shunt;

  struct BestRule {
    MixRulePtr rule;
    MixInput result;
    bool tie;
  } best = { GC_NULL, MixInput(), false };

  MIXDEBUG(4) {
    errStream << "Parsing:";

    for(MixInput::reverse_iterator itr = origInput.rbegin();
        itr != origInput.rend();
        itr++) {
      errStream << " ";
      (*itr).PrettyPrint(errStream, pp_NONE);
    }
    errStream << " in context of "<< (*parentRule);
    errStream << endl;
  }

  // We are proceding through all of the parse rules, trying to find
  // one that reduces the input without regard to operator
  // precedence. We'll fix up operator precedence later using a tree
  // re-writing.

  for(RuleSet::iterator itr = rules.begin();
      itr != rules.end();
      ++itr) {
    MixRulePtr rule = *itr;

    // ParentRule is actually telling us the hole precedence:
    if (rule->prec < parentRule->prec) {
      MIXDEBUG(5)
        errStream << (*rule)
                  << "rejected (below required precedence)"
                  << endl;
      continue;
    }
    
    if (rule->prec == parentRule->prec) {
      if ((rule->assoc != assoc_right) ||
          (parentRule->assoc != assoc_right)) {
        MIXDEBUG(5)
          errStream << (*rule)
                    << "rejected (prec OK, not right-assoc)"
                    << endl;
        continue;
      }
    }
    
    // If the candidate rule has lower precedence than the one we actually
    // found, the current best rule would be preferred.
    if (best.rule && rule->prec < best.rule->prec)
      continue;
    
    if (cannotPossiblyMatch(errStream, rule, origInput))
      continue;

    // The parse processing is destructive, so we need to operate on a
    // copy:
    MixInput input = origInput;
    shunt = MixInput();

    MIXDEBUG(4) {
      errStream << "Attempting rule " << rule->name
                << " on";

        for(MixInput::reverse_iterator itr = input.rbegin();
            itr != input.rend();
            itr++) {
          errStream << " ";
          (*itr).PrettyPrint(errStream, pp_NONE);
        }
      errStream << endl;
    }

    errStream.more();

    // If we survived cannotPossiblyMatch(), then the first element
    // matches, so shift that:
    MIXDEBUG(3) {
      errStream << "Shifting first element: ";
      top(input).PrettyPrint(errStream, pp_FinalNewline);
    }
    push(shunt, pop(input));

    for (size_t pos = 1; pos < rule->rhs.size(); pos++) {
      // Parsing of expressions can cause the remaining input to
      // become too small for this rule to succeed. Need to check here
      // to avoid a range overrun on the input:
      if (input.size() < (rule->rhs.size() - pos))
        break;

      // Note that if matchesKwd() passes then we know the node
      // actually *was* a keyword by virtue of the fact that we are
      // matching a keyword position in the rule. There is no need
      // to check that redundantly.
      //
      // We handle right-most holes specially because they have to
      // have higher precedence than their parent rule, and when we
      // recurse we are only looking for potential child nodes.

      if (rule->isKwd(pos) && top(input).matchesKwd(rule->rhs[pos])) {
        MIXDEBUG(3) {
          errStream << "Shifting: ";
          top(input).PrettyPrint(errStream, pp_FinalNewline);
        }

        push(shunt, pop(input));
      }
      // Note: Want to do this whether the next thing in the input is
      // an expr or a kwd! Consider _-_ matching 1 - (2) 
      else if (rule->isHole(pos) &&
               ParseMixFix(errStream, input, 
                           rule->isFinalHole(pos) ? rule : MixInputRule)) {
        MIXDEBUG(3) {
          errStream << "Shifting: ";
          top(input).PrettyPrint(errStream, pp_FinalNewline);
        }

        push(shunt, pop(input));
      }
      else if(rule->isHole(pos) && top(input).isExpr()) {
        // No way to reduce. Shift this element because it is an
        // pre-existing expression constructed by the initial parser.
        MIXDEBUG(3) {
          errStream << "Shifting: ";
          top(input).PrettyPrint(errStream, pp_FinalNewline);
        }

        push(shunt, pop(input));
      }
      else {
        // Rule did not match.
        break;
      }
    }

    // Did we get a complete match for this rule? If so, compute the
    // reduction:
    MIXDEBUG(4) {
      errStream << "Rule " << rule->name
                << " (size " << rule->rhs.size()
                << ")";
      if (rule->rhs.size() == shunt.size()) {
        errStream << " matched stack " << shunt.size();

        if (best.rule) {
          if (rule->prec > best.rule->prec)
            errStream << " and is preferred";
          else
            errStream << " but existing rule is better";
        }
      }
      else
        errStream << " did not match stack " << shunt.size();

      errStream << endl;
    }

    errStream.less();

    if (rule->rhs.size() == shunt.size()) {
      MixFixNode nd = reduce(errStream, shunt, rule);
      
      assert(nd.ast);

      if (best.rule && rule->prec == best.rule->prec) {
        // FIX: Somehow need to track the alternatives here for
        // reporting purposes.
        best.tie = true;
        continue;
      }

      push(input, nd);
      best.rule = rule;
      best.result = input;
      best.tie = false;
    }
  }

  errStream.less();

  if (best.tie)
    return GC_NULL;

  if (!best.rule)               // no rule fonud
    return GC_NULL;

  origInput = best.result;
  return best.rule;
}

MixRulePtr
MixContext::ParseMixFix(INOstream& errStream, MixInput& origInput,
                        MixRulePtr parentRule)
{
  MixRulePtr best = GC_NULL;
  MixRulePtr p = GC_NULL;

  while (p = ParseOneMixFix(errStream, origInput, parentRule)) {
    best = p;
  }

  return best;
}

MixRulePtr MixRules[] =  {
  // Beginning of user-defined mixfix range

  MixRule::make(msc_expr, "_or_",  0, assoc_left), // lazy OR (syntax)
  MixRule::make(msc_expr, "_||_",  0, assoc_left), // lazy OR (syntax)
  MixRule::make(msc_expr, "_and_", 1, assoc_left), // lazy AND (syntax)
  MixRule::make(msc_expr, "_&&_",  1, assoc_left), // lazy AND (syntax)
  MixRule::make(msc_expr, "_!=_",  2, assoc_left),
  MixRule::make(msc_expr, "_==_",  2, assoc_left),
  MixRule::make(msc_expr, "_<_",   3, assoc_left),
  MixRule::make(msc_expr, "_<=_",  3, assoc_left),
  MixRule::make(msc_expr, "_>_",   3, assoc_left),
  MixRule::make(msc_expr, "_>=_",  3, assoc_left),
  MixRule::make(msc_expr, "_::_",  4, assoc_left), // infix cons
  MixRule::make(msc_expr, "_|_",   5, assoc_left),
  MixRule::make(msc_expr, "_^_",   6, assoc_left),
  MixRule::make(msc_expr, "_&_",   7, assoc_left),
  MixRule::make(msc_expr, "_<<_",  8, assoc_left),
  MixRule::make(msc_expr, "_>>_",  8, assoc_left),
  MixRule::make(msc_expr, "_+_",   9, assoc_left),
  MixRule::make(msc_expr, "_-_",   9, assoc_left),
  MixRule::make(msc_expr, "_%_",  10, assoc_left),
  MixRule::make(msc_expr, "_*_",  10, assoc_left),
  MixRule::make(msc_expr, "_/_",  10, assoc_left),

  MixRule::make(msc_expr, "_**_",    11, assoc_left), // exponentiation
  MixRule::make(msc_expr, "_**_+_",  11, assoc_left),  // hypothetical mul-add for testing

  MixRule::make(msc_expr, "-_",   12, assoc_right), // Unary negation
  MixRule::make(msc_expr, "!_",   13, assoc_right), // Boolean inverse
  MixRule::make(msc_expr, "not_", 13, assoc_right), // Boolean inverse
  MixRule::make(msc_expr, "~_",   14, assoc_right), // Bitwise inverse

  // End of user-defined mixfix range

  // Rules associated with built-in structure start here.
  //
  // These productions yield (after massage) syntactic forms rather
  // than applications.

  // The precedence of these next two doesn't really matter, because
  // (a) they are closed, and (b) the related forms below don't have
  // the same first token.

  // cpair convenience and precedence override:
  MixRule::make(msc_expr, "(_)",  128, assoc_none),

  // list convenience syntax:
  MixRule::make(msc_expr, "[_]",  128, assoc_none),

  // Kind matching is not yet implemented:
  // MixRule::make(msc_type, "_:#k_", 129, assoc_none),

  // The design note called for:
  //   MixRule::make(msc_expr, "__",  0, assoc_left),
  // but I'm giving these a try instead:

  MixRule::make(msc_expr, "_,_",  -1, assoc_right), // arg assembly, cpair assembly

  MixRule::make(msc_expr, "(@)",   129, assoc_left), // unit constructor

  MixRule::make(msc_expr, "_(@)",  130, assoc_left), // nullary application
  MixRule::make(msc_expr, "_(_)",  130, assoc_left), // application
  MixRule::make(msc_expr, "_[_]",  130, assoc_left), // array/vector subscript
  MixRule::make(msc_expr, "_._",   130, assoc_left), // dot notation (select or usesel)

  // Which might quite possibly be a better approach
};
static size_t nMixRules = sizeof(MixRules) / sizeof(MixRules[0]);

void
mixfix_init()
{
  for (size_t i = 0; i < nMixRules; i++) {
    TheMixContext.add(MixRules[i]);
  }
}

static bool 
HandleMixFix(std::ostream& errStream, shared_ptr<AST> ast)
{
  bool errFree = true;

  // In this pass, we proceed bottom-up
  for (size_t c = 0; c < ast->children.size(); c++)
    errFree = errFree && HandleMixFix(errStream, ast->child(c));

  if (ast->astType == at_mixfix) {
    shared_ptr<AST> newAst = ProcessMixFix(errStream, ast);

    if (!newAst)
      errFree = false;

    if (newAst && newAst != ast) {
      // Clobber the old node in-place:
      ast->s = newAst->s;
      ast->astType = newAst->astType;
      ast->identType = newAst->identType;
      ast->litValue = newAst->litValue;
      ast->litBase = newAst->litBase;
      ast->flags = newAst->flags;
      ast->children = newAst->children;
      ast->fqn = newAst->fqn;
    }
  }

  return errFree;
}

bool
UocInfo::fe_mixfix(std::ostream& errStream,
                   bool init, unsigned long flags)
{
  return HandleMixFix(errStream, uocAst);
}

---