[PATCH 2/3] (v3) C++ template type diff printing

[David Malcolm <dmalcolm@redhat.com>]

Changes in v3:
- Merge bodies of type_to_string_with_compare and
print_template_tree_comparison into a new function,
print_template_differences.  Use simpler comma-insertion criterion.
- Cleanup assertions in cxx_format_postprocessor::handle.

Would it make sense to rename "m_type_a"/"m_type_b" to "m_type_H"/m_type_I"?
(we normally don't go for uppercase in fieldnames, but given the codes are
case-sensitive, does it make sense here?)

gcc/c-family/ChangeLog:
	* c-format.c (gcc_cxxdiag_char_table): Add 'H' and 'I' to
	format_chars.
	* c.opt (fdiagnostics-show-template-tree): New option.
	(felide-type): New option.

gcc/cp/ChangeLog:
	* call.c (perform_implicit_conversion_flags): Convert
	"from %qT to %qT" to "from %qH to %qI" in diagnostic.
	* error.c (struct deferred_printed_type): New struct.
	(class cxx_format_postprocessor): New class.
	(cxx_initialize_diagnostics): Wire up a cxx_format_postprocessor
	to pp->m_format_postprocessor.
	(comparable_template_types_p): New function.
	(newline_and_indent): New function.
	(arg_to_string): New function.
	(print_nonequal_arg): New function.
	(print_template_differences): New function.
	(type_to_string_with_compare): New function.
	(print_template_tree_comparison): New function.
	(append_formatted_chunk): New function.
	(add_quotes): New function.
	(cxx_format_postprocessor::handle): New function.
	(defer_phase_2_of_type_diff): New function.
	(cp_printer): Add "quoted" and "buffer_ptr" params.  Implement
	%H and %I.

gcc/ChangeLog:
	* doc/invoke.texi (-fdiagnostics-show-template-tree): New.
	(-fno-elide-type): New.

gcc/testsuite/ChangeLog:
	* g++.dg/plugin/plugin.exp (plugin_test_list): Add...
	* g++.dg/plugin/show-template-tree-color-no-elide-type.C: New
	test case.
	* g++.dg/plugin/show-template-tree-color.C: New test case.
	* g++.dg/plugin/show_template_tree_color_plugin.c: New plugin.
	* g++.dg/template/show-template-tree-2.C: New test case.
	* g++.dg/template/show-template-tree-3.C: New test case.
	* g++.dg/template/show-template-tree-4.C: New test case.
	* g++.dg/template/show-template-tree-no-elide-type.C: New test case.
	* g++.dg/template/show-template-tree.C: New test case.
---
 gcc/c-family/c-format.c                            |   2 +-
 gcc/c-family/c.opt                                 |   8 +
 gcc/cp/call.c                                      |   2 +-
 gcc/cp/error.c                                     | 450 ++++++++++++++++++++-
 gcc/doc/invoke.texi                                |  42 ++
 gcc/testsuite/g++.dg/plugin/plugin.exp             |   3 +
 .../show-template-tree-color-no-elide-type.C       |  30 ++
 .../g++.dg/plugin/show-template-tree-color.C       |  30 ++
 .../plugin/show_template_tree_color_plugin.c       |  38 ++
 .../g++.dg/template/show-template-tree-2.C         | 118 ++++++
 .../g++.dg/template/show-template-tree-3.C         |  37 ++
 .../g++.dg/template/show-template-tree-4.C         |  95 +++++
 .../template/show-template-tree-no-elide-type.C    |  24 ++
 gcc/testsuite/g++.dg/template/show-template-tree.C |  51 +++
 14 files changed, 926 insertions(+), 4 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/plugin/show-template-tree-color-no-elide-type.C
 create mode 100644 gcc/testsuite/g++.dg/plugin/show-template-tree-color.C
 create mode 100644 gcc/testsuite/g++.dg/plugin/show_template_tree_color_plugin.c
 create mode 100644 gcc/testsuite/g++.dg/template/show-template-tree-2.C
 create mode 100644 gcc/testsuite/g++.dg/template/show-template-tree-3.C
 create mode 100644 gcc/testsuite/g++.dg/template/show-template-tree-4.C
 create mode 100644 gcc/testsuite/g++.dg/template/show-template-tree-no-elide-type.C
 create mode 100644 gcc/testsuite/g++.dg/template/show-template-tree.C

diff --git a/gcc/c-family/c-format.c b/gcc/c-family/c-format.c
index 400eb66..fd40359 100644
--- a/gcc/c-family/c-format.c
+++ b/gcc/c-family/c-format.c
@@ -754,7 +754,7 @@ static const format_char_info gcc_cxxdiag_char_table[] =
   /* Custom conversion specifiers.  */
 
   /* These will require a "tree" at runtime.  */
-  { "ADEFKSTVX",0,STD_C89,{ T89_V,   BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN  }, "q+#",   "",   NULL },
+  { "ADEFHIKSTVX",0,STD_C89,{ T89_V,   BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN  }, "q+#",   "",   NULL },
 
   { "v", 0,STD_C89, { T89_I,   BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN,  BADLEN  }, "q#",  "",   NULL },
 
diff --git a/gcc/c-family/c.opt b/gcc/c-family/c.opt
index 9ad2f6e..4648e60 100644
--- a/gcc/c-family/c.opt
+++ b/gcc/c-family/c.opt
@@ -1342,6 +1342,10 @@ fdefault-inline
 C++ ObjC++ Ignore
 Does nothing.  Preserved for backward compatibility.
 
+fdiagnostics-show-template-tree
+C++ ObjC++ Var(flag_diagnostics_show_template_tree) Init(0)
+Print hierarchical comparisons when template types are mismatched.
+
 fdirectives-only
 C ObjC C++ ObjC++
 Preprocess directives only.
@@ -1361,6 +1365,10 @@ Write all declarations as Ada code for the given file only.
 felide-constructors
 C++ ObjC++ Var(flag_elide_constructors) Init(1)
 
+felide-type
+C++ ObjC++ Var(flag_elide_type) Init(1)
+-fno-elide-type Do not elide common elements in template comparisons.
+
 fenforce-eh-specs
 C++ ObjC++ Var(flag_enforce_eh_specs) Init(1)
 Generate code to check exception specifications.
diff --git a/gcc/cp/call.c b/gcc/cp/call.c
index c15b8e4..f1b6bf4 100644
--- a/gcc/cp/call.c
+++ b/gcc/cp/call.c
@@ -10099,7 +10099,7 @@ perform_implicit_conversion_flags (tree type, tree expr,
 	  else if (invalid_nonstatic_memfn_p (loc, expr, complain))
 	    /* We gave an error.  */;
 	  else
-	    error_at (loc, "could not convert %qE from %qT to %qT", expr,
+	    error_at (loc, "could not convert %qE from %qH to %qI", expr,
 		      TREE_TYPE (expr), type);
 	}
       expr = error_mark_node;
diff --git a/gcc/cp/error.c b/gcc/cp/error.c
index 4934c51..996998c 100644
--- a/gcc/cp/error.c
+++ b/gcc/cp/error.c
@@ -101,6 +101,49 @@ static void cp_print_error_function (diagnostic_context *, diagnostic_info *);
 static bool cp_printer (pretty_printer *, text_info *, const char *,
 			int, bool, bool, bool, bool, const char **);
 
+/* Struct for handling %H or %I, which require delaying printing the
+   type until a postprocessing stage.  */
+
+struct deferred_printed_type
+{
+  deferred_printed_type ()
+  : m_tree (NULL_TREE), m_buffer_ptr (NULL), m_verbose (false), m_quote (false)
+  {}
+
+  deferred_printed_type (tree type, const char **buffer_ptr, bool verbose,
+			 bool quote)
+  : m_tree (type), m_buffer_ptr (buffer_ptr), m_verbose (verbose),
+    m_quote (quote)
+  {
+    gcc_assert (type);
+    gcc_assert (buffer_ptr);
+  }
+
+  /* The tree is not GTY-marked: they are only non-NULL within a
+     call to pp_format.  */
+  tree m_tree;
+  const char **m_buffer_ptr;
+  bool m_verbose;
+  bool m_quote;
+};
+
+/* Subclass of format_postprocessor for the C++ frontend.
+   This handles the %H and %I formatting codes, printing them
+   in a postprocessing phase (since they affect each other).  */
+
+class cxx_format_postprocessor : public format_postprocessor
+{
+ public:
+  cxx_format_postprocessor ()
+  : m_type_a (), m_type_b ()
+  {}
+
+  void handle (pretty_printer *pp) FINAL OVERRIDE;
+
+  deferred_printed_type m_type_a;
+  deferred_printed_type m_type_b;
+};
+
 /* CONTEXT->printer is a basic pretty printer that was constructed
    presumably by diagnostic_initialize(), called early in the
    compiler's initialization process (in general_init) Before the FE
@@ -123,6 +166,7 @@ cxx_initialize_diagnostics (diagnostic_context *context)
   diagnostic_starter (context) = cp_diagnostic_starter;
   /* diagnostic_finalizer is already c_diagnostic_finalizer.  */
   diagnostic_format_decoder (context) = cp_printer;
+  pp->m_format_postprocessor = new cxx_format_postprocessor ();
 }
 
 /* Dump a scope, if deemed necessary.  */
@@ -3565,6 +3609,388 @@ maybe_print_constexpr_context (diagnostic_context *context)
     }
 }
 \f
+
+/* Return true iff TYPE_A and TYPE_B are template types that are
+   meaningful to compare.  */
+
+static bool
+comparable_template_types_p (tree type_a, tree type_b)
+{
+  if (!CLASS_TYPE_P (type_a))
+    return false;
+  if (!CLASS_TYPE_P (type_b))
+    return false;
+
+  tree tinfo_a = TYPE_TEMPLATE_INFO (type_a);
+  tree tinfo_b = TYPE_TEMPLATE_INFO (type_b);
+  if (!tinfo_a || !tinfo_b)
+    return false;
+
+  return TI_TEMPLATE (tinfo_a) == TI_TEMPLATE (tinfo_b);
+}
+
+/* Start a new line indented by SPC spaces on PP.  */
+
+static void
+newline_and_indent (pretty_printer *pp, int spc)
+{
+  pp_newline (pp);
+  for (int i = 0; i < spc; i++)
+    pp_space (pp);
+}
+
+/* Generate a GC-allocated string for ARG, an expression or type.  */
+
+static const char *
+arg_to_string (tree arg, bool verbose)
+{
+  if (TYPE_P (arg))
+    return type_to_string (arg, verbose);
+  else
+    return expr_to_string (arg);
+}
+
+/* Subroutine to type_to_string_with_compare and
+   print_template_tree_comparison.
+
+   Print a representation of ARG (an expression or type) to PP,
+   colorizing it as "type-diff" if PP->show_color.  */
+
+static void
+print_nonequal_arg (pretty_printer *pp, tree arg, bool verbose)
+{
+  pp_printf (pp, "%r%s%R",
+	     "type-diff",
+	     (arg
+	      ? arg_to_string (arg, verbose)
+	      : G_("(no argument)")));
+}
+
+/* Recursively print template TYPE_A to PP, as compared to template TYPE_B.
+
+   The types must satisfy comparable_template_types_p.
+
+   If INDENT is 0, then this is equivalent to type_to_string (TYPE_A), but
+   potentially colorizing/eliding in comparison with TYPE_B.
+
+   For example given types:
+     vector<map<int,double>>
+   and
+     vector<map<int,float>>
+   then the result on PP would be:
+     vector<map<[...],double>>
+   with type elision, and:
+     vector<map<int,double>>
+   without type elision.
+
+   In both cases the parts of TYPE that differ from PEER will be colorized
+   if pp_show_color (pp) is true.  In the above example, this would be
+   "double".
+
+   If INDENT is non-zero, then the types are printed in a tree-like form
+   which shows both types.  In the above example, the result on PP would be:
+
+     vector<
+       map<
+         [...],
+         [double != float]>>
+
+   and without type-elision would be:
+
+     vector<
+       map<
+         int,
+         [double != float]>>
+
+   As before, the differing parts of the types are colorized if
+   pp_show_color (pp) is true ("double" and "float" in this example).
+
+   Template arguments in which both types are using the default arguments
+   are not printed; if at least one of the two types is using a non-default
+   argument, then that argument is printed (or both arguments for the
+   tree-like print format).  */
+
+static void
+print_template_differences (pretty_printer *pp, tree type_a, tree type_b,
+			    bool verbose, int indent)
+{
+  if (indent)
+    newline_and_indent (pp, indent);
+
+  tree tinfo_a = TYPE_TEMPLATE_INFO (type_a);
+  tree tinfo_b = TYPE_TEMPLATE_INFO (type_b);
+
+  pp_printf (pp, "%s<",
+	     IDENTIFIER_POINTER (DECL_NAME (TI_TEMPLATE (tinfo_a))));
+
+  tree args_a = TI_ARGS (tinfo_a);
+  tree args_b = TI_ARGS (tinfo_b);
+  gcc_assert (TREE_CODE (args_a) == TREE_VEC);
+  gcc_assert (TREE_CODE (args_b) == TREE_VEC);
+  int flags = 0;
+  int len_a = get_non_default_template_args_count (args_a, flags);
+  args_a = INNERMOST_TEMPLATE_ARGS (args_a);
+  int len_b = get_non_default_template_args_count (args_b, flags);
+  args_b = INNERMOST_TEMPLATE_ARGS (args_b);
+  /* Determine the maximum range of args for which non-default template args
+     were used; beyond this, only default args (if any) were used, and so
+     they will be equal from this point onwards.
+     One of the two peers might have used default arguments within this
+     range, but the other will be using non-default arguments, and so
+     it's more readable to print both within this range, to highlight
+     the differences.  */
+  int len_max = MAX (len_a, len_b);
+  gcc_assert (TREE_CODE (args_a) == TREE_VEC);
+  gcc_assert (TREE_CODE (args_b) == TREE_VEC);
+  for (int idx = 0; idx < len_max; idx++)
+    {
+      if (idx)
+	pp_character (pp, ',');
+
+      tree arg_a = TREE_VEC_ELT (args_a, idx);
+      tree arg_b = TREE_VEC_ELT (args_b, idx);
+      if (arg_a == arg_b)
+	{
+	  if (indent)
+	    newline_and_indent (pp, indent + 2);
+	  /* Can do elision here, printing "[...]".  */
+	  if (flag_elide_type)
+	    pp_string (pp, G_("[...]"));
+	  else
+	    pp_string (pp, arg_to_string (arg_a, verbose));
+	}
+      else
+	{
+	  int new_indent = indent ? indent + 2 : 0;
+	  if (comparable_template_types_p (arg_a, arg_b))
+	    print_template_differences (pp, arg_a, arg_b, verbose, new_indent);
+	  else
+	    if (indent)
+	      {
+		newline_and_indent (pp, indent + 2);
+		pp_character (pp, '[');
+		print_nonequal_arg (pp, arg_a, verbose);
+		pp_string (pp, " != ");
+		print_nonequal_arg (pp, arg_b, verbose);
+		pp_character (pp, ']');
+	      }
+	    else
+	      print_nonequal_arg (pp, arg_a, verbose);
+	}
+    }
+  pp_printf (pp, ">");
+}
+
+/* As type_to_string, but for a template, potentially colorizing/eliding
+   in comparison with PEER.
+   For example, if TYPE is map<int,double> and PEER is map<int,int>,
+   then the resulting string would be:
+     map<[...],double>
+   with type elision, and:
+     map<int,double>
+   without type elision.
+
+   In both cases the parts of TYPE that differ from PEER will be colorized
+   if SHOW_COLOR is true.  In the above example, this would be "double".
+
+   Template arguments in which both types are using the default arguments
+   are not printed; if at least one of the two types is using a non-default
+   argument, then both arguments are printed.
+
+   The resulting string is in a GC-allocated buffer.  */
+
+static const char *
+type_to_string_with_compare (tree type, tree peer, bool verbose,
+			     bool show_color)
+{
+  pretty_printer inner_pp;
+  pretty_printer *pp = &inner_pp;
+  pp_show_color (pp) = show_color;
+
+  print_template_differences (pp, type, peer, verbose, 0);
+  return pp_ggc_formatted_text (pp);
+}
+
+/* Recursively print a tree-like comparison of TYPE_A and TYPE_B to PP,
+   indented by INDENT spaces.
+
+   For example given types:
+
+     vector<map<int,double>>
+
+   and
+
+     vector<map<double,float>>
+
+   the output with type elision would be:
+
+     vector<
+       map<
+         [...],
+         [double != float]>>
+
+   and without type-elision would be:
+
+     vector<
+       map<
+         int,
+         [double != float]>>
+
+   TYPE_A and TYPE_B must both be comparable template types
+   (as per comparable_template_types_p).
+
+   Template arguments in which both types are using the default arguments
+   are not printed; if at least one of the two types is using a non-default
+   argument, then both arguments are printed.  */
+
+static void
+print_template_tree_comparison (pretty_printer *pp, tree type_a, tree type_b,
+				bool verbose, int indent)
+{
+  print_template_differences (pp, type_a, type_b, verbose, indent);
+}
+
+/* Subroutine for use in a format_postprocessor::handle
+   implementation.  Adds a chunk to the end of
+   formatted output, so that it will be printed
+   by pp_output_formatted_text.  */
+
+static void
+append_formatted_chunk (pretty_printer *pp, const char *content)
+{
+  output_buffer *buffer = pp_buffer (pp);
+  struct chunk_info *chunk_array = buffer->cur_chunk_array;
+  const char **args = chunk_array->args;
+
+  unsigned int chunk_idx;
+  for (chunk_idx = 0; args[chunk_idx]; chunk_idx++)
+    ;
+  args[chunk_idx++] = content;
+  args[chunk_idx] = NULL;
+}
+
+/* Create a copy of CONTENT, with quotes added, and,
+   potentially, with colorization.
+   No escaped is performed on CONTENT.
+   The result is in a GC-allocated buffer. */
+
+static const char *
+add_quotes (const char *content, bool show_color)
+{
+  pretty_printer tmp_pp;
+  pp_show_color (&tmp_pp) = show_color;
+
+  /* We have to use "%<%s%>" rather than "%qs" here in order to avoid
+     quoting colorization bytes within the results.  */
+  pp_printf (&tmp_pp, "%<%s%>", content);
+
+  return pp_ggc_formatted_text (&tmp_pp);
+}
+
+/* If we had %H and %I, and hence deferred printing them,
+   print them now, storing the result into the chunk_info
+   for pp_format.  Quote them if 'q' was provided.
+   Also print the difference in tree form, adding it as
+   an additional chunk.  */
+
+void
+cxx_format_postprocessor::handle (pretty_printer *pp)
+{
+  /* If we have one of %H and %I, the other should have
+     been present.  */
+  if (m_type_a.m_tree || m_type_b.m_tree)
+    {
+      /* Avoid reentrancy issues by working with a copy of
+	 m_type_a and m_type_b, resetting them now.  */
+      deferred_printed_type type_a = m_type_a;
+      deferred_printed_type type_b = m_type_b;
+      m_type_a = deferred_printed_type ();
+      m_type_b = deferred_printed_type ();
+
+      gcc_assert (type_a.m_buffer_ptr);
+      gcc_assert (type_b.m_buffer_ptr);
+
+      bool show_color = pp_show_color (pp);
+
+      const char *type_a_text;
+      const char *type_b_text;
+
+      if (comparable_template_types_p (type_a.m_tree, type_b.m_tree))
+	{
+	  type_a_text
+	    = type_to_string_with_compare (type_a.m_tree, type_b.m_tree,
+					   type_a.m_verbose, show_color);
+	  type_b_text
+	    = type_to_string_with_compare (type_b.m_tree, type_a.m_tree,
+					   type_b.m_verbose, show_color);
+
+	  if (flag_diagnostics_show_template_tree)
+	    {
+	      pretty_printer inner_pp;
+	      pp_show_color (&inner_pp) = pp_show_color (pp);
+	      print_template_tree_comparison
+		(&inner_pp, type_a.m_tree, type_b.m_tree, type_a.m_verbose, 2);
+	      append_formatted_chunk (pp, pp_ggc_formatted_text (&inner_pp));
+	    }
+	}
+      else
+	{
+	  /* If the types were not comparable, they are printed normally,
+	     and no difference tree is printed.  */
+	  type_a_text = type_to_string (type_a.m_tree, type_a.m_verbose);
+	  type_b_text = type_to_string (type_b.m_tree, type_b.m_verbose);
+	}
+
+      if (type_a.m_quote)
+	type_a_text = add_quotes (type_a_text, show_color);
+      *type_a.m_buffer_ptr = type_a_text;
+
+       if (type_b.m_quote)
+	type_b_text = add_quotes (type_b_text, show_color);
+      *type_b.m_buffer_ptr = type_b_text;
+   }
+}
+
+/* Subroutine for handling %H and %I, to support i18n of messages like:
+
+    error_at (loc, "could not convert %qE from %qH to %qI",
+	       expr, type_a, type_b);
+
+   so that we can print things like:
+
+     could not convert 'foo' from 'map<int,double>' to 'map<int,int>'
+
+   and, with type-elision:
+
+     could not convert 'foo' from 'map<[...],double>' to 'map<[...],int>'
+
+   (with color-coding of the differences between the types).
+
+   The %H and %I format codes are peers: both must be present,
+   and they affect each other.  Hence to handle them, we must
+   delay printing until we have both, deferring the printing to
+   pretty_printer's m_format_postprocessor hook.
+
+   This is called in phase 2 of pp_format, when it is accumulating
+   a series of formatted chunks.  We stash the location of the chunk
+   we're meant to have written to, so that we can write to it in the
+   m_format_postprocessor hook.
+
+   We also need to stash whether a 'q' prefix was provided (the QUOTE
+   param)  so that we can add the quotes when writing out the delayed
+   chunk.  */
+
+static void
+defer_phase_2_of_type_diff (deferred_printed_type *deferred,
+			    tree type, const char **buffer_ptr,
+			    bool verbose, bool quote)
+{
+  gcc_assert (deferred->m_tree == NULL_TREE);
+  gcc_assert (deferred->m_buffer_ptr == NULL);
+  *deferred = deferred_printed_type (type, buffer_ptr, verbose, quote);
+}
+
+
 /* Called from output_format -- during diagnostic message processing --
    to handle C++ specific format specifier with the following meanings:
    %A   function argument-list.
@@ -3579,12 +4005,18 @@ maybe_print_constexpr_context (diagnostic_context *context)
    %S   substitution (template + args)
    %T   type.
    %V   cv-qualifier.
-   %X   exception-specification.  */
+   %X   exception-specification.
+   %H   type difference (from)
+   %I   type difference (to).  */
 static bool
 cp_printer (pretty_printer *pp, text_info *text, const char *spec,
 	    int precision, bool wide, bool set_locus, bool verbose,
-	    bool, const char **)
+	    bool quoted, const char **buffer_ptr)
 {
+  gcc_assert (pp->m_format_postprocessor);
+  cxx_format_postprocessor *postprocessor
+    = static_cast <cxx_format_postprocessor *> (pp->m_format_postprocessor);
+
   const char *result;
   tree t = NULL;
 #define next_tree    (t = va_arg (*text->args_ptr, tree))
@@ -3630,6 +4062,20 @@ cp_printer (pretty_printer *pp, text_info *text, const char *spec,
       percent_K_format (text);
       return true;
 
+    case 'H':
+      {
+	defer_phase_2_of_type_diff (&postprocessor->m_type_a, next_tree,
+				    buffer_ptr, verbose, quoted);
+	return true;
+      }
+
+    case 'I':
+      {
+	defer_phase_2_of_type_diff (&postprocessor->m_type_b, next_tree,
+				    buffer_ptr, verbose, quoted);
+	return true;
+      }
+
     default:
       return false;
     }
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 1ba45cf..9966fa0 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -251,6 +251,7 @@ Objective-C and Objective-C++ Dialects}.
 -fdiagnostics-color=@r{[}auto@r{|}never@r{|}always@r{]}  @gol
 -fno-diagnostics-show-option  -fno-diagnostics-show-caret @gol
 -fdiagnostics-parseable-fixits  -fdiagnostics-generate-patch @gol
+-fdiagnostics-show-template-tree -fno-elide-type @gol
 -fno-show-column}
 
 @item Warning Options
@@ -3584,6 +3585,47 @@ are printed.  For example:
 The diff may or may not be colorized, following the same rules
 as for diagnostics (see @option{-fdiagnostics-color}).
 
+@item -fdiagnostics-show-template-tree
+@opindex fdiagnostics-show-template-tree
+
+In the C++ frontend, when printing diagnostics showing mismatching
+template types, such as:
+
+@smallexample
+  could not convert 'std::map<int, std::vector<double> >()'
+    from 'map<[...],vector<double>>' to 'map<[...],vector<float>>
+@end smallexample
+
+the @option{-fdiagnostics-show-template-tree} flag enables printing a
+tree-like structure showing the common and differing parts of the types,
+such as:
+
+@smallexample
+  map<
+    [...],
+    vector<
+      [double != float]>>
+@end smallexample
+
+The parts that differ are highlighted with color (``double'' and
+``float'' in this case).
+
+@item -fno-elide-type
+@opindex fno-elide-type
+@opindex felide-type
+By default when the C++ frontend prints diagnostics showing mismatching
+template types, common parts of the types are printed as ``[...]'' to
+simplify the error message.  For example:
+
+@smallexample
+  could not convert 'std::map<int, std::vector<double> >()'
+    from 'map<[...],vector<double>>' to 'map<[...],vector<float>>
+@end smallexample
+
+Specifying the @option{-fno-elide-type} flag suppresses that behavior.
+This flag also affects the output of the
+@option{-fdiagnostics-show-template-tree} flag.
+
 @item -fno-show-column
 @opindex fno-show-column
 Do not print column numbers in diagnostics.  This may be necessary if
diff --git a/gcc/testsuite/g++.dg/plugin/plugin.exp b/gcc/testsuite/g++.dg/plugin/plugin.exp
index 6a0c1aa..94ebe93 100644
--- a/gcc/testsuite/g++.dg/plugin/plugin.exp
+++ b/gcc/testsuite/g++.dg/plugin/plugin.exp
@@ -65,6 +65,9 @@ set plugin_test_list [list \
     { def_plugin.c def-plugin-test.C } \
     { ../../gcc.dg/plugin/diagnostic_plugin_test_tree_expression_range.c \
 	  diagnostic-test-expressions-1.C } \
+    { show_template_tree_color_plugin.c \
+    	  show-template-tree-color.C \
+    	  show-template-tree-color-no-elide-type.C } \
 ]
 
 foreach plugin_test $plugin_test_list {
diff --git a/gcc/testsuite/g++.dg/plugin/show-template-tree-color-no-elide-type.C b/gcc/testsuite/g++.dg/plugin/show-template-tree-color-no-elide-type.C
new file mode 100644
index 0000000..cab0359
--- /dev/null
+++ b/gcc/testsuite/g++.dg/plugin/show-template-tree-color-no-elide-type.C
@@ -0,0 +1,30 @@
+/* Verify colorization of the output of -fdiagnostics-show-template-tree,
+   and within the %H and %I format codes.
+   Doing so requires a plugin; see the comments in the plugin for the
+   rationale.  */
+
+// { dg-options "-fdiagnostics-show-template-tree -fdiagnostics-color=always -fno-elide-type" }
+
+template<typename> struct vector {};
+template<typename, typename> struct map {};
+
+void fn_1(vector<int>);
+void fn_2(map<int, int>);
+
+void test ()
+{
+  fn_1 (vector<double> ());
+  /* { dg-begin-multiline-output "" }
+could not convert '^[[01m^[[Kvector<double>()^[[m^[[K' from '^[[01m^[[Kvector<^[[01;32m^[[Kdouble^[[m^[[K>^[[m^[[K' to '^[[01m^[[Kvector<^[[01;32m^[[Kint^[[m^[[K>^[[m^[[K'
+  vector<
+    [^[[01;32m^[[Kdouble^[[m^[[K != ^[[01;32m^[[Kint^[[m^[[K]>
+     { dg-end-multiline-output "" } */
+
+  fn_2 (map<int, double>());
+  /* { dg-begin-multiline-output "" }
+could not convert '^[[01m^[[Kmap<int, double>()^[[m^[[K' from '^[[01m^[[Kmap<int,^[[01;32m^[[Kdouble^[[m^[[K>^[[m^[[K' to '^[[01m^[[Kmap<int,^[[01;32m^[[Kint^[[m^[[K>^[[m^[[K'
+  map<
+    int,
+    [^[[01;32m^[[Kdouble^[[m^[[K != ^[[01;32m^[[Kint^[[m^[[K]>
+     { dg-end-multiline-output "" } */
+}
diff --git a/gcc/testsuite/g++.dg/plugin/show-template-tree-color.C b/gcc/testsuite/g++.dg/plugin/show-template-tree-color.C
new file mode 100644
index 0000000..eb99a3e
--- /dev/null
+++ b/gcc/testsuite/g++.dg/plugin/show-template-tree-color.C
@@ -0,0 +1,30 @@
+/* Verify colorization of the output of -fdiagnostics-show-template-tree,
+   and within the %H and %I format codes.
+   Doing so requires a plugin; see the comments in the plugin for the
+   rationale.  */
+
+// { dg-options "-fdiagnostics-show-template-tree -fdiagnostics-color=always" }
+
+template<typename> struct vector {};
+template<typename, typename> struct map {};
+
+void fn_1(vector<int>);
+void fn_2(map<int, int>);
+
+void test ()
+{
+  fn_1 (vector<double> ());
+  /* { dg-begin-multiline-output "" }
+could not convert '^[[01m^[[Kvector<double>()^[[m^[[K' from '^[[01m^[[Kvector<^[[01;32m^[[Kdouble^[[m^[[K>^[[m^[[K' to '^[[01m^[[Kvector<^[[01;32m^[[Kint^[[m^[[K>^[[m^[[K'
+  vector<
+    [^[[01;32m^[[Kdouble^[[m^[[K != ^[[01;32m^[[Kint^[[m^[[K]>
+     { dg-end-multiline-output "" } */
+
+  fn_2 (map<int, double>());
+  /* { dg-begin-multiline-output "" }
+could not convert '^[[01m^[[Kmap<int, double>()^[[m^[[K' from '^[[01m^[[Kmap<[...],^[[01;32m^[[Kdouble^[[m^[[K>^[[m^[[K' to '^[[01m^[[Kmap<[...],^[[01;32m^[[Kint^[[m^[[K>^[[m^[[K'
+  map<
+    [...],
+    [^[[01;32m^[[Kdouble^[[m^[[K != ^[[01;32m^[[Kint^[[m^[[K]>
+     { dg-end-multiline-output "" } */
+}
diff --git a/gcc/testsuite/g++.dg/plugin/show_template_tree_color_plugin.c b/gcc/testsuite/g++.dg/plugin/show_template_tree_color_plugin.c
new file mode 100644
index 0000000..af568bf
--- /dev/null
+++ b/gcc/testsuite/g++.dg/plugin/show_template_tree_color_plugin.c
@@ -0,0 +1,38 @@
+/* We want to verify the colorized output of cxx_format_postprocessor,
+   but turning on colorization for everything confuses "dg-error" etc.
+   The color codes in the generated messages would also need escaping
+   for use within dg-error.
+
+   Hence the simplest approach is to provide a custom diagnostic_starter_fn,
+   which does nothing.
+
+   The resulting messages lack the "FILENAME:LINE:COL: error: " prefix
+   and can thus be tested using dg-begin/end-multiline-output.  */
+
+/* { dg-options "-O" } */
+
+#include "gcc-plugin.h"
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "plugin-version.h"
+#include "diagnostic.h"
+
+int plugin_is_GPL_compatible;
+
+void
+noop_starter_fn (diagnostic_context *, diagnostic_info *)
+{
+}
+
+int
+plugin_init (struct plugin_name_args *plugin_info,
+	     struct plugin_gcc_version *version)
+{
+  if (!plugin_default_version_check (version, &gcc_version))
+    return 1;
+
+  diagnostic_starter (global_dc) = noop_starter_fn;
+
+  return 0;
+}
diff --git a/gcc/testsuite/g++.dg/template/show-template-tree-2.C b/gcc/testsuite/g++.dg/template/show-template-tree-2.C
new file mode 100644
index 0000000..1cd3a06
--- /dev/null
+++ b/gcc/testsuite/g++.dg/template/show-template-tree-2.C
@@ -0,0 +1,118 @@
+// Tests of -fdiagnostics-show-template-tree with variadic templates
+// { dg-options "-fdiagnostics-show-template-tree -std=c++11" }
+
+template<typename> struct vector {};
+template<typename, typename> struct map {};
+template<typename ... Types> struct var {};
+
+void fn_0(var<>);
+void fn_1(var<int>);
+void fn_2(var<int, int>);
+void fn_3(vector<var<> >);
+void fn_4(vector<var<int> >);
+void fn_5(vector<var<int, int> >);
+
+void test_fn_0 ()
+{
+  fn_0 (var<> ());
+  fn_0 (var<int> ()); // { dg-error "could not convert .* from 'var<int>' to 'var<>'" }
+  /* { dg-begin-multiline-output "" }
+  var<
+    [int != ]>
+     { dg-end-multiline-output "" } */
+  fn_0 (var<int, int> ()); // { dg-error "could not convert .* from 'var<int, int>' to 'var<>'" }
+  /* { dg-begin-multiline-output "" }
+  var<
+    [int, int != ]>
+     { dg-end-multiline-output "" } */
+  fn_0 (vector<var<int> >()); // { dg-error "could not convert .* from 'vector<var<int> >' to 'var<>'" }
+  fn_0 (vector<var<int, int> >());  // { dg-error "could not convert .* from 'vector<var<int, int> >' to 'var<>'" }
+}
+
+void test_fn_1 ()
+{
+  fn_1 (var<> ()); // { dg-error "could not convert .* from 'var<>' to 'var<int>'" }
+  /* { dg-begin-multiline-output "" }
+  var<
+    [ != int]>
+     { dg-end-multiline-output "" } */
+  fn_1 (var<int> ());
+  fn_1 (var<int, int> ()); // { dg-error "could not convert .* from 'var<int, int>' to 'var<int>'" }
+  /* { dg-begin-multiline-output "" }
+  var<
+    [int, int != int]>
+     { dg-end-multiline-output "" } */
+  fn_1 (vector<var<int> >()); // { dg-error "could not convert .* from 'vector<var<int> >' to 'var<int>'" }
+  fn_1 (vector<var<int, int> >()); // { dg-error "could not convert .* from 'vector<var<int, int> >' to 'var<int>'" }
+}
+
+void test_fn_2 ()
+{
+  fn_2 (var<> ()); // { dg-error "could not convert .* from 'var<>' to 'var<int, int>'" }
+  /* { dg-begin-multiline-output "" }
+  var<
+    [ != int, int]>
+     { dg-end-multiline-output "" } */
+  fn_2 (var<int> ()); // { dg-error "could not convert .* from 'var<int>' to 'var<int, int>'" }
+  /* { dg-begin-multiline-output "" }
+  var<
+    [int != int, int]>
+     { dg-end-multiline-output "" } */
+  fn_2 (var<int, int> ());
+  fn_2 (vector<var<int> >()); // { dg-error "could not convert .* from 'vector<var<int> >' to 'var<int, int>'" }
+  fn_2 (vector<var<int, int> >()); // { dg-error "could not convert .* from 'vector<var<int, int> >' to 'var<int, int>'" }
+}
+
+void test_fn_3 ()
+{
+  fn_3 (var<> ()); // { dg-error "could not convert .* from 'var<>' to 'vector<var<> >'" }
+  fn_3 (var<int> ()); // { dg-error "could not convert .* from 'var<int>' to 'vector<var<> >'" }
+  fn_3 (var<int, int> ()); // { dg-error "could not convert .* from 'var<int, int>' to 'vector<var<> >'" }
+  fn_3 (vector<var<> >());
+  fn_3 (vector<var<int> >());  // { dg-error "could not convert .* from 'vector<var<int>>' to 'vector<var<>>'" }
+  /* { dg-begin-multiline-output "" }
+  vector<
+    var<
+      [int != ]>>
+     { dg-end-multiline-output "" } */
+  fn_3 (vector<var<int, int> >()); // { dg-error "could not convert .* from 'vector<var<int, int>>' to 'vector<var<>>'" }
+  /* { dg-begin-multiline-output "" }
+  vector<
+    var<
+      [int, int != ]>>
+     { dg-end-multiline-output "" } */
+}
+
+void test_fn_4 ()
+{
+  fn_4 (var<> ()); // { dg-error "could not convert .* from 'var<>' to 'vector<var<int> >'" }
+  fn_4 (var<int> ()); // { dg-error "could not convert .* from 'var<int>' to 'vector<var<int> >'" }
+  fn_4 (var<int, int> ()); // { dg-error "could not convert .* from 'var<int, int>' to 'vector<var<int> >'" }
+  fn_4 (vector<var<> >()); // { dg-error "could not convert .* from 'vector<var<>>' to 'vector<var<int>>'" }
+  /* { dg-begin-multiline-output "" }
+  vector<
+    var<
+      [ != int]>>
+     { dg-end-multiline-output "" } */
+  fn_4 (vector<var<int> >()); 
+  fn_4 (vector<var<int, int> >()); // { dg-error "could not convert .* from 'vector<var<int, int>>' to 'vector<var<int>>'" }
+  /* { dg-begin-multiline-output "" }
+  vector<
+    var<
+      [int, int != int]>>
+     { dg-end-multiline-output "" } */
+}
+
+void test_fn_5 ()
+{
+  fn_5 (var<> ()); // { dg-error "could not convert .* from 'var<>' to 'vector<var<int, int> >'" }
+  fn_5 (var<int> ());  // { dg-error "could not convert .* from 'var<int>' to 'vector<var<int, int> >'" }
+  fn_5 (var<int, int> ());  // { dg-error "could not convert .* from 'var<int, int>' to 'vector<var<int, int> >'" }
+  fn_5 (vector<var<int> >());  // { dg-error "could not convert .* from 'vector<var<int>>' to 'vector<var<int, int>>'" }
+  /* { dg-begin-multiline-output "" }
+  vector<
+    var<
+      [int != int, int]>>
+     { dg-end-multiline-output "" } */
+  fn_5 (vector<var<int, int> >());
+}
diff --git a/gcc/testsuite/g++.dg/template/show-template-tree-3.C b/gcc/testsuite/g++.dg/template/show-template-tree-3.C
new file mode 100644
index 0000000..0eda40b
--- /dev/null
+++ b/gcc/testsuite/g++.dg/template/show-template-tree-3.C
@@ -0,0 +1,37 @@
+/* End-to-end test of -fdiagnostics-show-template-tree and -felide-type
+   using the STL.
+   In particular, ensure that we don't print the default arguments e.g.
+   rather than printing
+     from 'vector<double,allocator<double>>' to 'vector<float,allocator<float>>'
+   (albeit with differences nicely color-coded), we want to print:
+     from 'vector<double>' to 'vector<float>'
+   (again, with the "double" and "float" highlighted, though we can't test
+   for that in this case).  */
+
+// { dg-options "-fdiagnostics-show-template-tree" }
+
+#include <map>
+#include <vector>
+
+using std::vector;
+using std::map;
+
+void takes_vf (vector<float> v);
+void takes_mivf (map<int, vector<float> > v);
+
+int test ()
+{
+  takes_vf (vector<double> ()); // { dg-error "could not convert '.*' from 'vector<double>' to 'vector<float>'" }
+  /* { dg-begin-multiline-output "" }
+  vector<
+    [double != float]>
+     { dg-end-multiline-output "" } */
+
+  takes_mivf (map<int, vector<double> > ()); // { dg-error "could not convert '.*' from 'map<.\\.\\.\\..,vector<double>>' to 'map<.\\.\\.\\..,vector<float>>'" }
+  /* { dg-begin-multiline-output "" }
+  map<
+    [...],
+    vector<
+      [double != float]>>
+     { dg-end-multiline-output "" } */
+}
diff --git a/gcc/testsuite/g++.dg/template/show-template-tree-4.C b/gcc/testsuite/g++.dg/template/show-template-tree-4.C
new file mode 100644
index 0000000..953733b
--- /dev/null
+++ b/gcc/testsuite/g++.dg/template/show-template-tree-4.C
@@ -0,0 +1,95 @@
+// { dg-options "-fdiagnostics-show-template-tree" }
+
+/* Example of default template args, and various kinds of mismatch.  */
+
+template <int = 0, int = 1, int = 2>
+struct s {};
+
+void takes_s (s<> );
+void takes_s013 (s<0, 1, 3> );
+void takes_s321 (s<3, 2, 1> );
+
+void test ()
+{
+  takes_s (s<>());
+  takes_s (s<0, 1>());
+  takes_s (s<0, 1, 2>());
+  takes_s (s<0, 2>()); // { dg-error "could not convert '.*' from 's<.\\.\\.\\..,2>' to 's<.\\.\\.\\..,1>'" }
+  /* { dg-begin-multiline-output "" }
+  s<
+    [...],
+    [2 != 1]>
+     { dg-end-multiline-output "" } */
+
+  takes_s (s<1>()); // { dg-error "could not convert '.*' from 's<1>' to 's<0>'" }
+  /* { dg-begin-multiline-output "" }
+  s<
+    [1 != 0]>
+     { dg-end-multiline-output "" } */
+
+  takes_s (s<0, 1, 3>()); // { dg-error "could not convert '.*' from 's<.\\.\\.\\..,.\\.\\.\\..,3>' to 's<.\\.\\.\\..,.\\.\\.\\..,2>'" }
+  /* { dg-begin-multiline-output "" }
+  s<
+    [...],
+    [...],
+    [3 != 2]>
+     { dg-end-multiline-output "" } */
+
+  takes_s (s<3, 2, 0>()); // { dg-error "could not convert '.*' from 's<3,2,0>' to 's<0,1,2>'" }
+  /* { dg-begin-multiline-output "" }
+  s<
+    [3 != 0],
+    [2 != 1],
+    [0 != 2]>
+     { dg-end-multiline-output "" } */
+
+  takes_s (s<3, 2, 1>()); // { dg-error "could not convert '.*' from 's<3,2,1>' to 's<0,1,2>'" }
+  /* { dg-begin-multiline-output "" }
+  s<
+    [3 != 0],
+    [2 != 1],
+    [1 != 2]>
+     { dg-end-multiline-output "" } */
+
+  takes_s013 (s<0, 1, 2>()); // { dg-error "could not convert '.*' from 's<.\\.\\.\\..,.\\.\\.\\..,2>' to 's<.\\.\\.\\..,.\\.\\.\\..,3>'" }
+  /* { dg-begin-multiline-output "" }
+  s<
+    [...],
+    [...],
+    [2 != 3]>
+     { dg-end-multiline-output "" } */
+
+  takes_s321 (s<>());        // { dg-error "could not convert '.*' from 's<0,1,2>' to 's<3,2,1>'" }
+  /* { dg-begin-multiline-output "" }
+  s<
+    [0 != 3],
+    [1 != 2],
+    [2 != 1]>
+     { dg-end-multiline-output "" } */
+
+  takes_s321 (s<0, 1, 3>()); // { dg-error "could not convert '.*' from 's<0,1,3>' to 's<3,2,1>'" }
+  /* { dg-begin-multiline-output "" }
+  s<
+    [0 != 3],
+    [1 != 2],
+    [3 != 1]>
+     { dg-end-multiline-output "" } */
+
+  takes_s321 (s<3, 2, 0>()); // { dg-error "could not convert '.*' from 's<.\\.\\.\\..,.\\.\\.\\..,0>' to 's<.\\.\\.\\..,.\\.\\.\\..,1>'" }
+  /* { dg-begin-multiline-output "" }
+  s<
+    [...],
+    [...],
+    [0 != 1]>
+     { dg-end-multiline-output "" } */
+
+  takes_s321 (s<3, 2, 1>());
+
+  takes_s321 (s<1, 2, 3>()); // { dg-error "could not convert '.*' from 's<1,.\\.\\.\\..,3>' to 's<3,.\\.\\.\\..,1>'" }
+  /* { dg-begin-multiline-output "" }
+  s<
+    [1 != 3],
+    [...],
+    [3 != 1]>
+     { dg-end-multiline-output "" } */
+}
diff --git a/gcc/testsuite/g++.dg/template/show-template-tree-no-elide-type.C b/gcc/testsuite/g++.dg/template/show-template-tree-no-elide-type.C
new file mode 100644
index 0000000..d4bfa81
--- /dev/null
+++ b/gcc/testsuite/g++.dg/template/show-template-tree-no-elide-type.C
@@ -0,0 +1,24 @@
+// { dg-options "-fdiagnostics-show-template-tree -fno-elide-type" }
+
+template<typename> struct vector {};
+template<typename, typename> struct map {};
+
+void fn_1(vector<int>);
+void fn_2(map<int, int>);
+void fn_3(vector<map<int, float> >);
+
+void test ()
+{
+  fn_1 (vector<double> ()); // { dg-error "could not convert .* from 'vector<double>' to 'vector<int>'" }
+  /* { dg-begin-multiline-output "" }
+  vector<
+    [double != int]>
+     { dg-end-multiline-output "" } */
+
+  fn_2 (map<int, double>());  // { dg-error "could not convert .* from 'map<int,double>' to 'map<int,int>'" }
+  /* { dg-begin-multiline-output "" }
+  map<
+    int,
+    [double != int]>
+     { dg-end-multiline-output "" } */
+}
diff --git a/gcc/testsuite/g++.dg/template/show-template-tree.C b/gcc/testsuite/g++.dg/template/show-template-tree.C
new file mode 100644
index 0000000..0b75098
--- /dev/null
+++ b/gcc/testsuite/g++.dg/template/show-template-tree.C
@@ -0,0 +1,51 @@
+// { dg-options "-fdiagnostics-show-template-tree" }
+
+template<typename> struct vector {};
+template<typename, typename> struct map {};
+template<int> struct arr {};
+
+void fn_1(vector<int>);
+void fn_2(map<int, int>);
+void fn_3(vector<map<int, float> >);
+void takes_arr_10 (arr<10>);
+
+void test ()
+{
+  fn_1 (vector<int> ());
+  fn_1 (42); // { dg-error "could not convert '42' from 'int' to 'vector<int>'" }
+  fn_1 (vector<double> ()); // { dg-error "could not convert .* from 'vector<double>' to 'vector<int>'" }
+  /* { dg-begin-multiline-output "" }
+  vector<
+    [double != int]>
+     { dg-end-multiline-output "" } */
+  fn_1 (map<int, int> ()); // { dg-error "could not convert .* from 'map<int, int>' to 'vector<int>'" }
+
+  fn_2 (map<int, int>());
+  fn_2 (map<int, double>());  // { dg-error "could not convert .* from 'map<.\\.\\.\\..,double>. to .map<.\\.\\.\\..,int>'" }
+  /* { dg-begin-multiline-output "" }
+  map<
+    [...],
+    [double != int]>
+     { dg-end-multiline-output "" } */
+  fn_2 (map<double, double>());  // { dg-error "could not convert .* from .map<double,double>. to .map<int,int>." }
+  /* { dg-begin-multiline-output "" }
+  map<
+    [double != int],
+    [double != int]>
+     { dg-end-multiline-output "" } */
+
+  fn_3 (vector<map<int, float> >());
+  fn_3 (vector<map<int, double> >());  // { dg-error "could not convert .* from 'vector<map<.\\.\\.\\..,double>>' to 'vector<map<.\\.\\.\\..,float>>'" }
+  /* { dg-begin-multiline-output "" }
+  vector<
+    map<
+      [...],
+      [double != float]>>
+     { dg-end-multiline-output "" } */
+
+  takes_arr_10 (arr<5>()); // { dg-error "could not convert '.*' from 'arr<5>' to 'arr<10>'" }
+  /* { dg-begin-multiline-output "" }
+  arr<
+    [5 != 10]>
+     { dg-end-multiline-output "" } */
+}
-- 
1.8.5.3