#412

Committed 09 May 2025 10:37AM UTC coverage: 73.772% (-0.03%) from 73.798%

Build # #412

Build Type

push

Committed by

Commit Message

fix pattern (#342)

* fix issue where matching on patterns can have unexpected results.

Run Details

48 of 56 new or added lines in 2 files covered. (85.71%)

2568 of 3481 relevant lines covered (73.77%)

0.74 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

83.67

/waggle-dance-core/src/main/java/com/hotels/bdp/waggledance/mapping/service/HivePrefixPattern.java

/**
 * Copyright (C) 2016-2025 Expedia, 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.hotels.bdp.waggledance.mapping.service;

import java.util.ArrayList;
import java.util.List;

import com.google.common.annotations.VisibleForTesting;

public class HivePrefixPattern {
  private String prefix;
  private String pattern;
  private final List<String> subPatterns = new ArrayList<>();

  /**
   * Using a dynamic programming algorithm to match a given pattern with an input string,
   * where '*' represents matching any number of any characters,
   * and '.' represents matching a single arbitrary character.
   *
   * @param input input string.
   * @param pattern regular expression.
   * @return A boolean array with a length of one more than the length of the pattern.
   * If the substring of the pattern from index 0 to i+1 can match the input string,
   * the value at index i of the boolean array is true; otherwise, it is false.
   */
  @VisibleForTesting
  static boolean[] matchDp(String input, String pattern) {
    int m = input.length() + 1;
    int n = pattern.length() + 1;
    boolean[] matchingResult = new boolean[n];
    boolean[] prevMatchingResult = new boolean[n];

    matchingResult[0] = true;

    for (int j = 1; j < n; j++) {
      matchingResult[j] = matchingResult[j - 1] && pattern.charAt(j - 1) == '*';
    }

    for (int i = 1; i < m; i++) {
      copy(prevMatchingResult, matchingResult);
      matchingResult[0] = false;
      for (int j = 1; j < n; j++) {
        if (pattern.charAt(j - 1) == '*') {
          matchingResult[j] = prevMatchingResult[j] || prevMatchingResult[j - 1] || matchingResult[j - 1];
        } else {
          matchingResult[j] = prevMatchingResult[j - 1] && (pattern.charAt(j - 1) == '.'
              || input.charAt(i - 1) == pattern.charAt(j - 1));
        }
      }
    }
    return matchingResult;
  }

  static void copy(boolean[] prev, boolean[] current) {
    for (int i = 0; i < prev.length; i++) {
      prev[i] = current[i];
    }
  }

  public HivePrefixPattern(String prefix, String pattern) {
    if (prefix == null || pattern == null) {
      return;
    }
    this.prefix = prefix;
    this.pattern = pattern;
    init();
  }

  private void init() {
    boolean[] match = matchDp(this.prefix, this.pattern);
    if (match[0]) {
      this.subPatterns.add(this.pattern);
    }
    int n = this.pattern.length();
    for (int j = 1; j <= n; j++) {
      if (!match[j]) {
        continue;
      }
      String subPattern = this.pattern.charAt(j - 1) == '*' ?
          this.pattern.substring(j - 1, n) : this.pattern.substring(j, n);
      if (subPattern.isEmpty()) {
        continue;
      }
      this.subPatterns.add(subPattern);
    }
  }

  public String getPrefix() {
    return prefix;
  }

  public String getPattern() {
    return pattern;
  }

  public List<String> getSubPatterns() {
    return subPatterns;
  }

  @Override
  public String toString() {
    return "HivePrefixPattern{" +
        "prefix='" + prefix + '\'' +
        ", pattern='" + pattern + '\'' +
        ", subPatterns=" + subPatterns +
        '}';
  }
}

1	/**
2	* Copyright (C) 2016-2025 Expedia, Inc.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package com.hotels.bdp.waggledance.mapping.service;
17
18	import java.util.ArrayList;
19	import java.util.List;
20
21	import com.google.common.annotations.VisibleForTesting;
22
23	public class HivePrefixPattern {
24	private String prefix;
25	private String pattern;
26	private final List<String> subPatterns = new ArrayList<>();	1✔
27
28	/**
29	* Using a dynamic programming algorithm to match a given pattern with an input string,
30	* where '*' represents matching any number of any characters,
31	* and '.' represents matching a single arbitrary character.
32	*
33	* @param input input string.
34	* @param pattern regular expression.
35	* @return A boolean array with a length of one more than the length of the pattern.
36	* If the substring of the pattern from index 0 to i+1 can match the input string,
37	* the value at index i of the boolean array is true; otherwise, it is false.
38	*/
39	@VisibleForTesting
40	static boolean[] matchDp(String input, String pattern) {
41	int m = input.length() + 1;	1✔
42	int n = pattern.length() + 1;	1✔
43	boolean[] matchingResult = new boolean[n];	1✔
44	boolean[] prevMatchingResult = new boolean[n];	1✔
45
46	matchingResult[0] = true;	1✔
47
48	for (int j = 1; j < n; j++) {	1✔
49	matchingResult[j] = matchingResult[j - 1] && pattern.charAt(j - 1) == '*';	1✔
50	}
51
52	for (int i = 1; i < m; i++) {	1✔
53	copy(prevMatchingResult, matchingResult);	1✔
54	matchingResult[0] = false;	1✔
55	for (int j = 1; j < n; j++) {	1✔
56	if (pattern.charAt(j - 1) == '*') {	1✔
57	matchingResult[j] = prevMatchingResult[j] \|\| prevMatchingResult[j - 1] \|\| matchingResult[j - 1];	1✔
58	} else {	1✔
59	matchingResult[j] = prevMatchingResult[j - 1] && (pattern.charAt(j - 1) == '.'	1✔
60	\|\| input.charAt(i - 1) == pattern.charAt(j - 1));	1✔
61	}
62	}
63	}
64	return matchingResult;	1✔
65	}
66
67	static void copy(boolean[] prev, boolean[] current) {
68	for (int i = 0; i < prev.length; i++) {	1✔
69	prev[i] = current[i];	1✔
70	}
71	}	1✔
72
73	public HivePrefixPattern(String prefix, String pattern) {	1✔
74	if (prefix == null \|\| pattern == null) {	1✔
NEW 75	return;	×
76	}
77	this.prefix = prefix;	1✔
78	this.pattern = pattern;	1✔
79	init();	1✔
80	}	1✔
81
82	private void init() {
83	boolean[] match = matchDp(this.prefix, this.pattern);	1✔
84	if (match[0]) {	1✔
85	this.subPatterns.add(this.pattern);	1✔
86	}
87	int n = this.pattern.length();	1✔
88	for (int j = 1; j <= n; j++) {	1✔
89	if (!match[j]) {	1✔
90	continue;	1✔
91	}
92	String subPattern = this.pattern.charAt(j - 1) == '*' ?	1✔
93	this.pattern.substring(j - 1, n) : this.pattern.substring(j, n);	1✔
94	if (subPattern.isEmpty()) {	1✔
95	continue;	1✔
96	}
97	this.subPatterns.add(subPattern);	1✔
98	}
99	}	1✔
100
101	public String getPrefix() {
NEW 102	return prefix;	×
103	}
104
105	public String getPattern() {
NEW 106	return pattern;	×
107	}
108
109	public List<String> getSubPatterns() {
110	return subPatterns;	1✔
111	}
112
113	@Override
114	public String toString() {
NEW 115	return "HivePrefixPattern{" +	×
NEW 116	"prefix='" + prefix + '\'' +	×
NEW 117	", pattern='" + pattern + '\'' +	×
NEW 118	", subPatterns=" + subPatterns +	×
NEW 119	'}';	×
120	}
121	}

HotelsDotCom / waggle-dance / #412

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous