content: /*
   * Copyright 2015 Google Inc.
   *
   * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
   * in compliance with the License. You may obtain a copy of the License at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software distributed under the License
   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
   * or implied. See the License for the specific language governing permissions and limitations under
   * the License.
   */
  
  package com.google.googlejavaformat.java;
  
  import static java.lang.Math.min;
  import static java.util.Comparator.comparing;
  
  import com.google.common.base.CharMatcher;
  import com.google.common.base.MoreObjects;
  import com.google.common.base.Strings;
  import com.google.common.collect.DiscreteDomain;
  import com.google.common.collect.ImmutableList;
  import com.google.common.collect.Range;
  import com.google.common.collect.RangeSet;
  import com.google.common.collect.TreeRangeSet;
  import com.google.googlejavaformat.CommentsHelper;
  import com.google.googlejavaformat.Input;
  import com.google.googlejavaformat.Input.Token;
  import com.google.googlejavaformat.Newlines;
  import com.google.googlejavaformat.OpsBuilder.BlankLineWanted;
  import com.google.googlejavaformat.Output;
  import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  
  /*
   * Throughout this file, {@code i} is an index for input lines, {@code j} is an index for output
   * lines, {@code ij} is an index into either input or output lines, and {@code k} is an index for
   * toks.
   */
  
  /**
   * {@code JavaOutput} extends {@link Output Output} to represent a Java output document. It includes
   * methods to emit the output document.
   */
  public final class JavaOutput extends Output {
    private final String lineSeparator;
    private final Input javaInput; // Used to follow along while emitting the output.
    private final CommentsHelper commentsHelper; // Used to re-flow comments.
    private final Map<Integer, BlankLineWanted> blankLines = new HashMap<>(); // Info on blank lines.
    private final RangeSet<Integer> partialFormatRanges = TreeRangeSet.create();
  
    private final List<String> mutableLines = new ArrayList<>();
    private final int kN; // The number of tokens or comments in the input, excluding the EOF.
    private int iLine = 0; // Closest corresponding line number on input.
    private int lastK = -1; // Last {@link Tok} index output.
    private int newlinesPending = 0;
    private StringBuilder lineBuilder = new StringBuilder();
    private StringBuilder spacesPending = new StringBuilder();
  
    /**
     * {@code JavaOutput} constructor.
     *
     * @param javaInput the {@link Input}, used to match up blank lines in the output
     * @param commentsHelper the {@link CommentsHelper}, used to rewrite comments
     */
    public JavaOutput(String lineSeparator, Input javaInput, CommentsHelper commentsHelper) {
      this.lineSeparator = lineSeparator;
      this.javaInput = javaInput;
      this.commentsHelper = commentsHelper;
      kN = javaInput.getkN();
    }
  
    @Override
    public void blankLine(int k, BlankLineWanted wanted) {
      if (blankLines.containsKey(k)) {
        blankLines.put(k, blankLines.get(k).merge(wanted));
      } else {
        blankLines.put(k, wanted);
      }
    }
  
    @Override
    public void markForPartialFormat(Token start, Token end) {
      int lo = JavaOutput.startTok(start).getIndex();
      int hi = JavaOutput.endTok(end).getIndex();
      partialFormatRanges.add(Range.closed(lo, hi));
    }
  
    // TODO(user): Add invariant.
    @Override
    public void append(String text, Range<Integer> range) {
      if (!range.isEmpty()) {
        boolean sawNewlines = false;
        // Skip over input line we've passed.
        int iN = javaInput.getLineCount();
        while (iLine < iN
            && (javaInput.getRanges(iLine).isEmpty()
                || javaInput.getRanges(iLine).upperEndpoint() <= range.lowerEndpoint())) {
          if (javaInput.getRanges(iLine).isEmpty()) {
            // Skipped over a blank line.
            sawNewlines = true;
          }
          ++iLine;
        }
        /*
         * Output blank line if we've called {@link OpsBuilder#blankLine}{@code (true)} here, or if
         * there's a blank line here and it's a comment.
         */
        BlankLineWanted wanted = blankLines.getOrDefault(lastK, BlankLineWanted.NO);
        if ((sawNewlines && isComment(text)) || wanted.wanted().orElse(sawNewlines)) {
          ++newlinesPending;
        }
      }
      if (Newlines.isNewline(text)) {
        /*
         * Don't update range information, and swallow extra newlines. The case below for '\n' is for
         * block comments.
         */
        if (newlinesPending == 0) {
          ++newlinesPending;
        }
        spacesPending = new StringBuilder();
      } else {
        boolean rangesSet = false;
        int textN = text.length();
        for (int i = 0; i < textN; i++) {
          char c = text.charAt(i);
          switch (c) {
            case ' ':
              spacesPending.append(' ');
              break;
            case '\t':
              spacesPending.append('\t');
              break;
            case '\r':
              if (i + 1 < text.length() && text.charAt(i + 1) == '\n') {
                i++;
              }
              // falls through
            case '\n':
              spacesPending = new StringBuilder();
              ++newlinesPending;
              break;
            default:
              while (newlinesPending > 0) {
                // drop leading blank lines
                if (!mutableLines.isEmpty() || lineBuilder.length() > 0) {
                  mutableLines.add(lineBuilder.toString());
                }
                lineBuilder = new StringBuilder();
                rangesSet = false;
                --newlinesPending;
              }
              if (spacesPending.length() > 0) {
                lineBuilder.append(spacesPending);
                spacesPending = new StringBuilder();
              }
              lineBuilder.append(c);
              if (!range.isEmpty()) {
                if (!rangesSet) {
                  while (ranges.size() <= mutableLines.size()) {
                    ranges.add(Formatter.EMPTY_RANGE);
                  }
                  ranges.set(mutableLines.size(), union(ranges.get(mutableLines.size()), range));
                  rangesSet = true;
                }
              }
          }
        }
      }
      if (!range.isEmpty()) {
        lastK = range.upperEndpoint();
      }
    }
  
    @Override
    public void indent(int indent) {
      spacesPending.append(Strings.repeat(" ", indent));
    }
  
    /** Flush any incomplete last line, then add the EOF token into our data structures. */
    public void flush() {
      String lastLine = lineBuilder.toString();
      if (!CharMatcher.whitespace().matchesAllOf(lastLine)) {
        mutableLines.add(lastLine);
      }
      int jN = mutableLines.size();
      Range<Integer> eofRange = Range.closedOpen(kN, kN + 1);
      while (ranges.size() < jN) {
        ranges.add(Formatter.EMPTY_RANGE);
      }
      ranges.add(eofRange);
      setLines(ImmutableList.copyOf(mutableLines));
    }
  
    // The following methods can be used after the Output has been built.
  
    @Override
    public CommentsHelper getCommentsHelper() {
      return commentsHelper;
    }
  
    /**
     * Emit a list of {@link Replacement}s to convert from input to output.
     *
     * @return a list of {@link Replacement}s, sorted by start index, without overlaps
     */
    public ImmutableList<Replacement> getFormatReplacements(RangeSet<Integer> iRangeSet0) {
      ImmutableList.Builder<Replacement> result = ImmutableList.builder();
      Map<Integer, Range<Integer>> kToJ = JavaOutput.makeKToIJ(this);
  
      // Expand the token ranges to align with re-formattable boundaries.
      RangeSet<Integer> breakableRanges = TreeRangeSet.create();
      RangeSet<Integer> iRangeSet = iRangeSet0.subRangeSet(Range.closed(0, javaInput.getkN()));
      for (Range<Integer> iRange : iRangeSet.asRanges()) {
        Range<Integer> range = expandToBreakableRegions(iRange.canonical(DiscreteDomain.integers()));
        if (range.equals(EMPTY_RANGE)) {
          // the range contains only whitespace
          continue;
        }
        breakableRanges.add(range);
      }
  
      // Construct replacements for each reformatted region.
      for (Range<Integer> range : breakableRanges.asRanges()) {
  
        Input.Tok startTok = startTok(javaInput.getToken(range.lowerEndpoint()));
        Input.Tok endTok = endTok(javaInput.getToken(range.upperEndpoint() - 1));
  
        // Add all output lines in the given token range to the replacement.
        StringBuilder replacement = new StringBuilder();
  
        int replaceFrom = startTok.getPosition();
        // Replace leading whitespace in the input with the whitespace from the formatted file
        while (replaceFrom > 0) {
          char previous = javaInput.getText().charAt(replaceFrom - 1);
          if (!CharMatcher.whitespace().matches(previous)) {
            break;
          }
          replaceFrom--;
        }
  
        int i = kToJ.get(startTok.getIndex()).lowerEndpoint();
        // Include leading blank lines from the formatted output, unless the formatted range
        // starts at the beginning of the file.
        while (i > 0 && getLine(i - 1).isEmpty()) {
          i--;
        }
        // Write out the formatted range.
        for (; i < kToJ.get(endTok.getIndex()).upperEndpoint(); i++) {
          // It's possible to run out of output lines (e.g. if the input ended with
          // multiple trailing newlines).
          if (i < getLineCount()) {
            if (i > 0) {
              replacement.append(lineSeparator);
            }
            replacement.append(getLine(i));
          }
        }
  
        int replaceTo = min(endTok.getPosition() + endTok.length(), javaInput.getText().length());
        // If the formatted ranged ended in the trailing trivia of the last token before EOF,
        // format all the way up to EOF to deal with trailing whitespace correctly.
        if (endTok.getIndex() == javaInput.getkN() - 1) {
          replaceTo = javaInput.getText().length();
        }
        // Replace trailing whitespace in the input with the whitespace from the formatted file.
        // If the trailing whitespace in the input includes one or more line breaks, preserve the
        // whitespace after the last newline to avoid re-indenting the line following the formatted
        // line.
        int newline = -1;
        while (replaceTo < javaInput.getText().length()) {
          char next = javaInput.getText().charAt(replaceTo);
          if (!CharMatcher.whitespace().matches(next)) {
            break;
          }
          int newlineLength = Newlines.hasNewlineAt(javaInput.getText(), replaceTo);
          if (newlineLength != -1) {
            newline = replaceTo;
            // Skip over the entire newline; don't count the second character of \r\n as a newline.
            replaceTo += newlineLength;
          } else {
            replaceTo++;
          }
        }
        if (newline != -1) {
          replaceTo = newline;
        }
  
        if (newline == -1) {
          // There wasn't an existing trailing newline; add one.
          replacement.append(lineSeparator);
        }
        for (; i < getLineCount(); i++) {
          String after = getLine(i);
          int idx = CharMatcher.whitespace().negate().indexIn(after);
          if (idx == -1) {
            // Write out trailing empty lines from the formatted output.
            replacement.append(lineSeparator);
          } else {
            if (newline == -1) {
              // If there wasn't a trailing newline in the input, indent the next line.
              replacement.append(after, 0, idx);
            }
            break;
          }
        }
  
        result.add(Replacement.create(replaceFrom, replaceTo, replacement.toString()));
      }
      return result.build();
    }
  
    /**
     * Expand a token range to start and end on acceptable boundaries for re-formatting.
     *
     * @param iRange the {@link Range} of tokens
     * @return the expanded token range
     */
    private Range<Integer> expandToBreakableRegions(Range<Integer> iRange) {
      // The original line range.
      int loTok = iRange.lowerEndpoint();
      int hiTok = iRange.upperEndpoint() - 1;
  
      // Expand the token indices to formattable boundaries (e.g. edges of statements).
      if (!partialFormatRanges.contains(loTok) || !partialFormatRanges.contains(hiTok)) {
        return EMPTY_RANGE;
      }
      loTok = partialFormatRanges.rangeContaining(loTok).lowerEndpoint();
      hiTok = partialFormatRanges.rangeContaining(hiTok).upperEndpoint();
      return Range.closedOpen(loTok, hiTok + 1);
    }
  
    public static String applyReplacements(String input, List<Replacement> replacements) {
      replacements = new ArrayList<>(replacements);
      replacements.sort(comparing((Replacement r) -> r.getReplaceRange().lowerEndpoint()).reversed());
      StringBuilder writer = new StringBuilder(input);
      for (Replacement replacement : replacements) {
        writer.replace(
            replacement.getReplaceRange().lowerEndpoint(),
            replacement.getReplaceRange().upperEndpoint(),
            replacement.getReplacementString());
      }
      return writer.toString();
    }
  
    /** The earliest position of any Tok in the Token, including leading whitespace. */
    public static int startPosition(Token token) {
      int min = token.getTok().getPosition();
      for (Input.Tok tok : token.getToksBefore()) {
        min = min(min, tok.getPosition());
      }
      return min;
    }
  
    /** The earliest non-whitespace Tok in the Token. */
    public static Input.Tok startTok(Token token) {
      for (Input.Tok tok : token.getToksBefore()) {
        if (tok.getIndex() >= 0) {
          return tok;
        }
      }
      return token.getTok();
    }
  
    /** The last non-whitespace Tok in the Token. */
    public static Input.Tok endTok(Token token) {
      for (int i = token.getToksAfter().size() - 1; i >= 0; i--) {
        Input.Tok tok = token.getToksAfter().get(i);
        if (tok.getIndex() >= 0) {
          return tok;
        }
      }
      return token.getTok();
    }
  
    private boolean isComment(String text) {
      return text.startsWith("//") || text.startsWith("/*");
    }
  
    private static Range<Integer> union(Range<Integer> x, Range<Integer> y) {
      return x.isEmpty() ? y : y.isEmpty() ? x : x.span(y).canonical(DiscreteDomain.integers());
    }
  
    @Override
    public String toString() {
      return MoreObjects.toStringHelper(this)
          .add("iLine", iLine)
          .add("lastK", lastK)
          .add("spacesPending", spacesPending.toString().replace("\t", "\\t"))
          .add("newlinesPending", newlinesPending)
          .add("blankLines", blankLines)
          .add("super", super.toString())
          .toString();
    }
  }
  