/**
 * Negative Keyword Conflict Finder
 * by SearchSavior  (search-savior.com)
 *
 * Finds negative keywords that are blocking your own active keywords, at three
 * levels: ad group, campaign, and shared negative keyword lists.
 *
 * It reads. It never changes anything, and it sends nothing anywhere.
 * Results are printed in the log.
 *
 * The last part of each line is the useful bit. Google's own Negative Keyword
 * Conflicts script, now removed from its documentation but forked into most
 * free conflict scripts, asks before comparing any text whether the
 * negative is stricter than the keyword. An exact negative against a phrase
 * keyword is stricter, so that pair is skipped and never reported. The same
 * goes for any non-broad negative against a broad keyword. Lines marked
 * "Google's own script does not report this one" are those.
 *
 * Not covered: account-level negative keywords, which are a separate tier.
 *
 * SETUP
 *   1. Google Ads > Tools > Bulk actions > Scripts > +
 *   2. Paste this in, Authorize, Preview, then Run.
 *   3. Read the log.
 *
 * ON THE PERMISSION IT ASKS FOR
 *   Google Ads scripts have no read-only permission, so the prompt says the
 *   script can edit and delete. This one only reads: there is no mutate call
 *   anywhere in it, which you can confirm by searching the code for "remove",
 *   "create" or "set". Nothing leaves your account.
 */

var CONFIG = {
  MAX_LOG_ROWS: 100,
  MAX_POSITIVES: 150000,
  MAX_NEGATIVES: 150000
};

function main() {
  var account = collectAccount();
  var conflicts = findConflicts(account);

  var missedByGoogle = 0;
  var negativesSeen = {};
  var negativesMissed = {};
  for (var i = 0; i < conflicts.length; i++) {
    var key = conflicts[i].level + '|' + conflicts[i].listName + '|' + conflicts[i].negative;
    negativesSeen[key] = true;
    if (!conflicts[i].googleReports) {
      missedByGoogle++;
      negativesMissed[key] = true;
    }
  }

  Logger.log('Positives checked: ' + account.positiveCount);
  Logger.log('Negatives checked: ' + account.negativeCount);
  Logger.log('Conflicts found: ' + conflicts.length + ' across ' + count(negativesSeen) + ' negatives.');
  Logger.log("Google's own script would not report: " + missedByGoogle +
             ' of those, across ' + count(negativesMissed) + ' negatives.');

  if (!conflicts.length) {
    Logger.log('Nothing blocking. Note that account-level negatives are not checked here.');
    return;
  }

  logConflicts(conflicts);

}

/** Reads everything the check needs, in three passes. */
function collectAccount() {
  var campaigns = {};
  var positiveCount = 0;
  var negativeCount = 0;

  var rows = AdsApp.report(
    'SELECT campaign.id, campaign.name, ad_group.id, ad_group.name, ' +
    'ad_group_criterion.keyword.text, ad_group_criterion.keyword.match_type, ' +
    'ad_group_criterion.negative ' +
    'FROM ad_group_criterion ' +
    "WHERE ad_group_criterion.type = 'KEYWORD' " +
    "AND campaign.status = 'ENABLED' AND ad_group.status = 'ENABLED' " +
    "AND ad_group_criterion.status = 'ENABLED'"
  ).rows();

  while (rows.hasNext()) {
    var row = rows.next();
    var campaignId = row['campaign.id'];
    var adGroupId = row['ad_group.id'];

    if (!campaigns[campaignId]) {
      campaigns[campaignId] = {
        name: row['campaign.name'],
        adGroups: {},
        negatives: [],
        lists: []
      };
    }
    if (!campaigns[campaignId].adGroups[adGroupId]) {
      campaigns[campaignId].adGroups[adGroupId] = {
        name: row['ad_group.name'],
        positives: [],
        negatives: []
      };
    }

    var keyword = normalize(
      row['ad_group_criterion.keyword.text'],
      row['ad_group_criterion.keyword.match_type']
    );
    var isNegative = String(row['ad_group_criterion.negative']).toLowerCase() === 'true';

    if (isNegative) {
      campaigns[campaignId].adGroups[adGroupId].negatives.push(keyword);
      negativeCount++;
    } else {
      campaigns[campaignId].adGroups[adGroupId].positives.push(keyword);
      positiveCount++;
    }

    if (positiveCount > CONFIG.MAX_POSITIVES || negativeCount > CONFIG.MAX_NEGATIVES) {
      throw new Error('This account is larger than the script is set up to handle. ' +
                      'Raise MAX_POSITIVES and MAX_NEGATIVES, or run it on fewer campaigns.');
    }
  }

  var campaignRows = AdsApp.report(
    'SELECT campaign.id, campaign_criterion.keyword.text, campaign_criterion.keyword.match_type ' +
    'FROM campaign_criterion ' +
    'WHERE campaign_criterion.negative = true ' +
    "AND campaign_criterion.type = 'KEYWORD' AND campaign.status = 'ENABLED'"
  ).rows();

  while (campaignRows.hasNext()) {
    var cRow = campaignRows.next();
    var cId = cRow['campaign.id'];
    if (!campaigns[cId]) continue;
    campaigns[cId].negatives.push(normalize(
      cRow['campaign_criterion.keyword.text'],
      cRow['campaign_criterion.keyword.match_type']
    ));
    negativeCount++;
  }

  var lists = AdsApp.negativeKeywordLists().get();
  while (lists.hasNext()) {
    var list = lists.next();
    var listNegatives = [];
    var listKeywords = list.negativeKeywords().get();
    while (listKeywords.hasNext()) {
      var shared = listKeywords.next();
      listNegatives.push(normalize(shared.getText(), shared.getMatchType()));
      negativeCount++;
    }

    var attached = list.campaigns().withCondition('Status = ENABLED').get();
    while (attached.hasNext()) {
      var attachedId = attached.next().getId();
      if (campaigns[attachedId]) {
        campaigns[attachedId].lists.push({ name: list.getName(), negatives: listNegatives });
      }
    }
  }

  return { campaigns: campaigns, positiveCount: positiveCount, negativeCount: negativeCount };
}

/** Walks every ad group and tests every negative that can reach it. */
function findConflicts(account) {
  var conflicts = [];

  for (var campaignId in account.campaigns) {
    var campaign = account.campaigns[campaignId];

    for (var adGroupId in campaign.adGroups) {
      var adGroup = campaign.adGroups[adGroupId];

      var sources = [];
      sources.push({ level: 'Ad group', listName: '', negatives: adGroup.negatives });
      sources.push({ level: 'Campaign', listName: '', negatives: campaign.negatives });
      for (var i = 0; i < campaign.lists.length; i++) {
        sources.push({
          level: 'Shared list',
          listName: campaign.lists[i].name,
          negatives: campaign.lists[i].negatives
        });
      }

      for (var s = 0; s < sources.length; s++) {
        var source = sources[s];
        for (var n = 0; n < source.negatives.length; n++) {
          var negative = source.negatives[n];
          for (var p = 0; p < adGroup.positives.length; p++) {
            var positive = adGroup.positives[p];
            if (!blocks(negative, positive)) continue;

            conflicts.push({
              campaign: campaign.name,
              adGroup: adGroup.name,
              positive: positive.display,
              positiveMatchType: positive.matchType,
              negative: negative.display,
              negativeMatchType: negative.matchType,
              level: source.level,
              listName: source.listName || '-',
              googleReports: !isStricter(negative, positive),
              clears: clearedBy(negative, positive)
            });
          }
        }
      }
    }
  }

  return conflicts;
}

/** True when the negative's text rule catches the keyword's text. */
function blocks(negative, positive) {
  if (negative.matchType === 'BROAD') return hasAllTokens(negative.raw, positive.raw);
  if (negative.matchType === 'PHRASE') return isSubsequence(negative.raw, positive.raw);
  return negative.raw === positive.raw;
}

/**
 * The rule from Google's own conflict script. When the negative is stricter
 * than the keyword, that script returns before testing the text, so the pair
 * is never reported.
 */
function isStricter(negative, positive) {
  if (positive.matchType === 'BROAD') return negative.matchType !== 'BROAD';
  if (positive.matchType === 'PHRASE') return negative.matchType === 'EXACT';
  return false;
}

/** The narrowest match type that stops this negative catching this keyword. */
function clearedBy(negative, positive) {
  if (negative.matchType !== 'BROAD' && negative.raw === positive.raw) return 'Removal only';
  var asPhrase = { raw: negative.raw, matchType: 'PHRASE' };
  if (!blocks(asPhrase, positive)) return 'Narrow to phrase';
  var asExact = { raw: negative.raw, matchType: 'EXACT' };
  if (!blocks(asExact, positive)) return 'Narrow to exact';
  return 'Removal only';
}

function hasAllTokens(negativeText, positiveText) {
  var negativeTokens = negativeText.split(' ');
  var positiveTokens = positiveText.split(' ');
  for (var i = 0; i < negativeTokens.length; i++) {
    if (positiveTokens.indexOf(negativeTokens[i]) === -1) return false;
  }
  return true;
}

function isSubsequence(negativeText, positiveText) {
  return (' ' + positiveText + ' ').indexOf(' ' + negativeText + ' ') >= 0;
}

/** Lowercases, strips match type punctuation, collapses whitespace. */
function normalize(text, matchType) {
  var raw = String(text);
  var type = String(matchType).toUpperCase();

  if (type === 'PHRASE') raw = trim(raw, '"', '"');
  else if (type === 'EXACT') raw = trim(raw, '[', ']');

  raw = raw.replace(/\s+/g, ' ').trim().toLowerCase();

  var display = raw;
  if (type === 'PHRASE') display = '"' + raw + '"';
  else if (type === 'EXACT') display = '[' + raw + ']';

  raw = raw.replace(/\s\+/g, ' ');

  return { raw: raw, display: display, matchType: type };
}

function trim(text, open, close) {
  if (text.substring(0, 1) === open && text.substring(text.length - 1) === close) {
    return text.substring(1, text.length - 1);
  }
  return text;
}

/** Prints the conflicts into the log, for a first run with no spreadsheet. */
function logConflicts(conflicts) {
  var shown = Math.min(conflicts.length, CONFIG.MAX_LOG_ROWS);
  Logger.log('');
  for (var i = 0; i < shown; i++) {
    var c = conflicts[i];
    Logger.log(
      c.negative + ' (' + title(c.negativeMatchType) + ', ' + c.level.toLowerCase() +
      (c.listName !== '-' ? ' "' + c.listName + '"' : '') + ') blocks ' +
      c.positive + ' in ' + c.campaign + ' > ' + c.adGroup + '. ' +
      c.clears + '.' + (c.googleReports ? '' : " Google's own script does not report this one.")
    );
  }
  if (conflicts.length > shown) {
    Logger.log('');
    Logger.log((conflicts.length - shown) + ' more not shown. Raise MAX_LOG_ROWS at the top ' +
               'of the script, or get the spreadsheet version at search-savior.com.');
  }
}

/** Number of keys on a plain object, for counting distinct negatives. */
function count(map) {
  var n = 0;
  for (var key in map) n++;
  return n;
}

function title(matchType) {
  return matchType.charAt(0) + matchType.slice(1).toLowerCase();
}